在 Day1 我們有提到過 Francis Sullivan 說的什麼是好的演算法，我覺得很讚~

For me, great algorithms are the poetry of computation. Just like verse, they can be terse, allusive, dense, and even mysterious. But once unlocked, they cast a brilliant new light on some aspect of computing.
-- Francis Sullivan

但這並沒有辦法詳細的衡量一個演算法的好壞

所以今天來介紹如何客觀的衡量一個演算法的好壞，首先就是時間複雜度 (Time Complexity)

時間複雜度 (Time Complexity)

演算法分析的執行時間的快慢，一定是一個判斷演算法好壞的重要原因。

但每台電腦都有不同的效能，所以我們會以執行次數來代表執行時間

而影響執行時間的因素，還有更重要的是輸入規模

• 像是一個排序演算法，排序 10 筆資料更排序 10000 筆資料速度肯定不同的

所以我們會以輸入規模 n (n 筆資料) 作為基準，來觀察演算法的執行時間 (次數) 隨 n 增長的變化來進行分析。

這就是所謂的時間複雜度 (Time Complexity)。

但每一次的輸入狀況都不同 (像是輸入一個排序好的 vs 排序完全相反的)，所以我們想要客觀判斷時間複雜度，通常會分為：

• 最佳狀況複雜度 (Best-Case Complexity)
• 平均狀況複雜度 (Average-Case Complexity)
• 最壞狀況複雜度 (Worst-Case Complexity)

而大多數都會以最壞狀況複雜度作為判斷依據

而最壞狀況複雜度又取決於最壞狀況執行次數

那怎麼判斷輸入規模跟執行次數的關係呢？

接下來我們以 Insertion Sort 做分析。

Insertion Sort 分析

這是我們的 code，我們開始逐行分析，我們定義 unsorted 的長度為 n，那總次數我們會寫成 T(n)。

def insertion_sort(unsorted):
    for i in range(1, len(unsorted)):
        key = unsorted[i]
        j = i - 1
        while j >= 0 and unsorted[j] > key:
            unsorted[j+1] = unsorted[j]
            j -= 1
        unsorted[j+1] = key
    return unsorted

第 1 行：
定義函數，不算次數

def insertion_sort(unsorted):

第 2 行：
迴圈內部程式碼執行 n-1 次，但會多 1 次判斷當 i == len(unsorted) 時
總共：n 次

    for i in range(1, len(unsorted)):

第 3 行：
for 迴圈內部從 1 到 n-1
總共：n-1 次

        key = unsorted[i]

第 4 行：
for 迴圈內部從 1 到 n-1
總共：n-1 次

        j = i - 1

第 5 行：
for 迴圈內部的 while 從 1 到 n-1，每一次又會跑 i 次，所以為 1 + 2 + 3 +... + (n-1)
但會多 1 次判斷當 j < 0 or unsorted[j] <= key 時
總共：2 + 3 + 4 +... + (n-1) + n 次

        while j >= 0 and unsorted[j] > key:

第 6 行：
while 內部，為 1 + 2 + 3 +... + (n-1)
總共：1 + 2 + 3 +... + (n-1) 次

            unsorted[j+1] = unsorted[j]

第 7 行：
while 內部，為 1 + 2 + 3 +... + (n-1)
總共：1 + 2 + 3 +... + (n-1) 次

            j -= 1

第 8 行：
for 迴圈內部從 1 到 n-1
總共：n-1 次

        unsorted[j+1] = key

第 9 行：
return 一個東西只需要 1 次
總共：1 次

    return unsorted

總覽：

def insertion_sort(unsorted):                 #  次數
    for i in range(1, len(unsorted)):         #   n
        key = unsorted[i]                     #   n-1
        j = i - 1                             #   n-1
        while j >= 0 and unsorted[j] > key:   #   2 + 3 + 4 + … + n 
            unsorted[j+1] = unsorted[j]       #   1 + 2 + 3 + … + (n-1)
            j -= 1                            #   1 + 2 + 3 + … + (n-1)
        unsorted[j+1] = key                   #   n-1
    return unsorted                           #   1

那我們透過高斯的等差級數公式化簡 5-7 行：

• 1 + 2 + 3 + ... + (n-1) = (n-1) * (1 + (n-1))/2
• 2 + 3 + 4 + ... + n = (n-1) * (2 + n)/2

我們就可以得到

這就是我們 insertion sort 的最壞狀況執行次數了！

謝謝~

參考資料
Thomas H. Cormen、Charles E. Leiserson、Ronald L. Rivest、Clifford Stein，《演算法導論》，碁峰資訊，2024 年
ChatGPT