は、私は1つが正しいこのビッグO記法計算の2つの答えを見つけた

Question

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); 

なお、第1のループは1/2実行されるまで、第2のループが実行されないので、O（N）回実行されるように思えます* n回。しかし、最初のループはO（n）回実行し、2回目はO（n）回実行してO（n^2）と言うこともできます。今私は混乱していますが、どちらが正しいですか？

Answer 1

内部ループは、最後の値がiの間、1回だけ開始されます。だから、「外側のループの繰り返しごとに内側のループを実行する」と言うことはできません。代わりに、 "外側ループの繰り返しごとに、本体がO（1）、（O（n）で実行される最後の反復の場合はを除く）で実行されます"と言うことができます。したがって、合計時間はO（n）* O（1）+ 1 * O（n）= O（n）です。

また、何かがO（n）で実行されている場合、それは正確にではありません。でもO（n^2）で実行されます。 O（n）は厳密な境界に過ぎず、通常、可能な上限を得ることが期待されます。

Answer 2

result += arr[i];は、0からn-1までのiの値ごとに1回だけ実行されることに気付くことをお勧めします。したがって、コードは混乱しているように見えますが、O（n）です。