1a。）循環在下面，我想找到它的運行時間。這裏是循環嵌套for循環的運行時間
sum = 0
for (int i =0; i < N; i++){
for(int j = i; j >= 0; j--)
sum ++
第一個for循環運行在爲O（n），這是容易的，但是，對於第二，我認爲它也運行在O（n）的時間，因爲每當j = i，這個循環將運行我的時間。
所以我寫下這有一個運行時間O（n^2）。
1b。 ）另外，有人可以解釋什麼是指什麼，當一個問題要求「theta bound」？
好吧，這裏計算循環迭代的確切次數非常簡單。你得到1 + 2 + 3 + 4 + 5 + 6 + 7 + ... + N.
即總計爲N（N + 1）/ 2，所以是的，算法的複雜性是O（N 2 ）。
我不能說我碰到了theta界限... Wikipedia page on big-O notation雖然提到它，所以這可能是合理的開始點。
那麼內循環的迭代次數也是外循環的迭代次數是否正確？ – 2011-01-23 21:29:28
@ user373466：不，外層循環只執行N次......但它沒有做任何額外的工作。 – 2011-01-24 06:24:42
f(n) = O(g(n))當且僅當足夠大n存在一個常數c這樣f(n) <= c*g(n)。基本上，大O符號給你一個上限。你可以說你的程序運行在O(n^3)，O(n^2011)，甚至O(n^42142342)，但這些對你來說沒有太大的幫助，對嗎？
Theta notation給你一個緊約束，這是更有幫助。 f(n) = Theta(g(n))當且僅當足夠大n存在常數c1, c2，使得c1*g(n) <= f(n) <= c2*g(n)，這意味着你知道你的算法正比於的確切函數。
您的算法確實有1 + 2 + 3 + ... + N的操作，其總和爲N(N+1)/2。這是Theta(N^2)，因爲N^2/4 + N/4 <= N^2/2 + N/2 <= N^2 + N。所以你可以把c1和c2定義爲1/2和2。
大多數時候人們會用大O符號來表達一個緊密的界限，但這不是必需的。當被問及函數的大O時，總會有多個答案，但是當被問到theta函數時只有一個答案。
Theta bound意味着它是一個緊密的漸近界，它限制了從上面和下面的運行時間。在你的例子中，N^2既是運行時間的上下界，也是運行時間的界限。
更正式：
存在k1和k2爲使得：
N^2 * K1 < = N（N + 1）/ 2 < = N^2 * K2
爲N>一些值N0。
Ps。本書給出了對不同漸近界的相當好的解釋：http://www.amazon.com/Introduction-Algorithms-Third-Thomas-Cormen/dp/0262033844/ref=sr_1_1?ie=UTF8&qid=1295777605&sr=8-1
作業問題！閱讀你的課本。 – Neo 2011-01-23 09:59:31