C++中的数组寻址，是线性时间还是固定时间

[LuckyPocketWatch]

比如

int datas[] = new int[m];
int v = *(datas + n);

在上述代码中，向系统申请了一段连续的内存，用于存放 m 个 int,然后需要访问第 n 个元素，那编译器 or 系统是如何处理(datas + n)这段代码的，

也就是说，当 m 和 n 都趋向于无穷大的时候（在系统的可接受范围内）

int v = *(datas + n);

这句代码执行的时间是固定的 O(1)时间，还是 O(n)？

另外，当 n 趋向于无穷大的时候，下列 2 句代码执行的时间差距有多大

int v1 = *(datas + 1);
int v2 = *(datas + n);

[Inn0Vat10n]

1 、O(1)
2 、不考虑编译器优化 /cache 等的话，没有差距

[ysc3839]

只从编译后代码来看那应该是 O(1)，因为编译出的代码中没有循环。但是具体运行耗时就得看平台了。

[Jooooooooo]

这涉及好几级的缓存...比如数据被虚拟内存置换到硬盘上了, 这读起来就算是 O(1) 的也会很慢. 但机械硬盘和 ssd 又不一样. 研究这种问题你得把假设讲明白.

[Saxton]

连续的内存块地址也是连续的，在这片已知的连续内存块访问任意一个地址都是 O （ 1 ），因为都是已知的

[yannxia]

代码上是 O(1)，具体的硬件上嘛，因为 L1/L2/L3/ 有限，就不一定是一模一样的了。

[Origami404]

当 N 趋向无限大时，使用二进制编码索引的话，理论上应该是 O （ logN ）的，因为最快的也就是二分去查找对应的单元格。

而平时认为的单次内存操作 O （ 1 ）只不过是 **目前人类的计算机设计 /内存实现** 把对“由定长二进制地址找单元格”这个操作硬编码到硬件，从而对上层程序体现出来的特点罢了。外星人的电脑设计很可能就会直接底层支持任意长索引以至于它们的内存读写是 O （ logN ）的。

所以要多学学纯函数式编程，万一外星人来侵略地球了还能给它们写写电脑病毒。（🐶，最近外星人入侵电影看多了）

[cpstar]

数组，不是链表结构，不需要挨个遍历。直接跳过去
差别就是 1 和 n 的计算难度，一个直接加一，另一个是挪几步缓存 add 之后再挪回去。

[Juszoe]

不学计算机组成，编程处处是魔法 (🐶

[haolongsun]

重修 csapp 吧

[dcsuibian]

O(1)的。
数组寻址实际上就是数组的地址加上一个 n 号元素的偏移量（ n*sizeof(int)），就得出了 n 号元素的地址。然后访问。
同时，RAM 里的 R 是 Random ，但不是“随机”而是“任意”，指的是：你给的任意一个地址，访问所花的代价都是一样的。（对比机械硬盘，访问盘中间的数据会快一点）
所以你访问数组第一个元素和访问第一万个元素的代价是一样的。


O(n)的话，那得是一个一个找过去的链表了。

[icyalala]

单算法来说当然是 O(1)
但实际算下来有一堆可能性。比如那段内存之前访问过，刚好在 CPU Cache 里，那不同等级的 Cache 延迟不一样。如果触发了 page fault 那延迟更大。要是开启 NUMA ，那跨 NUMA 节点访问延迟也不一样。

[ipwx]

不学计算机组成，编程处处是魔法 (🐶

[dcsuibian]

@Origami404 我觉得应该不是。
因为当地址到达后，每一位的信号都应该是并行发出的。没有必要等到第一位完全起作用了再弄第二位。

如果真是 O(logN)的话，那 64 位计算机花的时间就是 32 位计算机的 2 倍了。

[feather12315]

就算触发 PF 、cache Miss ，它也是 O(1)

[yanqiyu]

如果你的程序被一台纸带机模拟（即存储器不能随机访问，那么就会是 O(n))，在带有随机存储器的机器上当然是 O(1)

[johnkiller]

要取某项数据，只需要知道它的内存地址。

而得到数组某项的内存地址，
就是一次纯粹地址加法，
对于计算机而言，
n+1 和 n+9999 ，在 cpu 运算上是没有任何区别。

所以结论肯定都是 O(1)

[yehoshua]

《计算机组成原理》 《深入理解计算机系统》

[FYFX]

我其实挺好奇你怎么理解哈希表的访问时间的

[LuckyPocketWatch]

@haolongsun
土木狗转行自学的编程，缺乏很多系统知识

[ColorfulBoar]

我以前也想过类似的问题，当时以为考虑这个时间之后理论上 hashtable 和 map 复杂度就没区别了，后来反应过来我可能那几天烤鹅吃多了……
不考虑物理实现的话本来就是只数抽象机上读写内存的次数，那这个时间就是常数；考虑物理实现 N -> ∞ 就是个并不 well-defined 的事情，所以这个问题没有意义。
非要算个玩的话，真插足够多根内存……恭喜电脑爆炸了你得到了一个黑洞；控制一下自己不到那个质量上限……按 Bekenstein bound 可能你得到了一个 log N 的模型，如果觉得“现实”系统（其实你看我这放飞自我了就知道现在并没有在严肃讨论任何人类世界存在的东西）受 area law 支配\sqrt{2}{log N}；再小一点你可以把内存堆叠在 3 维空间里，那 length scale 增长速度是\sqrt{3}{log N}（光速是固定的所以这就是时间增长速度的下限）……所以这种鬼东西有什么意义？如果你想说不是真取这个极限，只是考虑足够大的时候的渐进行为，那我觉得渐进行为并不在有限范围的有意义，我可以用任何我喜欢的东西来拟合它的增长。
换句话说复杂度只对真的能取极限的东西——比如抽象机——有意义，脱离抽象机之后它更多是个比喻。现实中所有能真的取 N -> ∞ 极限的地方都是因为重整化群流向对应的 fixed point ，所以某些我们感兴趣的 observable 稳定下来了（回忆一下我们管这个极限叫 thermodynamic limit...），同时这也是我们能考察 critical exponent （即某种“渐进行为”）的原因。
（免责声明：我对 complexity 没兴趣，以上相关部分都是没睡醒瞎写的，也不知道它们现在又搞出什么新鲜玩意了）