c++ - increment 会执行多少次？

Question

我有以下代码

    int cnt = 0;
    for (int i = 0; i < N; ++i)
    {
        for (int j = i + 1; j < N; ++j)
        {
           if(a[i] + a[j] == 0)
           { ++cnt;}
        }
    }

其中 N 是数组中元素的数量。

我开始学习算法，我试图找出增量将被执行多少次？

对于 i 它将是 N 次。

对于 j 当 i = 0 时它将是 N-1 次，当 N-2 时 i = 1 等 所以 N-1 + N-2 + ... + 0 = ((0 + N-1)/2)*N = N*(N-1)/2

那么cnt++会被执行多少次呢？

要回答这个问题，我们需要找出 == 将被执行多少次？当然会在范围内。从 0 到某个值。我们的最终答案将在从 0 + number of(++i) + number of(++j) 到 some value + number of(++i) + number 的范围内的(++j)。

让我们找到这个一些值

i=0时为1...N-1，时为2...N-2 i=1 等 所以 N-1 + N-2 + ... + 0 = N*(N-1)/2

所以答案将从 N*(N-1)/2 到 N + N(N-1)/2 + N(N-1)/2，所以从 N*(N-1)/2 到 N^2

但 R.Sedgwick 在第 33 张幻灯片中说 http://www.cs.princeton.edu/courses/archive/spring15/cos226/lectures/14AnalysisOfAlgorithms.pdf

答案将从 N*(N+1)/2 到 N^2

为什么？我错了吗？在哪里？

Answer 1

内部循环(== 测试)确实执行了 N(N-1)/2 次。

因此，增量 (++cnt) 可能会在 0 和 N(N-1)/2 之间执行.

可以达到这两个边界:0 当所有 a[k] > 0 和 N(N-1)/2当所有 a[k] == 0 时。

---

对于增量的总数，为外部 for 循环添加 N 为内部添加 N(N-1)/2 for 循环，并在 N(N+1)/2 和 N² 之间获取。