は大きく異なりますか？

Question

これらの2つの異なるコード（同じことをやっている）では、bigOが異なっています。 O（1）文は変更されますが、for-loopsは同じ数、つまり同じ実行数に留まりますか？

for (i=0;i<n;i++) { 
    for (j=0;j<i;j++) { 
     b+=i+i 
    } 
    } 

そして、次の時間を実行している

 for (i=0;i<n;i++) { 
     int k = i+i; 
     for (j=0;j<i;j++) { 
      b+=k; 
     } 
     } 

ありえないコードの両方？

Answer 1

これらは同じ複雑さを持っています（O(n^2)）。

の両方が同じ構造を有する：全体的な複雑さをカウントするために

for (i=0;i<n;i++) { 
    // some constant amount of steps (without changing i or n), say p steps 
    for (j=0;j<i;j++) { 
     // another constant amount of steps (without changing i or j), say q steps 
    } 
} 

を、のは、一つ一つのステップをカウントしてみましょう：

合計、 p*n + q*n*(n-1)/2段階で

i = 0, so p steps on this stage 
i = 1, j from 0 to 0, so (p + q) steps on this stage 
... 
i = k, j from 0 to k-1, so (p + q*k) steps on this stage 
... 
i = n-1, j from 0 to n-1, so (p + q*(n-1)) steps on this stage 

、またはO(n^2)中BigO表記