確定這些循環的Big-O運行時間

Question

我正在嘗試確定這些循環的Big-O運行時間。我相信我的答案是正確的，但我想與社區覈對。

int sum = 0; 
for (int i = 1; i <= n*2; i++) 
    sum++; 

我的回答是O（n）

這是因爲循環迭代的N×2倍。我們放棄2，並留下n。因此O（n）。

int sum = 0; 
for (int i = 1; i <= n; i++) 
    for (int j = n; j > 0; j /= 2) 
     sum++; 

我的回答是O（n LGN）

外循環迭代n次。內循環從n重複爲0，但只能通過一半的項目。這可以看作是n的Log base 2。我們放下2並保持記錄n。內循環（log n）乘以外循環（n），給我們O（n lgn）。

int sum = 0; 
for (int i = 1; i <= n; i++) 
    for (int j = i; j <= n; j += 2) 
     sum++; 

我的回答是O（n^2）

這一個是容易的。內循環和外循環每次迭代n次。 n x n = n^2。因此O（n^2）。

int sum = 0; 
for (int i = 1; i <= n * n; i++) 
    for (int j = 1; j < i; j++) 
     sum++; 

我的回答是O（n^3）

是我的答案是否正確？如果不是，我該如何糾正它們？

Answer 1

只有最後一個是錯誤的。它應該是O（n 4）。

你可以這樣看：用x代替n * n。操作次數將是通常的O（x *（x + 1）/ 2）= O（x 2）。現在用n * n替換回x。

---

對你來說是額外的挑戰。

你正確地說：

int sum = 0; 
for (int i = 1; i <= n; i++) 
    for (int j = n; j > 0; j /= 2) 
     sum++; 

是O（n log n）的。但對於這一個：

int sum = 0; 
for (int i = 1; i <= n; i++) 
    for (int j = i; j > 0; j /= 2) 
     sum++; 

我只改j = n到j = i。