代碼片段的複雜性

Question

for(int i = 0; i < N; i++) 
    if(i < 2 || i > N - 3) 
    for(int j = 1; j <= 10N; j++) 
     a[i] = a[j - 1]/2; 

那麼答案是N(1 + 10N(1)) = n + 10n^2對不對？或者是n？ 請解釋。

Answer 1

如果你想要一個漸近上界... O（n^2）。如果你想要比那更挑剔，我們需要爲單個指令定義計算權重。

編輯：是的，它是O（n）。我第一次讀錯了。

Answer 2

這看起來O(N)給我。

if陳述對於i = 0,1,N-1,N-2是正確的，這是一個恆定數量的情況。

Answer 3

你的結論是錯誤的。雖然外部for環N次，if條件僅在4個案例（0,1,N -2，N -1）中成立。因此總運行時間爲N + 4·10·N即O（n）。