为什么链表（单链表）的时间复杂度不是n-1？
Why the time complexity of linked list ( single linked list ) isn't n-1?
我的观点是，当指针在链表中遍历到n-1位置时，他很容易得到nth的值，因为正如我们所知，nth pointer 的地址位于第 n-1 个位置。因此，时间复杂度必须是 n-1 而不是 n.
任何 Big O 表示法总是描述 upper 边界。这意味着虽然 n-1 描述复杂性会更准确，但它仍然包含在 O(n).
中
其次，在描述大 O 复杂性 class 时，任何常数因子 (-1) 都会从等式中减少，因为对于任何体面的大 n，任何常数因子对结果。
与删除 n 的任何常数因子相同。 O(3n+5) 与 O(n).
的复杂性相同 class
这两者的结合是您将复杂性描述为 O(n) 而不是 O(n-1) 的原因，尽管它在技术上可能仍然是正确的并且更准确。
我的观点是，当指针在链表中遍历到n-1位置时，他很容易得到nth的值，因为正如我们所知，nth pointer 的地址位于第 n-1 个位置。因此，时间复杂度必须是 n-1 而不是 n.
任何 Big O 表示法总是描述 upper 边界。这意味着虽然 n-1 描述复杂性会更准确，但它仍然包含在 O(n).
中
其次，在描述大 O 复杂性 class 时，任何常数因子 (-1) 都会从等式中减少，因为对于任何体面的大 n，任何常数因子对结果。
与删除 n 的任何常数因子相同。 O(3n+5) 与 O(n).
这两者的结合是您将复杂性描述为 O(n) 而不是 O(n-1) 的原因，尽管它在技术上可能仍然是正确的并且更准确。