我發現這個大O符號計算，哪一個是正確的兩個答案

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/2第二環路將不被執行將被O（N）次中執行* n次。但我也可以說第一個循環執行O（n）次，第二個執行O（n）次，因此它是O（n^2）。我現在很混亂，哪一個是對的？

Answer 1

內循環將只啓動一次，最後一個值爲i。所以你不能說「對於外部循環的每次迭代，我們運行內部循環」。相反，你可以說，「對於外循環的每次迭代，它的主體運行在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];對於i的每個值在0和n-1之間將只執行一次。所以，雖然代碼看起來很混亂，但它是O（n）。