algorithm - 以下循环的运行时间

Question

我正在尝试查找以下循环的运行时间:

int m=1;
for(i=1;i<=k;i++)
{
    for(j=1;j<=A[i];j++)
    {
        B[m]=i;
        m++;
     }
}

这里，A是一个数组，里面有整数，这些整数的和是n。例如A的长度为2，A[1]=2，a[2]=4，则内循环会运行6次。

因此，在我的讲义中，它说这段代码的运行时间是 O(n+k)。但假设，例如，k 为 5，数组 A 的长度为 4，并且 A[1]=3，A[2]=0，A[3]=0，A[4]=9，A[ 5]=0。所以，n=12。然后，对于 k=1，内循环将迭代 2 次，对于 k=2，外循环将迭代 1 次，对于 k=3，外循环将运行 1 次，对于 k=4，内循环将运行 9 次，并且对于 k=5，外循环将运行 1 次，因此迭代总数为 14。这大于 k 和 n，运行时间既不是 O(n) 也不是 O(k)。我在这里做错了什么？

谢谢

Answer 1

外层循环会迭代k次，因为你在做

for(i=1;i<=k;i++)

内层循环的总迭代次数为

sum (A[i])对于 i = 1...k ，你知道它是 = n .

这给出了 n + k迭代。由于内部循环中的东西在恒定时间内运行，复杂度为 O(n + k) .

编辑:

当我们说一个非负函数 f(n) 是什么意思是O(g(n)) ？

回答:

查找适当的 Stackoverflow 问题

What is a plain English explanation of "Big O" notation?

编辑 2:

实际上，上面链接中的答案很冗长，所以为了完整起见，这里给出数学定义。

让f(n)是一个非负函数。然后我们说f(n) = O(g(n)) (阅读“f(n) 是 g(n) 的大 O”)如果存在正常数 c和 n0这样

f(n) <= c g(n)

所有n >= n0 .