嵌套for循环的运行时间

Question

1a.)循环在下面,我想找到它的运行时间.这是循环

sum = 0
for (int i =0; i < N; i++){
    for(int j = i; j >= 0; j--)
          sum ++

第一个for循环在O(n)中运行很容易,但对于第二个我认为它也在O(n)时间运行,因为无论何时j = i,这个循环将运行i次.

所以我写下了它的运行时间为O(n ^ 2).

1B.)此外,当有问题要求"theta界限"时,有人还可以解释是什么意思吗？

Answer 1

好吧,在这里计算出确切的循环迭代次数非常简单.你得到1 + 2 + 3 + 4 + 5 + 6 + 7 + ... + N.

总和为N(N + 1)/ 2,所以是的,算法复杂度为O(N ²).

我不能说我遇到了这个界限......但是关于big-O表示法的维基百科页面提到了它,所以这可能是一个合理的起点.