c - 以下代码的时间复杂度

Question

这个问题已经有答案了:

How can I find the time complexity of an algorithm? (10 个回答)

Time complexity of nested for-loop (10 个回答)

已关闭 5 年前。

我想找到以下代码的时间复杂度，但我不确定我做得是否正确。 printf是基本流程。printf的时间复杂度是否因i*j or i*k而改变？ ？

i=0;              //c1
while (i<n){      //c2*(n+1)
     for(j=i; j<n; j++)  // c3*n*(n+1)
         printf("The product of %d and %d is %d\n",i,j,i*j);   //c4*n*n
     for(k=n; k>i; k--)    //c5*n*(n-1)
         printf("The product of %d and %d is %d\n",i,k,i*k);   //c6*n*n
      i++;  //c7*n 
}

所以时间复杂度= c1+c2*(n+1)+c3*(n^2 +n)+c4*n^2 + c5*(n^2 -n)+c6*n^2 + c7*n=c8*n^2 +c9*n +c10

Answer 1

要查找代码的时间复杂度，

    i=0;
    while (i<n){      // a loop will run n times
            for(j=i; j<n; j++)  // a loop will run n - i times
                     printf("The product of %d and %d is %d\n",i,j,i*j);  
            for(k=n; k>i; k--)    //a loop will run n -i times
                     printf("The product of %d and %d is %d\n",i,k,i*k);
            i++;
    }

所以总数约为 n * ((n-i) + (n -i))。但我们只需要关心当n趋于无穷大时增加最快的项。所以它是O(n^2)。