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;
   }
}

对于 i 的所有值，上述方法将运行 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!)。

更新于：2019 年 10 月 24 日

855 次浏览

开始你的 职业生涯

完成课程获得认证

开始学习
广告