這兩個嵌套for循環的時間複雜度是多少？

Question

我發現這段代碼的時間複雜度是O（N ）。這樣對嗎？

for(i=n;i>=1;i--) { 
    for(j=n-i; j>=1; j--) { 
    x++; 
    } 
} 

Answer 1

是的，這是爲O（n ）。

外循環將執行n次。內循環平均執行n/2次。將內部循環和外部循環的複雜度相乘得到O(n * n/2)，即O（n ）。