随机访问数组的时间复杂度
Time complexity of random access of an array
在分析一个算法的时间复杂度时，我们通常认为随机访问一个数组的时间是一个常数（数组的大小n不是一个常数），但是为什么呢？
考虑图灵机模型，其中数组存储在磁带中，要访问数组的特定元素，其磁带头必须移动到该位置，这需要 O(n) 时间。或者有没有其他方法可以为图灵机存储数组，以便随机访问只需要常数时间？
戈登:
Computers are not Turing machines.
"real" 典型通用机器上的数组不存储在 "infinitely long" 线性存储器中，而是存储在 RAM 随机存取存储器 中。从技术上讲，（坦率地说，简化了很多），您只需将 RAM 理解为通过内存地址的路径即可从 RAM 获取任何地址。所以访问任何地址都需要相同的时间。
现在，对于数组，可以直接计算第n个元素的地址，取第一个元素的地址加上单个元素大小的n倍。
请记住：图灵机是一种概念，是关于如何证明和理解某些事物的，并不反映事物实际如何完成的现实.复杂性计算也是如此：当然，在现实中访问向量中的任何元素并不总是需要完全相同的时间，因为计算机科学人员需要做出的关于算法的有趣事情的假设并不总是完全代表每台可以 运行 给定算法的物理机器 -- 真正的现代计算机都有缓存和预取内存控制器，因此访问您 "just" 访问过的一块内存比仅仅获取要快得多任何记忆。
算法分析未考虑内存模型（cpu 寄存器、RAM 和外部存储器）引起的开销。
原因很简单，它会使分析不通用。然后分析将取决于您使用的硬件类型。这会使分析复杂化，并且对一般用途没有用。
数组访问是常数时间的，因为数组元素是连续存储的。将其与链表访问进行对比。在链表中，每个节点都有到下一个节点的地址。这迫使CPU走遍所有n-1个节点才能到达第n个节点。但是对于数组，您可以直接通过 address_to_first_element + (n-1)*size_of_elements 知道地址，因此可以在常数时间内访问元素。
这里的假设是数据存储在随机访问内存中。
对于图灵机，数据存储在磁带上。而磁带是一种线性存取设备。 Wikipedia article 大致相同说：
While they can express arbitrary computations, their minimalistic
design makes them unsuitable for computation in practice: actual
computers are based on different designs that, unlike Turing machines,
use random access memory.
在一个数组中，所有元素都存储在一个连续的内存中location.Thus以访问任何元素，元素的地址计算为数组基地址的偏移量，需要一次乘法来计算应该将什么添加到基地址以获得元素的内存地址。
因此，首先计算该数据类型的元素的大小，然后将其与元素的索引相乘以获得要添加到基地址的值。
由于这个过程需要一次乘法和一次加法，因此可以在常数时间内访问数组元素。
在分析一个算法的时间复杂度时，我们通常认为随机访问一个数组的时间是一个常数（数组的大小n不是一个常数），但是为什么呢？
考虑图灵机模型，其中数组存储在磁带中，要访问数组的特定元素，其磁带头必须移动到该位置，这需要 O(n) 时间。或者有没有其他方法可以为图灵机存储数组，以便随机访问只需要常数时间？
戈登
Computers are not Turing machines.
"real" 典型通用机器上的数组不存储在 "infinitely long" 线性存储器中，而是存储在 RAM 随机存取存储器 中。从技术上讲，（坦率地说，简化了很多），您只需将 RAM 理解为通过内存地址的路径即可从 RAM 获取任何地址。所以访问任何地址都需要相同的时间。
现在，对于数组，可以直接计算第n个元素的地址，取第一个元素的地址加上单个元素大小的n倍。
请记住：图灵机是一种概念，是关于如何证明和理解某些事物的，并不反映事物实际如何完成的现实.复杂性计算也是如此：当然，在现实中访问向量中的任何元素并不总是需要完全相同的时间，因为计算机科学人员需要做出的关于算法的有趣事情的假设并不总是完全代表每台可以 运行 给定算法的物理机器 -- 真正的现代计算机都有缓存和预取内存控制器，因此访问您 "just" 访问过的一块内存比仅仅获取要快得多任何记忆。
算法分析未考虑内存模型（cpu 寄存器、RAM 和外部存储器）引起的开销。
原因很简单，它会使分析不通用。然后分析将取决于您使用的硬件类型。这会使分析复杂化，并且对一般用途没有用。
数组访问是常数时间的，因为数组元素是连续存储的。将其与链表访问进行对比。在链表中，每个节点都有到下一个节点的地址。这迫使CPU走遍所有n-1个节点才能到达第n个节点。但是对于数组，您可以直接通过 address_to_first_element + (n-1)*size_of_elements 知道地址，因此可以在常数时间内访问元素。
这里的假设是数据存储在随机访问内存中。
对于图灵机，数据存储在磁带上。而磁带是一种线性存取设备。 Wikipedia article 大致相同说：
While they can express arbitrary computations, their minimalistic design makes them unsuitable for computation in practice: actual computers are based on different designs that, unlike Turing machines, use random access memory.
在一个数组中，所有元素都存储在一个连续的内存中location.Thus以访问任何元素，元素的地址计算为数组基地址的偏移量，需要一次乘法来计算应该将什么添加到基地址以获得元素的内存地址。 因此，首先计算该数据类型的元素的大小，然后将其与元素的索引相乘以获得要添加到基地址的值。 由于这个过程需要一次乘法和一次加法，因此可以在常数时间内访问数组元素。