为什么在访问数组的元素需要一定的时间？ [英] why does accessing an element in an array take constant time?

问题描述

可以说我有一个数组：

int类型的[] = {} 4,5,7,10,2,3,6

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

当我访问一个元素，如[3]，这是什么实际发生的幕后？
为什么许多算法的书籍（如Cormen书...）说，它需要一定的时间？

when I access an element, such as a[3], what does it actually happen behind the scene? Why does many algorithm books (such as the Cormen book...) say that it takes a constant time?

（我只是在低层次的编程一个小白，所以我想了解更多从你们）

(I'm just a noob in low-level programing so I would like to learn more from you guys)

推荐答案

只是要完成，是什么结构，线性时间被访问？一个链表结构线性时间访问。为了让你必须通过来游 N 元素n-1 previous元素。你知道，像磁带录音机或VHS录像带，去哪里磁带/ VHS的最后，你不得不等待很长的时间： - ）

Just to be complete, "what structure is accessed in linear time?" A Linked List structure is accessed in linear time. To get the n element you have to travel through n-1 previous elements. You know, like a tape recorder or a VHS cassette, where to go to the end of the tape/VHS you had to wait a long time :-)

数组是更类似于硬盘：每一个点是常量时间访问:-)

An array is more similar to an hard disk: every point is accessible in "constant" time :-)

这是一台计算机的RAM称为RAM的原因：随机存取存储器。你可以去任何地方，如果你知道它的地址，而该位置之前遍历所有的内存。

This is the reason the RAM of a computer is called RAM: Random Access Memory. You can go to any location if you know its address without traversing all the memory before that location.

有些人告诉我，高清访问是不是真的在固定时间（如通过访问我的意思是时间到头部位置并读取HD的一个部门）。我不得不说，我不知道这一点。我用Google搜索周围，我还没有发现任何人讲它。我知道，时间不是线性的，因为它仍然是随机访问。最后，如​​果你认为高清访问是不是对你不够不变（但，什么是不变的？RAM的访问？考虑缓存，prefetching，数据局部性和编译器优化？），随意考虑句子的数组是更类似于U盘棒：每一个点是常量时间访问： - ）的

Some persons told me that HD access isn't really in constant time (where by access I mean "time to position the head and read one sector of the HD"). I have to say that I'm not sure of it. I have googled around and I haven't found anyone speaking of it. I DO know that the time isn't linear, because it is still accessed randomly. In the end, if you think that HD access isn't constant enough for you (but then, what is constant? the access of the RAM? considering Cache, Prefetching, Data Locality and Compiler optimizations?), feel free to consider the sentence as An array is more similar to an USB disk stick: every point is accessible in "constant" time :-)

这篇关于为什么在访问数组的元素需要一定的时间？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！