whileループの時間複雑度（Big O）はどのようにして確認できますか？

Question

コード1

int i = 0; 
int j = 0; 
while(i < n){ 
    while(j < n){ 
     printf("{%d,%d}",arr[i],arr[j]); 
     j++; 
    } 
    i++; 
    j = 0; 
    printf("\n"); 
} 

コード2

int result = 0; 
int i = 0; 
while (i < n/2){ 
    result += arr[i]; 
    i += 1; 
    while (i >= n/2 && i < n){ 
     result += arr[i]; 
     i += 1; 
    } 
} 
printf("%d\n", result); 

私はforループで時間の複雑さを見つける方法を知っているが、私は、whileループについて確信がもてません。 誰かが各コードの合計実行時間を見つけるのを手伝ってくれたら大いに感謝します。

Answer 1

最初のコードサンプルは、かなりループのClassisです。その複雑さはO（n^2）です。これは、内部ループが複雑さO（n）を有し、それがn回実行されるためである。

もう一つは、少し困難であるあなたは、その複雑さを意味

int result = 0; 
int i = 0; 
while (i < n){ 
    result += arr[i]; 
    i += 1; 
} 
printf("%d\n", result); 

（n）はO

ある（小切手の複雑さを無視する）ことがないネストされたループに相当する参照刚性

時間の複雑さを計算する最善の方法は、アルゴリズムの仕組みを理解し、操作を数えることです。 2番目の例では、内側ループは、外側ループが最後の繰り返しになるまで実行されません。同じコードを実行することさえあるので、全体を1つのループに減らすことができます。

もう一つの良い例はこれです：

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

の操作をカウントしてみましょう：+ 2 1 + 3 + 4 + ... + N。これはn * n/2になり、O（n^2）につながります。

Answer 2

ループの終わりには、whileループです。フォームの何かが：

for(int i=0; i<n; i++) 

のと同等です。

あなたがあなたのアルゴリズムでwhileループの中にループのいずれかを作ることになっているアルゴリズムの純粋な数学的解析で実際に

int i=0; 

while(i<n) 
{ 
i++; 
} 

（がありますカップルの理由）。

コードに戻ってください。解析は単純です：

-前回のwhileループの繰り返しの前に、iの値は0です。 - 変数i（i ++）を更新する一意の文が存在します。 - 外側のループiのすべての反復が1だけ増加します。 - 外側のループは最大でn回実行されます。私たちは内側のループのいずれかの反復の前に値を伝えることができます：

任意のループの繰り返し-before jの値が0 -Thereでは-Informally更新J（J = 0とj ++） という2文ですjの値は0です。 - 内部ループの内側で、jを更新する文はj ++です。 - 内側ループjのすべての反復で1を増加させます。 - 内側ループはループガードによって最大n回実行されます。

- 外側ループは最大でn回実行され、内側ループは外側ループの繰り返しごとに最大n回実行されます。その他のステートメントはすべて定数です。アルゴリズムはO（N×n個）= O（N^2）

にあるもう一つはやや入り組んだが：

外側ループの最初の反復-before iの値が0です。 -Informally：iの値になるまで、外側ループは、（N/2 - 1の）実行さ-Informally iが（N/2）に -The UPDATE文を（I + = 1）更新 ：内部ループ実行（ nn/2 = n/2回）、正確に1回実行されます。 -The外側ループは、内側ループは一度だけのN/2回実行し、N/2回実行されます。

アルゴリズムは、したがって、O（N/2 + N/2）= O（N）回