C++時間複雜度分析練習題

任何演算法的**時間複雜度**是指演算法完成所需的時間。它是衡量演算法效率和進行比較分析的重要指標。我們傾向於降低演算法的時間複雜度，使其更有效。

示例1

找出以下程式碼片段的時間複雜度

for(i= 0 ; i < n; i++){
   cout<< i << " " ;
   i++;
}

迴圈的最大值為n，但i在for迴圈中將被遞增兩次，這將使時間減半。因此，時間複雜度為O(n/2)，相當於O(n)。

示例2

找出以下程式碼片段的時間複雜度

for(i= 0 ; i < n; i++){
   for(j = 0; j<n ;j++){
      cout<< i << " ";
   }
}

內迴圈和外迴圈都執行n次。因此，對於i的單個值，j迴圈n次，對於n個i值，j將總共迴圈n*n = n²次。因此，時間複雜度為O(n²) 。

示例3

找出以下程式碼片段的時間複雜度

int i = n;
while(i){
   cout << i << " ";
   i = i/2;
}

在這種情況下，每次迭代後，i的值都變為其先前值的一半。因此，序列將類似於：。因此，時間複雜度為O(log n)。

示例4

找出以下程式碼片段的時間複雜度

if(i > j ){
   j>23 ? cout<<j : cout<<i;
}

程式碼中包含兩個條件語句。每個條件語句的時間複雜度為O(1)，對於其中的兩個，它為O(2)，相當於O(1)，即**常數**。

示例5

找出以下程式碼片段的時間複雜度

for(i= 0; i < n; i++){
   for(j = 1; j < n; j = j*2){
      cout << i << " ";
   }
}

內迴圈執行(log n)次，而外迴圈執行n次。因此，對於i的單個值，j執行(log n)次，對於n個i值，j將總共迴圈n*(log n) = (n log n)次。因此，時間複雜度為O(n log n)。

Sudhir Sharma

更新於：2021年8月2日

9K+ 次瀏覽

開啟你的職業生涯

完成課程獲得認證

開始學習