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

Question

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

据我所知,第一行是1次操作,第2行是(i+1)操作,第3行是(i-1)操作,第4行是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.