この機能の複雑さは何ですか？

Question

私はインタビューでこのような解決策を常に提供していますが、複雑さはO（n^2）、O（nlogn）はわかりません。

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

Answer 1

外部ループは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（N^2）であるコードO(n2)

Answer 2

のこの作品の複雑さを作るO(limit) * O(limit-1) * O(limit-2)*..*O(1)の複雑さを与えます。なぜ、演繹的な方法でこれを簡単な方法で分析しましょう。

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) 

Answer 3

ちょうど私が5ゼロから行くことができ、今6としての限界を取る、理解し、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）です。