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

LuckyPocketWatch · 7 小时 21 分钟前 · 935 次点击

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

18 条回复 • 2022-07-25 01:00:05 +08:00

Inn0Vat10n 7 小时 19 分钟前

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

ysc3839 7 小时 17 分钟前 via Android

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

Jooooooooo 6 小时 52 分钟前

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

Saxton 6 小时 49 分钟前

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

yannxia 6 小时 37 分钟前

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

Origami404 6 小时 34 分钟前 via Android

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

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

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

cpstar 6 小时 30 分钟前

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

Juszoe 6 小时 27 分钟前

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

haolongsun 4 小时 42 分钟前

重修 csapp 吧

dcsuibian 3 小时 17 分钟前

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

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