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