for-loop - for循环的运行时间

Question

这个大 O 表示法的嵌套 for 循环的运行时间是多少？

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

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

Answer 1

您的问题与级数和 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)。