为什么访问一个数组中的元素需要一段时间？
可以说我有一个数组为：
int a [] = {4,5,7,10,2,3,6}
当我访问一个元素时，例如[3]，它在场景后面究竟发生了什么？ 为什么许多algorithm书（如Cormen书…）说，它需要一个不变的时间？
（我只是低级编程的一个小菜鸟，所以我想向你们学习更多）
只是要完成，“线性时间访问什么结构？” 链表结构是以线性时间访问的。 要获得n元素，你必须通过n-1前面的元素。 你知道，就像录音机或VHS录像带一样，要走到磁带/ VHS的末端，你必须等待很长时间:-)
一个数组更类似于硬盘：每个点都可以在“常量”时间访问:-)
这就是计算机的RAM被称为RAM：Random Access Memory的原因。 如果您知道其地址，则可以前往任何位置，而无需遍历该位置之前的所有内存。
有些人告诉我，高清访问并不是真正的恒定时间（通过访问我的意思是“定位头部和读取HD的一个部分的时间”）。 我不得不说，我不确定。 我已经search了一下，我还没有发现有人说这个。 我知道时间不是线性的，因为它仍然是随机访问的。 最后，如果您认为高清访问对于您来说不够稳定（但是，考虑到高速caching，预取，数据位置和编译器优化，那么什么是恒定的RAM访问？），可以随意考虑这个句子作为一个数组更像是一个USB磁盘棒：每个点都可以在“恒定”时间访问:-)
数组有效地被存储位置（指针）所知。 访问a[3]可以在固定时间内find，因为它只是location_of_a + 3 * sizeof（int）。
在C中，你可以直接看到这个。 记住， a[3]和*(a+3)是相同的 – 就它在做什么而言更清楚一些（取消引用“3 items”指针）。
具有索引0至9的10个整数variables的数组可以作为10个字存储在存储器地址2000,2004,2008，…，2036中，使得具有索引i的元素具有地址2000 + 4×i。 这个过程需要一个乘法和一个加法，因为这两个操作需要一定的时间，所以我们可以说访问可以在一个定时执行
因为数组按顺序存储在内存中。 所以实际上，当你访问数组[3]时，你正在告诉计算机：“获取数组开头的内存地址，然后添加3，然后访问该地点。 由于添加需要时间，所以数组访问！
“恒定时间”实际上是指“不依赖于问题大小的时间”。 对于“问题”，“从容器中取出某物”，“问题大小”是容器的大小。
访问一个数组元素需要的时间基本相同（这是一个简化），因为使用一组固定的步骤来检索元素：它在内存中的位置（这也是一个简化）被计算出来，然后检索内存中该位置的值。
例如，链接列表不能这样做，因为每个链接都指示下一个链接的位置。 要find一个元素，你必须通过所有以前的工作; 平均来说，你将通过一半的容器工作，所以容器的大小显然很重要。
一个数组是连续的，意味着数组中的下一个元素的地址与当前数组的地址相邻。 所以如果你想得到一个数组的第5个元素，你可以通过总结数组的基地址来计算第5个元素的地址。这个直接地址现在被直接用来获取该地址的元素。
您现在可以在这里进一步提出同样的问题 – “计算机如何直接知道/访问计算出的地址？” 这是计算机内存（RAM）的性质和原理。 如果你对RAM如何访问任何地址有更多的兴趣，你可以在任何计算机组织文本中find它，或者你可以直接google。
数组是相似types数据的集合。 因此，如果你知道数组的基地址和数据types，你可以很容易地使用下面的公式获得元素Array [i]：
int takes 4 bytes in a 32 bit system. int array[10]; base address=4000; location of 7th element:4000+7*4. array[7]=array[4000+7*4];
因此，如果知道它所保存的基本地址和数据types，就可以清楚地看到你可以在恒定时间内获得第i个元素。 请访问此链接以了解有关arrays数据结构的更多信息。
如果我们知道需要访问的内存位置，那么这个访问是在不变的时间。 在数组的情况下，通过使用基指针，元素的索引和元素的大小来计算存储器位置。 这涉及乘法和加法操作，需要一定的时间来执行。 因此，数组内的元素访问需要一定的时间
