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

Question

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

据我了解，第一行是操作，第二行是(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​​是主要的增长项，因此如果我们忽略它的常数因素，我们会得到 O(N ² ) 的运行时间。

不要把这个答案看作是你应该记住的东西——想想得到答案所需的所有步骤。我们首先找到一些要计数的数量，然后查看该数量如何受到循环执行的影响。由此，我们能够推导出该数量的数学表达式，然后我们对其进行简化。最后，我们采用得到的表达式并确定主导项，它作为整个函数的大 O。

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 ² )。

Answer 3

它不是附加的：内循环在外循环的每次迭代中发生一次。所以它是 O(n ² )。

顺便说一句，这是一个很好的例子，说明了为什么我们对这类事情使用渐近符号——根据“操作”的定义，计数的确切细节可能会有很大差异。（例如，是sum++单个操作，还是add sum to 1 giving temp; load temp to sum？）但是由于我们知道所有可以隐藏在常数因子中的东西，它仍然是 O(n ² )。

Answer 4

不; 您不计算每行的特定操作次数，然后将它们相加。像“for”这样的结构的全部意义在于使给定的代码行可以多次运行。您应该使用思维和逻辑技能来计算“sum++”行将运行多少次，作为 N 的函数。提示：每次遇到第三行时它运行一次。

第二行遇到多少次？

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

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

哪条线最常出现？以 N 计，它多久发生一次？

Answer 5

所以猜猜你对 sum++ 有什么兴趣，以及你执行了多少次。

总和的最终统计数据将为您提供答案。

实际上你的循环只是：

Sigma(n) n 从 1 变为 N。

等于：N*(N+1) / 2这给了你大符号O(N^2)

此外，除了您的问题名称之外，您的算法中没有最坏的情况。或者你可以说最坏的情况是 N 趋于无穷大。

Answer 6

使用 Sigma 符号表示您的循环：