如何计算该算法的最坏情况分析？

Question

sum = 0;
for(int i = 0; i < N; i++)
    for(int j = i; j >= 0; j--)
       sum++;

据我了解，第一行是1个操作，第二行是(i+1)个操作，第三行是(i-1)个操作，第四行是n个操作。这是否意味着运行时间将是1 + (i+1)(i-1) + n？只是最后几步让我感到困惑。

- user595334

---

你需要根据N来计算复杂度，而不是循环计数器。 - thkala

Answer 1

要分析算法，你不需要逐行询问“这一行贡献了多少时间”，因为每一行执行的次数不同。例如，与第一行只运行一次相比，最内层的行被执行了很多次。

要分析这样的算法，尝试确定某个数量，其值在总运行时间的常数因子范围内。在这种情况下，这个数量可能是“sum ++这一行被执行的次数”，因为如果我们知道这个值，我们就知道算法中两个循环所花费的总时间。为了弄清楚这一点，让我们追踪一下这些循环发生了什么。在外部循环的第一次迭代中，i == 0，所以内部循环将恰好执行一次（从0到0倒计时）。在外部循环的第二次迭代中，i == 1，内部循环执行两次（首先是j == 1，然后是j == 0）。更一般地说，在外部循环的第k次迭代中，内部循环执行k + 1次。这意味着最内层循环的总迭代次数由以下公式给出：

1 + 2 + 3 + ... + N

这个数量可以被证明等于：

N (N + 1)      N^2 + N    N^2    N
---------   =  ------- =  --- + ---
    2             2        2     2

这两个术语中，N^2 / 2 是支配增长项，因此如果我们忽略其常数因子，就会得到 O(N²) 的运行时间。

不要将此答案视为您应该记住的东西 - 考虑获得答案所需的所有步骤。我们首先找到了一些需要计数的量，然后看到循环执行如何影响该数量。从这里，我们能够推导出该数量的数学表达式，然后进行简化。最后，我们取得的结果表达式确定了支配项，从而作为整个函数的大O。

- templatetypedef

Answer 2

从内而外工作。

sum++

这是一个单独的操作，不会重复。

for(int j = i; j >= 0; j--)

这个循环执行了i+1次。其中有几个操作，但你可能不需要计算asm指令的数量。因此，在这个问题中，我假设它是i+1的乘数。由于循环内容是单个操作，所以循环和其块执行了i+1个操作。

for(int i = 0; i < N; i++)

这个循环运行了N次。所以和之前一样，这是N的乘数。由于该块执行i+1次操作，因此该循环总共执行N(N+1)/2次操作。这就是答案！如果你想考虑大O复杂度，那么这可以简化为O(N²)。

- moinudin

Answer 3

它不是可加的：内部循环对于外部循环的每次迭代都会发生一次。因此，它是O(n²)。

顺便说一下，这是为什么我们使用渐近符号表示这种情况的好例子——根据“操作”的定义，计数的确切细节可能会有相当大的差异。（例如，sum++ 是单个操作，还是 将 sum 加 1 并将结果存储到 temp 中；将 temp 加载到 sum 中？）但由于我们知道所有这些可以隐藏在一个常数因子中，所以它仍然是O(n²)。

- Charlie Martin

Answer 4

不，你不能为每行计算特定数量的操作然后将它们累加。像“for”这样的结构的整个意义在于使给定的代码行能够运行多次。你应该使用思维和逻辑技巧来确定“sum ++”这一行将以N的函数运行多少次。提示：它会在第三行被遇到的每一次运行一次。

第二行会遇到多少次？

每当第二行被遇到时，“i”的值都会被设置。第三行会运行多少次以该值？因此，它会运行多少次？（提示：如果我在几个不同的场合给了你不同金额的钱，你如何找出我总共给了你多少钱？）

每当第三行被遇到时，第四行会发生一次。

哪一行发生最频繁？它在N方面有多频繁？

- Karl Knechtel

Answer 5

所以你感兴趣的是sum++以及它被执行的次数。

最终的sum状态将给出你答案。

实际上，你的循环只是：

Sigma(n) n从1到N。

这等于：N*(N+1) / 2 这在大O符号表示法中为O(N^2)

此外，在你的算法中没有最坏情况的名称。

或者你可以说最坏情况是当N趋近于无穷大时。

- mathk

Answer 6

使用Sigma符号来表示循环：

- Mohamed Ennahdi El Idrissi