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，i=5 j=5

因此，程序的“做某事”部分运行 5、4、3、2 和 1 次。这意味着limit = 6总共有15次。或n（n + 1）/ 2次，因为从1到n的数字之和就是这样。（假设极限由 n 表示）。

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

Answer 2

让我们分析一下。外循环将运行limit时间。

First iteration of outer loop, i=0.. Inner loop runs limit times..
Second iteration of outer loop, i=1.. Inner loop runs limit-1 times.. 
.
.
.
.
Limit-th iteration of outer loop, i=limit-1.. Inner loop runs 1 time.. 

这给了我们一个复杂性，O(limit) * O(limit-1) * O(limit-2)*..*O(1)这反过来又使这段代码的复杂性O(n2)

Answer 3

这种复杂度当然是 O(N^2)。为什么，让我们用演绎的方式简单地分析一下。

    Limit = 10, the iterations are = 10 + 9 + 8 + 7 + ... + 1 = 10*(10+1) / 2
    Limit = 20, the iterations are = 20 + 19 + 18 + ... + 1 = 20*(20+1) / 2
    .
    .
    .
    Limit = N, the iterations are = N + N-1 + N-2 + ... + 1 = (N)(N+1)/2 
    In big-Oh notation, its complexity is O( (N)(N+1)/2 ) = O( (N^2 + N) / 2 ) which gives O(N^2)