algorithm - 这个函数的复杂度是多少？

Question

我在面试中总是提供这样的解决方案，但我不确定 O(n^2)、O(nlogn) 的复杂度是多少？

for(i = 0; i < limit; i++)
{
    for(j = i; j < limit; j++)
    {
        // do something
    }
}

Answer 1

只是为了理解，将 limit 设为 6。现在，i 可以从 0 到 5，j 可以从 i 到 5。当 i=0 j=0 到 5 时， i=1 j=1 到 5, i=2 j=2 到 5, i=3 j=3 到 5, i=4 j=4 到 5, 我=5 j=5

因此，程序的“做某事”部分运行了 5、4、3、2 和 1 次。这意味着 limit = 6 总共有 15 次。或者说 n(n+1)/2 次是从 1 到 n 的数字总和。(假设limit用n表示)。

我看到它并不完全是 n^2 复杂度，但随着 n 变大，n^2 项将占主导地位。因此在我看来它是 O(n^2)。