您将如何找到该算法的复杂性？ [英] How would you go about finding the complexity of this algorithm?

问题描述

function alg1(n)
1 a=0
2 for o=1 to n do
3     for t=1 to o do
4         for k=t to o+t do
5         a=a+1
6 return(a)

如果有人可以指导我了解如何在这里找到最坏的情况，以及如何将alg1的输出a作为n的函数，我将不胜感激。谢谢！

If anyone could guide me to how you would find the worst-case here, and how to get the output a of alg1 as a function of n, I would be very grateful. Thanks!

推荐答案

我们可以计算出该代码执行的增量的确切数量。首先，让我们用

We can compute the exact number of increments this code executes. First, let's replace

for k=t to o+t do

与

for k=1 to o+1 do 

此更改后，两个内部循环看起来像这样

After this change, two inner loops looks like this

for t=1 to o do
    for k=1 to o+1 do

这些循环的迭代次数显然是 o *（o + 1）。迭代总数可以通过以下方式计算：

The number of iterations of these loops is obviously o*(o+1). The overall number of iterations can be calculated in the following way:

我们可以排除系数并降低系数使用big-O表示法时多项式的阶项。因此，复杂度为 O（n ^ 3）。

We can exclude coefficients and lower order terms of the polynomial when using big-O notation. Therefore, the complexity is O(n^3).

这篇关于您将如何找到该算法的复杂性？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！