algorithm - 解释为什么与链表的 O(n) 时间相比，访问数组的第 n 个元素可以在常数时间 O(1) 内完成？

Question

这是我作业上的一道题，我好像答不上来。有人可以简单地向我解释一下吗？或者只是链表中 O(1) 和 O(n) 之间的区别？

Answer 1

基础先行:所有变量内部都有一个内存地址，指向变量数据保存的物理起点，

现在变量的数据类型告诉存储在变量中的地址位置指向的数据分配多少空间，int 4, long 8, char 4 ...等等。

数组变量只是相同数据类型值的连续分配，数组变量存储第一个数据的内存位置。

数组如何为任何索引提供 O(1) 提取:假设有一个数组变量 A，其中包含数据类型 X 的 N 个元素，每个 X 数据类型在内存中占用 m 个大小，所以自动第一个元素将从 A 的内存位置到 A+m，第二个元素将从 A+m 到 A+m+m = A+m 到 A+2m，因此公式:

从内存位置A开始的数组的第n个索引的内存位置，每个元素在内存中占用m个大小

A+mxn

因此它的 O(1) dip 用于获取数组的索引。

Case with Linked-List : LL 不是连续的，每个元素存储下一个元素的内存位置，所以你必须从第一个开始遍历所有元素到达第 n 个元素，因此它的 O(N)。

重要的是要注意数组的空间复杂度取决于它存储的数据类型并且只能存储相同数据类型的倍数，数组中的插入只能在末尾，而时间复杂度明智的是在其他任何地方插入元素的成本很高，而在 LL 中，空间复杂度虽然取决于它存储的数据，但它可以在每个元素中存储任何类型的数据，而不管前面的元素是什么，并且写入的时间复杂度总是 O(1)，插入也很简单。