下面循环的最佳情况/最坏情况分析是什么?

本文关键字:最坏情况分析 是什么 情况 最佳 循环 | 更新日期: 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/21/3长环、j1/3长环和21/3长环。

如果我们只看这三种可能的情况中的第一种那么我们得到(n(n+1)/2) * 1/3 * n/2n*n*(n+1)/12O(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)是一样的。

    (更新——我忘了最外层的循环)