我正在尝试查找以下循环的运行时间:
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)。我在这里做错了什么?
谢谢