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

问题描述

根据维基百科，访问数组中的任何单个元素需要固定的时间，因为只需执行一项操作即可定位.

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(log 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屋！