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 次瀏覽

開始你的 職業生涯

完成課程獲得認證

開始學習
廣告