algorithm - 时间复杂度是多少？

Question

以下函数的时间复杂度是多少？

    for(int i = 0; i < a.size; i++) {
        for(int j = i; j < a.size; i++) {
            //
        }
    }

我认为它小于 big O n^2，因为我们没有在第二个 for 循环中迭代所有元素。我相信时间复杂度是这样的:

n[ (n) + (n-1) + (n-2) + ... + (n-n) ]

但是当我解决这个公式时，结果是

n^2 - n + n^2 - 2n + n^2 - 3n + ... + n^2 - n^2

这似乎根本不正确。谁能确切地告诉我如何解决这个问题，以及我哪里错了。

Answer 1

即 O(n^2)。如果您考虑 i = a.size() - 1 的迭代，并且您向后工作(i = a.size() - 2， i = a.size - 3 等)，您正在查看以下迭代次数总和，其中 n = a.size。

1 + 2 + 3 + 4 + ... + n

这个级数的和是n(n+1)/2，也就是O(n^2)。请注意，大 O 表示法在应用于多项式函数时会忽略常量并采用最高的多项式幂。