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 回ということです。つまり、1 から n までの数の合計は n(n+1)/2 回です。(制限が 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)