大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)）。