为什么访问数组中的元素需要恒定的时间？

Question

让我们说我有一个数组:

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

当我访问一个元素,如[3]时,它在场景后面实际发生了什么？为什么许多算法书籍(如Cormen书籍......)说它需要一个恒定的时间？

(我只是低级编程的菜鸟,所以我想向你们学习更多)

Answer 1

有效地,该数组由存储器位置(指针)所知.访问a[3]可以在恒定时间内找到,因为它只是location_of_a + 3*sizeof(int).

在C中,您可以直接看到这一点.请记住,a[3]它是相同的*(a+3)- 就它正在做的事情而言更清楚一些(取消引用指针"3项").

Answer 2

具有索引0到9的10个整数变量的数组可以在存储器地址2000,2004,2008,... 2036处存储为10个字,使得具有索引​​i的元素具有地址2000 + 4×i.这个过程需要一个乘法和一个加法.因为这两个操作需要一个恒定的时间.所以我们可以说访问可以在恒定的时间内执行

Answer 3

只是要完整,"在线性时间访问什么结构？" 甲链表结构以线性时间访问.要获得n元素,您必须通过n-1以前的元素.你知道,像录音机或VHS录音带一样,你必须等到很长一段时间才能到达磁带/ VHS的末端:-)

数组更类似于硬盘:每个点都可以在"常量"时间访问:-)

这就是计算机的RAM称为RAM:随机存取存储器的原因.如果您知道其地址而不遍历该位置之前的所有内存,则可以转到任何位置.

有些人告诉我HD访问并非真正处于不变时间(访问时我的意思是"定位头部并读取HD的一个扇区的时间").我不得不说我不确定.我用谷歌搜索过,我还没有发现任何人在谈论它.我知道时间不是线性的,因为它仍然是随机访问的.最后,如果您认为高清访问对您来说不够稳定(但那么,什么是常量？RAM的访问？考虑缓存,预取,数据位置和编译器优化？),请随意考虑这句话因为一个阵列更像是一个USB磁盘棒:每个点都可以在"恒定"时间内访问:-)

Answer 4

"恒定时间"实际上意味着"不依赖于'问题规模'的时间".对于'问题'"从容器中取出东西","问题大小"是容器的大小.

无论容器大小如何,访问数组元素花费的时间基本相同(这是一种简化),因为使用一组固定的步骤来检索元素:计算其在内存中的位置(这也是一种简化),然后检索内存中该位置的值.

例如,链表不能这样做,因为每个链接都指示下一个链接的位置.要找到一个元素,你必须完成以前的所有元素; 平均而言,你将通过容器的一半工作,因此容器的大小显然很重要.

Answer 5

因为数组按顺序存储在内存中.实际上,当您访问数组[3]时,您正在告诉计算机,"获取数组开头的内存地址,然后向其中添加3,然后访问该位置." 由于添加需要恒定时间,因此阵列访问也是如此!