数组的时间复杂度分析

Question

我有时会对包含数组的代码的时间复杂度分析感到困惑。例如：

    ans = [0] * n
    for x in range(1, n):
        ans[x] = ans[x-1] + 1

我认为 for 循环的时间复杂度为 O(n^2)，因为它访问数组中有 n 个元素的元素，并且重复同样的事情 n 次。

然而，我看到一些解释说它只需要 O(n)；因此，我的问题是：当我们分析访问数组元素（不一定是第一个或最后一个元素）的程序的时间复杂度时，我们应该包括访问这些数组元素的时间，还是经常被忽略？

Answer 1

索引访问通常是 constant-time 操作，因为在大多数实际情况下 random access 内存可用。如果你要运行这个例如在Python中测量n的不同取值所花费的时间，你会发现是这样的

因此，你的代码只执行一次从1到n的循环，其他所有操作都是constant-time，所以你得到 O(n).

的时间复杂度

您的想法在其他方面是正确的 - 如果这是一个链表并且您必须遍历它以找到您的值，那么它将是 O(n²).

Answer 2

time complexity

Time comlexity analysis for arrays