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