int i = 0;
int n = 20;
while (i < n)
{
i++;
int j = i;
while (i < n)
{
printf("this is %d", i);
i++;
}
i = j;
}
因此,为了估计这个函数的时间复杂度,我估计的方法是外循环运行n
时间。内环运行n - 1
时间吗?那么这个嵌套循环的时间复杂度是O(n^2)
吗?
发布于 2020-01-23 07:28:49
您可以重写初始代码。
int n = 20;
int i = 0;
while (i < n)
{
i++;
int j = i;
while (i < n)
{
printf("this is %d",i);
i++;
}
i = j;
}
与其相当:
int n = 20;
for (int i = 1; i < n; ++i)
for (int j = i; j < n; ++j)
printf("this is %d", j);
现在很明显,您有O(n**2)
时间复杂性:
(n - 1) + (n - 2) + (n - 3) + ... + 3 + 2 + 1 = n * (n - 1) / 2
操作(printf(...)
)和
O(n * (n - 1) / 2) = O(n**2 / 2 - n / 2) = O(n**2)
发布于 2020-01-23 07:30:49
在以后的迭代中,内循环运行次数与n-1、n-2、n-3、.= 1.所以和n(n-1)/2,从而导致了与O(n^2)一样的渐近时间复杂度.
https://stackoverflow.com/questions/59873362
复制相似问题