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

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？只是最后这些步骤让我感到困惑。

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 term 是主要的增长项，因此如果我们忽略它的常数因子，我们得到的运行时间为 O(N²)。

不要将此答案视为您应该记住的东西 - 想一想获得答案所需的所有步骤。我们首先找到一些要计算的数量，然后了解该数量如何受到循环执行的影响。由此，我们能够推导出该数量的数学表达式，然后对其进行简化。最后，我们采用生成的表达式并确定主导项，作为整体函数的大 O。