条件付きループの実行時間（ステップ数）

Question

実行時間を入力サイズNで特定する方法がわかりません。これが私が試みたことです。私は定数が正しいと推測しています。どのように見えるのですか？

i = 1;        //1 
k = n;        //1 
while (i <= k) {      //N+1 
    while (i <= k && A[i] < 0) {  //i+2 
     i = i + 1;     //2i 
    } 
    while (i <= k && A[k] >= 0) {  //i+2 
     k = k - 1;     //2i 
    } 
    printf("...");     //1 
    i = i + 1;      //1 
    k = k - 1;      //1 
} 

Answer 1

これは、両端からキャンドルを焼くこととして知られています。 iとkはどこかの中間で出会うが、アレイの各要素は1回だけ訪れる。したがって実行時間はO（n）です。

外側のwhileループはプロセスが完了するのを待っているだけなので、実行時間の計算は考慮されません。最初の内側のwhileループは、詰まるまでiを右に移動します。 2番目の内側のwhileループは、詰まるまでkを左に移動します。

ライン彼らは捕まってしまったポイント過去

i = i + 1; 
k = k - 1; 

移動iとk。

iが配列要素の一部を訪問し、kが他の配列要素を訪問しますが、配列の各要素は1回だけ訪問されます。