for循环的运行时

Question

在大O符号中，这个嵌套的for循环的运行时是什么？

for(i = 1 to k)
{
    for(j = i+1 to k)
    {}
}

它比O(k^2)小，但我算不出来。

Answer 1

你的问题与级数sum S(k) =0+1+2+ ... + (k-2) + (k-1)密切相关。证明了S(k) = (k*(k-1))/2 = (k*k)/2 - k/2。将和重新排序为S(k) = {0+(k-1)} + {1+(k-2)} + {2+(k-3)} + ....这说明了如何实现。

因此，算法的阶数是否小于O(k*k)？请记住，像1/2这样的常数系数不会影响大O记法。

问:所以它相当于用j = 1 to k替换了j = i+1 to k

回答:对。这很棘手，所以让我们仔细考虑一下。对于i == 1，内部循环的操作运行了多少次？答:它运行k-1次。同样，对于i == 2，内部循环的操作运行了多少次？答:它运行k-2次。最终，对于i == k，内部循环的操作运行了多少次？答案:它运行零次。因此，对于i的所有值，内部循环的操作运行了多少次？答案是：(k-1) + (k-2) + ... + 0，它就是前面提到的和S(k)。