以下代码的大麻烦是什么?

问题描述

代码:

int temp = 0;
for (int h = 1; h <= n; h = h * 2)
{
   for (int i = 1; i <= n; i++)
   {
      for (int j = 1; j<=n; j++)
      {
         for (int k = 1; k<i; k++)
         {
            temp++
         }
      }
   }
}

根据我的计算，big-O为 lg n * n ^ 4 .请指导.

According to my calculations, big-O is lg n * n^4.Kindly guide.

谢谢大家的答复.我知道我在哪里犯错了.我非常感谢参加的每个人.

Thank you all for the replies. I understood where I was making the mistake. I really appreciate everyone who participated.

推荐答案

for (int h = 1; h <= n; h = h * 2) // increment is pow(2). hence executed ln(n) times
{
   for (int i = 1; i <= n; i++) // increment is one. Executed n times
   {
      for (int j = 1; j<=n; j++)// increment is one. Executed n times
      {
         // increment is one. Executed i times. See below
         for (int k = 1; k<i; k++)
         {
            temp++
         }
      }
   }
}

k循环执行i次. i的最大值为n.因此您可以认为它总是被执行n次(近似)

The k loop is executed i times. The maximum value of i is n. so you can consider it as being executed n times always (over approximation)

复杂度= ln(n)* n * n * n = ln * pow(n，3)

complexity = ln(n) * n * n * n = ln*pow(n,3)

另一种查看方式...交换i循环和j循环

Another way to look at it... lets exchange i loop and j loop

for (int h = 1; h <= n; h = h * 2) // increment is pow(2). hence executed ln(n) times
    {
       for (int j = 1; j <= n; j++) // increment is one. Executed n times
       {
          // see below
          for (int i = 1; i<=n; i++)
          {
             for (int k = 1; k<i; k++)
             {
                temp++
             }
          }
       }
    }

现在看一下....(i，k)的执行总数为n*(n+1)/2.那么现在的复杂性是什么?

now look at it.... the total number of executions of (i,k) is n*(n+1)/2. so now what is the complexity?

h * j *(i，k)= ln(n)* n *(n *(n + 1)/2)== ln(n)* pow(n，3)

h * j * (i,k) = ln(n) * n * (n*(n+1)/2) == ln(n) * pow(n,3)

这篇关于以下代码的大麻烦是什么?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！