時間複雑

Question

申し訳

for (int i=0; i<n; i++) { 
    for (int j=0; j<i; j++) { 
     do stuff... 
    } 
} 

は、このコードn^2またはnlognの複雑さですか？ ありがとう

Answer 1

複雑さはO(n^2)です。

外側ループの最初の反復のために、内側ループは、外側ループの2回目の反復について0回

を反復し、内部ループは1回反復します。

外側ループの3番目の反復では、内部ループは2回繰り返されます。外側のループのn番目の反復について

.........

、インナーループがn - 1回反復します。

反復の総数= 0 + 1 + 2 + 3 + 4 ...... + (n - 1)

私たちが知っている、算術級数

1 + 2 + 3 + ..... + (n - 2) + (n - 1) + n = (n * (n + 1))/2 

ので、

0 + 1 + 2 + 3 + 4 ...... + (n - 1) 
= (n * (n - 1))/2 
~ n^2 

は一定の時間で実行されますdo stuff相を考慮するとの合計で、全体的な時間複雑度はO(n^2)です。