为什么要在恒定时间内访问数组中的任何单个元素（O（1））？ [英] Why is accessing any single element in an array done in constant time ( O(1) )?

问题描述

根据 Wikipedia ，访问数组中的任何单个元素

According to Wikipedia, accessing any single element in an array takes constant time as only one operation has to be performed to locate it.

对我来说，幕后发生的事情可能看起来像这样：

To me, what happens behind the scenes probably looks something like this:

a）搜索是线性进行的（例如，我要访问元素5。我从索引0开始搜索，如果它不等于5，则转到索引1，依此类推。）
这是O（n）-其中n是数组的长度

a) The search is done linearly (e.g. I want to access element 5. I begin the search at index 0, if it's not equal to 5, I go to index 1 etc.) This is O(n) -- where n is the length of the array

b）如果将数组存储为B树，则将得到O （登录n）

b) If the array is stored as a B-tree, this would give O(log n)

我看不到其他方法。

有人可以解释为什么以及如何做到这一点。在O（1）中？

Can someone please explain why and how this is done in O(1)?

推荐答案

数组从特定的内存地址开始 start 。每个元素占用相同数量的字节 element_size 。从起始地址开始，数组元素在内存中一个接一个地放置。因此，您可以使用 start + i * element_size 来计算元素 i 的内存地址。此计算与数组大小无关，因此是 O（1）。

An array starts at a specific memory address start. Each element occupies the same amount of bytes element_size. The array elements are located one after another in the memory from the start address on. So you can calculate the memory address of the element i with start + i * element_size. This computation is independent of the array size and is therefor O(1).

这篇关于为什么要在恒定时间内访问数组中的任何单个元素（O（1））？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！