根据 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))?
发布评论