下面循环的最佳情况/最坏情况分析是什么?
本文关键字:最坏情况分析 是什么 情况 最佳 循环 | 更新日期: 2023-09-27 18:15:52
没有跳过外层循环和第二个循环的步骤,这将给我们n(n+1)/2次迭代,但我不知道如何计算最内层循环。
int n = int.Parse(Console.ReadLine());
int i =1,j,k;
while(i<=n)
{
for(j=1;j<=i;j++)
{
if(j%3==0)
{
for(k=1;k<=(n/2);k++)
{
Console.Write("*");
}
}
else if(j%3==1)
{
k=j;
while(k>=1)
{
Console.Write("@");
k--;
}
}
else
{
for(k=1;k<=(j%3);k++)
{
Console.Write("$");
}
}
}
i++;
}
第一个循环将有精确的n
次迭代。
第二个循环将有精确的n(n+1)/2
次迭代。
第二个环内大致有n/2
的1/3
长环、j
的1/3
长环和2
的1/3
长环。
如果我们只看这三种可能的情况中的第一种那么我们得到(n(n+1)/2) * 1/3 * n/2
即n*n*(n+1)/12
即O(n^3)
或者更准确地说是Theta(n^3)
这两个额外的情况没有太大的区别,它们只是改变常量。
综上所述,在悲观和乐观两种情况下,该代码都必须执行与n^3
成比例的迭代次数。
两个小窍门
- 不输出单个字符,而是将它们收集到字符串构建器中并在末尾打印一次。
- 创建一个字符的重复字符串可以用
new string(char, int)
函数完成。
- 外环:基于n: O(n)的线性环
- 外环:基于n: O(n)的线性环
内循环:
- 基于n/2: O(n)
的线性回路- 基于基于n的i的基于j的线性回路:O(n)
- 基于基于n的i的基于j的线性回路:O(n)
O(n) * O(n) * O(n) = O(n ^3)。
你可能认为这不完全正确——第一个最内层循环是O(n/2),但是在Big-O计算中,常量被消除了,所以O(n/2)和O(n)是一样的。
(更新——我忘了最外层的循环)