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 没兴趣，以上相关部分都是没睡醒瞎写的，也不知道它们现在又搞出什么新鲜玩意了）

[msg7086]

内存存取速度是 O(1)的。如果你在磁带机上做同样的操作就是 O(n)的，因为磁带要倒带完才能访问。

[iceheart]

objdump -d 可解。
vc 可以参考输出汇编指令。
数组整数数组的随机访问一般是

[iceheart]

整数数组的访问一般是一到两条机器指令，复杂度必然是 O(1)的

[ColorfulBoar]

@ColorfulBoar #20
注：
1. 对于经典内存以上 log N 都应该换成 N ，N 为内存大小，上限是 2^地址位数（因为内存片大小就得跟着它增长，你把电信号发过去就会花这么多时间）（也就是说 64 位能比 32 位慢 2^(32/3) = 1625.49867722 > 1145.14 倍，所以我也不知道这有啥意义，可能红石电路 RAM 有点用？）
2. log N 是我瞎猜的 quantum RAM 花的时间，08 年有篇叫 quantum random access memory 的 PRL ，但好像虽然看起来是这么回事又我想要的不太一样，懒得细看了，另外我也不知道现在（考虑 error-correction 等问题之后，不然没法用）即使是在理论上能做成什么样……
3. 考虑到其实 C++只定义了抽象机或者大 O 记号只对真正能取极限的地方有定义或者啥类似的理由，比起不停加假设乱猜现实中会怎么样，还是认为这问题没意义比较省脑子。 [广告] 我们野猪教推荐：思考简单的问题，做容易的判断。
(复杂的反正花再长时间也想不清楚，能做对几个简单却重要的判断已经足够好了)

ack: 与 @geelaw 的私人通信使得这楼能出现

[YouRTBUG]

复杂度为 O(1)，其中还包括虚实地址转换、层级页表、L1/L2 Cpu cache, CacheLine 和 TLB 。 要了解的话从指针如何访问到实际的物理地址学习。

[Tanix2]

new 从堆里找空间，分配的空间大可能会慢一点，这个和堆管理的方式有关
访存涉及到 cache ，不在 cache 里会慢个几十倍，不考虑 cache 的话就是 O(1)

[0xFDA64]

数组是连续地址，编译后能直接偏移获得取的那个元素的地址，是 o(1)。
不要扯上缓存，扯上缓存的那还用什么大 o 表示法。

[codehz]

首先先明确一点，复杂度不反映实际情况，它也没必要反映现实，就像你做经典物理题目不应该考虑相对论。
复杂度显然是在抽象机器的模型上的描述，而且不同场景下抽象机器也可以完全不同，所以讨论复杂度的时候，显然要把采用的模型先作为共识，不然只能是鸡同鸭讲，结果自然没有任何意义。
讨论到寻址这一层的时候，自然要选取一个让结果不是常数的机器模型。但是这并不代表在讨论排序算法的时候，也需要用这样的机器模型，这是两件完全不同的事情，关注点根本不一样。

[someonedeng]

去掉细节 O （ 1 ） 就行了

[MoYi123]

大 O 表示法 是问题规模和运行时间的多项式关系, 和具体运行时间长短有什么关系?

[secondwtq]

大概明白楼主的意思，但是楼主的表达有点问题导致楼严重歪了 ...

就算不考虑“复杂度”定义的问题，楼主给出的几句代码的“执行时间”也是无法量化的。因为现代优化编译器和 OoO 处理器是基于*依赖*来运行的，单纯 load 一个值不用会被编译器优化掉，就算写汇编强行让处理器执行也不会有可直接观察到的差别。楼主必须给出这些值如何被使用，这问题才有意义。

[Origami404]

@dcsuibian 大 O 计数法只有在规定了什么操作是 O （ 1 ）的时候才有意义，它是计量“基本操作数”与输入规模的关系而不是运行时间与输入规模的关系。就您提出的例子而言，“64 位计算机花的时间是 32 位的两倍”是不正确的说法，正确的说法是“64 位计算机进行一次访存需要的“基础操作”数量是 32 位的 2 倍”，这里我把“基础操作”定义为“根据一个位来筛选掉一半内存单元格”。而执行时间自然是取决于这些基本操作需要跑多久和能不能并行跑的。

[Origami404]

@dcsuibian 而我认为对于楼主这种 N -> \inf 的情况而言，“基本操作”不应该就是“一次访存”，而应该是如我楼上所言的“根据一个位来排除”。因为不管怎么说将涉及一个无限长对象的操作定义为“基本操作”都是荒谬的。