CS61B資料結構及演算法筆記：(十)分析運算效率

Evan

6 min readJul 17, 2023

在前面的章節多次提到用不同方法實現資料結構對程式執行效率的差異，整個課程的核心也是在探討如何針對特定類型的問題，使用相對應最佳的資料結構，而這個章節會介紹如何判斷程式執行的效率。

首先，以如何判斷一個已經排序過的整數陣列中，是否存在重複整數的問題為例，如圖一所示：

為了示範，先比較兩種不同的判斷方法

方法一：遍歷陣列中所有的整數，找出當前和所有後續整數的所有組合，判斷陣列是否存在重複整數，如圖二所示。

public static boolean dup1(int[] A) {  
  for (int i = 0; i < A.length; i += 1) {
    for (int j = i + 1; j < A.length; j += 1) {
      if (A[i] == A[j]) {
         return true;
      }
    }
  }
  return false;
}

方法二：遍歷陣列中所有的整數，只比較當前整數和下一個整數，判斷陣列是否存在重複整數，如圖三所示。

public static boolean dup2(int[] A) {
  for (int i = 0; i < A.length - 1; i += 1) {
    if (A[i] == A[i + 1]) { 
      return true; 
    }
  }
  return false;
}

顯然第二個方法是比較好的方法，理由是利用陣列已經排序過的特性，只要下一個整數和當前整數不相同，則不須比對後續的整數，即可判斷出陣列是否存在重複的整數。不過為了示範如何用數學邏輯證明出方法二是比較好的做法，會一步步分析程式在執行這個兩種方法時所需要耗費的時間，最後再介紹現實中常用的判斷方式。

直觀上可以用另一個獨立的程式紀錄執行前後所經過的時間，或是實際用儀器量測。確實計算出兩種方法所花費的時間後，可以發現當陣列尺寸 N 愈來愈大時，方法二所花費的時間會遠小於方法一，因此可以得到方法二比方法一好的結論。雖然直觀且簡單，不過如果想要在實際量測前，就可以透過數學計算比較，則需要用到接下來介紹的方式。
首先觀察方法一實作中程式在執行每一個運算可能執行的次數。e.g. i = 0 無論如何都只會執行一次；可能第一次比較就會發現陣列有重複整數，所以 j = i + 1 可能只會執行一次，或是最差的狀況直到最後一組整數，i = 9999 時，執行第 10000 次 j = i + 1；以此類推粗略計算出每種運算可能執行的次數，如圖四所示。

同樣地也可以粗略算出方法二的執行次數，如圖五所示。

接著假設每種運算每次執行所花費的時間為常數，即可得到程式執行所花費的時間跟執行次數成正比的結果。雖然只是粗略估算，不過計算每種運算執行的次數的過程相當複雜且困難，同時也沒有辦法輕易得知當 N 變得更多或更少時，運算執行的次數會如何變化，不過從結果不難看出，從估算的執行次數清楚顯示方法二為比較有效率的作法。

如果將考慮 N 等於固定常數 10000 改為符號 N 代替，利用數學推導出以 N 表示的計算次數，如圖六所示。缺點一樣是推導出公式的過程非常困難，不過可以從結果觀察出方法一運算執行的次數會隨著 N 成平方幅度的成長；方法二則是和 N 成線性成長。

不管是考慮固定常數或是代數 N，都可以用來評估程式執行的效率，如果將 N 和運算執行次數的關係放到幾何座標上來看，觀察出平方幅度的成長會以呈現一條拋物線，而線性成長會呈現一條直線。假設 N 不大，線性運算的次數可能高於拋物線，不過當運算次數不多時，所花費的時間差可以忽略，因此在評估時，通常會以最差的條件，也就是假設 N 非常大的條件下，判斷拋物線執行的次數會遠大於直線，如圖七所示。

分析的目的並不是檢討每種運算實際上可能執行的次數或是函式，而是希望能夠快速估算程式執行運算的次數，相依於 N 的成長幅度，進而評估不同方法的運算效率，因此，依下列步驟再簡化分析流程：

選擇可以具代表性的運算 e.g. ==
忽略低階（當 N 非常大時可以忽略）的項目 e.g. - N
忽略常數係數 e.g. 1 / 2

得到執行次數成拋物線或是線性成長的結果，如圖八所示。

從簡化過程中可以發現第一步可以選擇其他運算代表演算法，挑選 == 和 A[] 的結果會相同，而明顯 i = 0 則不是一個好選擇。接下來，並不希望每次分析時都花時間列出每種運算代表的函示，再從中挑選，而是想簡化複雜的分析過程，一眼就能看出代表演算法的成長級數。

重新分析方法一的程式碼，依靠直覺挑選 == 當成代表演算法的運算，當然還有其他選擇，不過為了方便先假設選擇 ==，假設 i = j = N，== 執行的次數會等於1 + 2 + … + (N — 1) = N(N — 1)/2，或是從圖八的幾何表格可以觀察出執行次數為等腰三角形的面積，換句話說，不管用何種方式評估，都可以得到這段程式碼執行的成長級數為 N² 。

Big-Theta

為了方便形容可以代表程式碼相依於 N 的成長級數，引用符號 big-theta 的定義：
當 N 非常大時，如果程式碼的函數為 R 而它的成長級數為 f，代表存在兩個大於 0 的常數 k1 k2 使得 R 的值在落這兩個常數乘上 f 之間。舉例來說，當 N 非常大時，R = N(N — 1)/2 的值會落在 N²/10 和 N² 之間，因此該演算法的成長級數為 N²，如圖九所示。

另一個常見的符號 big-O 也經常被用來形容程式碼的成長級數，甚至比 big-theta 更常被使用，差別在於 big-theta 的成長級數同時有上限和下限，雖然較為精準不過我們通常會關心的問題大部分都是最差的情況，而 big-O 只定義上限而沒有下限，為一種較寬鬆同時又可以考慮最差狀況的表達方式。

實際上分析程式碼執行效率的過程可能更複雜且刁鑽，又或著是第一眼直覺的成長級數會跟實際一步步分析結果不同，舉例來說：寫出一段兩層迴圈的程式碼的成長級數並不一定就是 N²。不幸的是，分析的過程並沒有某種特定的通則可以適用於所有問題，因此，快速且準確的分析還需要更多的練習。

CS61B資料結構及演算法筆記：(十)分析運算效率

Big-Theta

Written by Evan