このアルゴリズムの実行時間T（n）はどれくらいですか？

Question

このアルゴリズムを実装しているプログラムの実行時間T（n）はどれですか？ - 合計時間とは何ですか？

T（n）≈cop C（n）。

sum = 0; 
for (i=1; i<=n; i++) 
    for (j=1; j<=i; j++) 
     sum++; 
for (k=0; k<n; k++) 
    A[k] = k; 

Answer 1

ネスト

for (i=1; i<=n; i++) 
    for (j=1; j<=i; j++) 
     sum++; 

ループ

n   - outer loop 
    (n + 1)/2 - inner loop 

    n * (n + 1)/2 == 0.5 * (n^2 + n) == O(n^2) 

操作をもたらします。あなたはより良いO(n)ルーチンを実装できます。

sum = n > 0 ? n * (n + 1)/2 : 0; 

    for (k = 0; k < n; k++) 
    A[k] = k; 

Answer 2

あなたは命令にsum++;n(n+1)/2回と指示A[k]=k;n倍に達します。

合計はT(n)=(n^2+3n)/2となります。

Answer 3

あなたは、正確な分析が必要な場合、それは（私たちが出て内側から開始する必要があります）、次のようになります：C1、C2は定数である

。