次のコードの時間複雑度

Question

次のコードの時間の複雑さを見つけたいと思っていますが、私が正しいことをしているかどうかはわかりません。 Printfは基本的なプロセスです。i*j or i*kのためにprintfの変更が複雑になりますか？

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 *（（NI）についてです+（n-i））である。しかし、nが無限に近づくと、用語の増加が最も速くなることだけを気にする必要があります。したがって、それはO(n^2)です。