顺序扫描数组与链表的时间复杂度？
Time complexity of sequentially scanning an array vs a linked list?
由于数组的元素连续存储在内存中，我知道顺序扫描数组的所有元素比在相同大小的链表中快得多。对于前者，您只需增加一些索引变量，然后读取该索引处的值，而对于 LL，您必须读取指针，然后在非连续内存地址处获取数据。我的问题具体是我们如何根据时间复杂度对这两种情况进行分类？
对于扫描数组，执行 n * 随机访问即 O(1) 操作是否意味着整体变成 O(n)？在那种情况下不会都是 O(n)?
抱歉，如果这个问题没有意义，可能我对时间复杂度的理解不是很好。
不幸的是，您没有理解这些东西是如何工作的。
- 顺序扫描所有数组元素的时间复杂度为 O(n)，
n 的大小
数组，因为您将访问每个元素。您将需要计算每个地址并获取数据 n 次；
- 顺序扫描所有 linked 列表元素是 O(n)，
n 是 linked 列表的大小，因为您将通过 links;
- 访问一个数组的元素是O(1)，因为访问涉及一次内存地址计算和一次读取过程；
- 访问一个 linked lisk 的一个元素是 O(n)，
n 你想要访问的位置，因为你需要到达第 n 个元素跳跃每个 link 直到到达所需的元素。
访问数组中某个索引处的值，比方说 500，是“立即的”(O(1))，而对于链表，您必须迭代 500 多个节点才能获得想要的节点（ O(n)).
因此，对于数组，容器开头或末尾的索引可以以相同的速度访问，而对于链表，索引越高，获取它的时间就越长。
相反，在链表中插入节点简单快捷，而在数组中插入节点则较慢。
所以问题变成了更常见的操作是什么：访问索引（写入、读取）或操作容器结构（插入、删除）？答案似乎显而易见，但在某些情况下可能并非如此。
你说得对
- 顺序扫描链表或数组需要时间O(n)，那
- 由于引用的局部性，扫描数组比扫描链表快得多。
怎么会这样？这个问题与您用 O(n) 计算的内容有关。通常，在对算法进行分析时，我们假设在内存中查找一个位置需要时间 O(1)，并且由于在这两种情况下您都在进行 O(n) 内存查找，因此总时间为 O(n)。
但是，所有内存查找花费相同时间的假设在实践中并不是一个很好的假设，尤其是对于链接结构。您有时会看到以不同方式执行的分析。我们假设，在机器的某个地方，有一个缓存可以随时保存 B 元素。每次我们进行内存查找时，如果它在缓存中，它（基本上）是空闲的，如果它不在缓存中，那么我们会做一些工作来加载该内存地址——加上该位置周围的内存内容——到缓存中。然后我们只关心我们必须将某些东西加载到缓存中的次数，因为这样可以更准确地预测运行时间。
在链表的情况下，单元格可以随机分散在整个内存中，我们期望在扫描链表时进行 Θ(n) 次内存传输，因为我们基本上永远不会期望有链接列出已经在缓存中的单元格。然而，对于一个数组，每当我们发现一个数组元素不在缓存中时，我们将所有相邻的内存位置拉入缓存，这意味着接下来的几个元素肯定会在缓存中。这意味着只有（大约）每 1/B 次查找会触发缓存未命中，因此我们希望进行 Θ(n / B) 次内存传输。这从理论上预测了我们从经验上看到的——顺序扫描数组比链表快得多。
所以总而言之，这实际上是一个关于你测量什么以及如何测量的问题。如果你只计算内存访问，那么两个顺序访问都需要 O(n) 内存访问，因此需要 O(n) 时间。但是，如果您只关心缓存未命中，那么动态数组的顺序访问需要 Θ(n / B) 次传输，而链表扫描需要 Θ(n) 次传输，这就是链表看起来更慢的原因。
在为数据库设计数据结构时经常使用这种分析。在数据库和文件系统中广泛使用的 B-tree（及其相关的 B+ 树）专门针对磁盘页面的大小进行了调整，以减少内存传输。最近的工作是设计“cache-oblivious”数据结构，即使不知道其大小也始终充分利用缓存。
由于数组的元素连续存储在内存中，我知道顺序扫描数组的所有元素比在相同大小的链表中快得多。对于前者，您只需增加一些索引变量，然后读取该索引处的值，而对于 LL，您必须读取指针，然后在非连续内存地址处获取数据。我的问题具体是我们如何根据时间复杂度对这两种情况进行分类？
对于扫描数组，执行 n * 随机访问即 O(1) 操作是否意味着整体变成 O(n)？在那种情况下不会都是 O(n)?
抱歉，如果这个问题没有意义，可能我对时间复杂度的理解不是很好。
不幸的是，您没有理解这些东西是如何工作的。
- 顺序扫描所有数组元素的时间复杂度为 O(n)，
n的大小 数组，因为您将访问每个元素。您将需要计算每个地址并获取数据n次； - 顺序扫描所有 linked 列表元素是 O(n)，
n是 linked 列表的大小，因为您将通过 links; - 访问一个数组的元素是O(1)，因为访问涉及一次内存地址计算和一次读取过程；
- 访问一个 linked lisk 的一个元素是 O(n)，
n你想要访问的位置，因为你需要到达第 n 个元素跳跃每个 link 直到到达所需的元素。
访问数组中某个索引处的值，比方说 500，是“立即的”(O(1))，而对于链表，您必须迭代 500 多个节点才能获得想要的节点（ O(n)).
因此，对于数组，容器开头或末尾的索引可以以相同的速度访问，而对于链表，索引越高，获取它的时间就越长。
相反，在链表中插入节点简单快捷，而在数组中插入节点则较慢。
所以问题变成了更常见的操作是什么：访问索引（写入、读取）或操作容器结构（插入、删除）？答案似乎显而易见，但在某些情况下可能并非如此。
你说得对
- 顺序扫描链表或数组需要时间O(n)，那
- 由于引用的局部性，扫描数组比扫描链表快得多。
怎么会这样？这个问题与您用 O(n) 计算的内容有关。通常，在对算法进行分析时，我们假设在内存中查找一个位置需要时间 O(1)，并且由于在这两种情况下您都在进行 O(n) 内存查找，因此总时间为 O(n)。
但是，所有内存查找花费相同时间的假设在实践中并不是一个很好的假设，尤其是对于链接结构。您有时会看到以不同方式执行的分析。我们假设，在机器的某个地方，有一个缓存可以随时保存 B 元素。每次我们进行内存查找时，如果它在缓存中，它（基本上）是空闲的，如果它不在缓存中，那么我们会做一些工作来加载该内存地址——加上该位置周围的内存内容——到缓存中。然后我们只关心我们必须将某些东西加载到缓存中的次数，因为这样可以更准确地预测运行时间。
在链表的情况下，单元格可以随机分散在整个内存中，我们期望在扫描链表时进行 Θ(n) 次内存传输，因为我们基本上永远不会期望有链接列出已经在缓存中的单元格。然而，对于一个数组，每当我们发现一个数组元素不在缓存中时，我们将所有相邻的内存位置拉入缓存，这意味着接下来的几个元素肯定会在缓存中。这意味着只有（大约）每 1/B 次查找会触发缓存未命中，因此我们希望进行 Θ(n / B) 次内存传输。这从理论上预测了我们从经验上看到的——顺序扫描数组比链表快得多。
所以总而言之，这实际上是一个关于你测量什么以及如何测量的问题。如果你只计算内存访问，那么两个顺序访问都需要 O(n) 内存访问，因此需要 O(n) 时间。但是，如果您只关心缓存未命中，那么动态数组的顺序访问需要 Θ(n / B) 次传输，而链表扫描需要 Θ(n) 次传输，这就是链表看起来更慢的原因。
在为数据库设计数据结构时经常使用这种分析。在数据库和文件系统中广泛使用的 B-tree（及其相关的 B+ 树）专门针对磁盘页面的大小进行了调整，以减少内存传输。最近的工作是设计“cache-oblivious”数据结构，即使不知道其大小也始终充分利用缓存。