C ++中一个有趣的时间复杂度问题

时间复杂度可以定义为算法运行其平均情况所需的时间。

让我们看看并计算一些基本功能的时间复杂度。

方法

void counter(int n){
   for(int i = 0 ; i < n ; i++){
      for(int j = 1 ; j<n ; j += i ){
         cout<<i<<” ”<<j;
      }
      cout<<endl;
   }
}

上面的方法将对所有值n / I次运行，即第一次迭代为n次，最后一次迭代为1次。

据此，总时间复杂度为

(n/1 + n/2 + n/3 + …. + n/n)
= n (1/1 + ½ + ⅓ + …. 1/n)

现在（1/1 +½+⅓+…。1 / n）的值等于O（log n）。

该代码的时间复杂度为O(nlogn)。

方法

void counter(n){
   int i , j ;
   for(int i = 1 ; i <= n ; i++){
      for(j = 1; j <= log(i) ; j++){
         cout<<i<<” ”<<j;
      }
   }
}

该函数的总复杂度为O（log 1）+ O（log 2）+ O（log 3）+…。+ O（log n），即O（log n！）。