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);

[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 的情况而言，“基本操作”不应该就是“一次访存”，而应该是如我楼上所言的“根据一个位来排除”。因为不管怎么说将涉及一个无限长对象的操作定义为“基本操作”都是荒谬的。