为什么遍历列表是线性时间？
Why is it linear time to traverse a list?
大家都知道，遍历一个长度为n的列表，时间复杂度为O(n)。这是因为假定从列表的一个元素到下一个元素的每一步都在 O(1) 时间内完成。如果我知道我需要存储的最长列表的长度最多为 4，那么如果可以的话，我会安排每个元素都存储在一个寄存器中，其中一个 2 位地址为 00、01、10、或 11. 那么读取正确地址并到达那里的任务只需要知道几位。
但是，我一直在想，如果一个列表的长度类似于 2^100，那么指针的使用就会变慢。看来要区分列表中两个不同元素的寄存器，处理器必须首先消化 100 位地址信息，然后才能知道接下来要处理哪个寄存器。这将使每个步骤的时间需求更像 Theta(log n)，而完整遍历的时间需求为 O(nlog(n)).
你完全正确。如果有人说遍历一个列表 if O(n)，那是基于这样的假设，即你可以在常数时间内从一个元素到达下一个元素。如果你改变这些假设，你可能会得到不同的时间复杂度。
当人们陈述算法的时间复杂度并将其用于讨论在真实计算机上的执行时，通常会掩盖以下事实：
在真实的物理计算机上，不同可能输入的数量总是有限的，所以计算机实际上是一个有限状态机（而不是图灵机），每个算法的复杂度都是O( 1), 严格来说（可能有一个相当大的常数因子！）。但是我们推断这个有限状态机来推断它的行为，就好像它不是有限的一样。
在您的示例中，列表遍历算法的可能输入的有限数量（实际上）受 CPU（例如 64 位）的字长限制，并且您不能拥有长度列表2^100（使用通常的 pointer-based 算法）。所以严格来说，在 64 位 CPU 上遍历列表的复杂度是 O(1)，但它 在可能的输入范围内表现得像 O(n) .对于超出该范围的输入，外推会失效。 所有算法在真实物理计算机上运行都是如此。
您混淆了不同的术语。
n指的是列表中的元素个数。
从一个元素移动到下一个元素的时间确实通常被认为是 O(1)。
non-trivial地址解析的例子对整体复杂度没有影响，只要地址解析受常数限制即可。所以即使列表中有 2100 个元素并且 CPU 必须执行几个额外的操作来检索下一个元素，它仍然需要 O(1) 来获得对它来说，只是稍微大一点的常数。只有当检索以某种方式取决于列表中元素的总数时，复杂性才会受到影响，这将是非常尴尬的场景。可能，但很尴尬。例如，考虑下一个元素地址不是由下一个指针给出的，而是在某个内存位置加密的，为了检索它，您需要应用解密算法 k 次，当 k 是列表到当前元素的长度。在此示例中，单跳的价格确实取决于列表长度，并且总复杂度会增加。
注意：这里假设物理机没有内存限制（否则讨论复杂性根本没有意义，因为所有算法都需要O(1)时间）
大家都知道，遍历一个长度为n的列表，时间复杂度为O(n)。这是因为假定从列表的一个元素到下一个元素的每一步都在 O(1) 时间内完成。如果我知道我需要存储的最长列表的长度最多为 4，那么如果可以的话，我会安排每个元素都存储在一个寄存器中，其中一个 2 位地址为 00、01、10、或 11. 那么读取正确地址并到达那里的任务只需要知道几位。 但是，我一直在想，如果一个列表的长度类似于 2^100，那么指针的使用就会变慢。看来要区分列表中两个不同元素的寄存器，处理器必须首先消化 100 位地址信息，然后才能知道接下来要处理哪个寄存器。这将使每个步骤的时间需求更像 Theta(log n)，而完整遍历的时间需求为 O(nlog(n)).
你完全正确。如果有人说遍历一个列表 if O(n)，那是基于这样的假设，即你可以在常数时间内从一个元素到达下一个元素。如果你改变这些假设，你可能会得到不同的时间复杂度。
当人们陈述算法的时间复杂度并将其用于讨论在真实计算机上的执行时，通常会掩盖以下事实：
在真实的物理计算机上，不同可能输入的数量总是有限的，所以计算机实际上是一个有限状态机（而不是图灵机），每个算法的复杂度都是O( 1), 严格来说（可能有一个相当大的常数因子！）。但是我们推断这个有限状态机来推断它的行为，就好像它不是有限的一样。
在您的示例中，列表遍历算法的可能输入的有限数量（实际上）受 CPU（例如 64 位）的字长限制，并且您不能拥有长度列表2^100（使用通常的 pointer-based 算法）。所以严格来说，在 64 位 CPU 上遍历列表的复杂度是 O(1)，但它 在可能的输入范围内表现得像 O(n) .对于超出该范围的输入，外推会失效。 所有算法在真实物理计算机上运行都是如此。
您混淆了不同的术语。
n指的是列表中的元素个数。
从一个元素移动到下一个元素的时间确实通常被认为是 O(1)。
non-trivial地址解析的例子对整体复杂度没有影响，只要地址解析受常数限制即可。所以即使列表中有 2100 个元素并且 CPU 必须执行几个额外的操作来检索下一个元素，它仍然需要 O(1) 来获得对它来说，只是稍微大一点的常数。只有当检索以某种方式取决于列表中元素的总数时，复杂性才会受到影响，这将是非常尴尬的场景。可能，但很尴尬。例如，考虑下一个元素地址不是由下一个指针给出的，而是在某个内存位置加密的，为了检索它，您需要应用解密算法 k 次，当 k 是列表到当前元素的长度。在此示例中，单跳的价格确实取决于列表长度，并且总复杂度会增加。
注意：这里假设物理机没有内存限制（否则讨论复杂性根本没有意义，因为所有算法都需要O(1)时间）