math - 计算循环的总次数

Question

我正在尝试计算执行最里面的语句的总次数。

count = 0;
for i = 1 to n
    for j = 1 to n - i
       count = count + 1

我认为循环最多可以执行 O(n*ni) = O(n^2)。我想通过使用双重求和来证明这一点，但我迷路了，因为我无法启动等式，因为 j = 1 被投入其中。

有人可以帮我解释一下吗？

谢谢

Answer 1

对于 each i，内部循环执行n - i次数（n是常数）。因此（因为i范围从1到n），要确定执行最里面的语句的总次数，我们必须评估总和

(n - 1) + (n - 2) + (n - 3) + ... + (n - n)

通过重新排列术语（将首先出现的所有 s 分组n），我们可以看到这等于

n*n - (1 + 2 + 3 + ... + n) = n*n - n(n+1)/2 = n*(n-1)/2 = n*n/2 - n/2

---

这是 Python 中的一个简单实现来验证这一点：

def f(n):
    count = 0;
    for i in range(1, n + 1):
        for _ in range(1, n - i + 1):
            count = count + 1
    return count

for n in range(1,11):
    print n, '\t', f(n), '\t', n*n/2 - n/2

输出：

1 0 0
2 1 1
3 3 3
4 6 6
5 10 10
6 15 15
7 21 21
8 28 28
9 36 36
10 45 45

第一列是n，第二列是内部语句的执行次数，第三列是n*n/2 - n/2。