2

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

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)。我在这里做错了什么？

谢谢

4

2 回答 2

3

外循环将迭代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 问题

“Big O”符号的简单英文解释是什么？

编辑2：

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

设f(n)为非负函数。然后我们说f(n) = O(g(n))(read "f(n) is big-oh of g(n)") 如果存在正常数c并且n0这样

f(n) <= c g(n)

对于所有人n >= n0。

于 2013-03-22T19:28:52.110 回答
0

除非我遗漏了一些东西，否则原始功能可以简化为：

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

在最坏的情况下，sum(A[i]) = n

在我看来，这个函数的运行应该不会比 k*n 差，对于大 k，k=n 所以 O(n^2) 应该是答案。

我认为乘法是有序的，而不是加法。

假设循环 A 运行 3 次，循环 B 每次运行 A 运行 2 次。这等于 6 次运行，而不是 5 次。所以 3*2 而不是 3+2

编辑：

证明：

f(n) = k*n

让 g(n) = n^2

f(n) <= C xg(n)

对于 C = 1，N0 = max(A[i])

于 2016-08-16T06:12:57.623 回答