c - 为什么访问数组中的元素需要常数时间？

Question

假设我有一个数组:

int a[]={4,5,7,10,2,3,6}

当我访问一个元素时，例如 a[3]，幕后究竟发生了什么？为什么很多算法书(比如Cormen书...)都说需要常数时间？

(我只是底层编程的菜鸟，所以我想向你们学习更多)

Answer 1

数组实际上是通过内存位置(指针)知道的。访问 a[3] 可以在常数时间内找到，因为它只是 location_of_a+3*sizeof(int)。

在C中，你可以直接看到这个。请记住，a[3] 与 *(a+3) 相同 - 就其作用而言更清楚一点(取消引用指针“3 项” “结束了)。