大O和T（N）混淆

Question

我目前正在做一些關於大O和T（N）的作業，並且遇到過幾個問題。我插入了像教授所說的數字，並提出每個循環運行多少次，但我無法弄清楚如何從這些信息中推導出T（n）和Big O.我看過整個網站，但似乎無法找到任何幫助。這些是一些未分配的問題，但與我正在努力解決的問題非常相似。

如果你可以一步一步地找出如何去尋找Big O和T（n），那會非常有幫助。謝謝你的時間。

for (int i = 0; i < n; i++) 
for (int j = 0; j < i * i; j++) 
cout << j << endl; 

i=1 runs 1 time 
i=2 runs 4 times 
i=3 runs 9 times 
i=4 runs 16 times 

for (int i = n; i >= 0; i -= 2) 
cout << i << endl; 

n=10 runs 6 times 
n=8 runs 5 times 
n=6 runs 4 times 
n=4 runs 3 times 
n=2 runs 2 times 

for (int i = 0; i < n; i++) 
for (int j = i; j > 0; j /= 2) 
cout << j << endl; 

i=16 runs 5 times 
i=8 runs 4 times 
i=4 runs 3 times 
i=2 runs 2 times 

Answer 1

這些都是非常簡單的情況，你所要做的就是計算迭代次數。

讓我們第一個：

for (int i = 0; i < n; i++) 
for (int j = 0; j < i * i; j++) 
    cout << j << endl; 

對於i一個特定的值，我們做的內循環的i^2迭代。因此，最內層步驟的迭代總次數爲：

0^2 + 1^2 + 2^2 + ... + (n-1)^2 
= (n-1)(n)(2n-1)/6 // it helps to just know the formula for sums of squares 
= Ө(n^3)   // just drop all the constants 

只需按照其他兩個相同的方法。第二個是微不足道的（Ө(n)），雖然第三個稍微有趣（O(n lg n)）。