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 = i+1 to k为j = 1 to k?

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