演算法 | Big O 複雜度| Pseudocode 偽代碼

不藏獅

2024/09/26閱讀時間約 11 分鐘

演算法是一種解決問題的虛擬邏輯。

想像一下，今天要在字典裡面找到 Zoo，有幾種方法：

逐頁查找：如果字典有 1000 頁，最糟情況下需要翻 1000 次 才能找到。
兩頁兩頁找：這樣的話，1000 頁最多要翻 500 次。
二分查找：從字典的中間開始，假設翻到 M，而 Z 在 M 之後，這時可以忽略掉左邊的資料。使用這種方法，1000 頁只需要翻大約 10 次（對數操作，log₂1000 ≈ 10）。

這三種方法都可以成功找到「Zoo」，但哪一種是效率最高的呢？

同樣地，程式也可以正確運行，但如何讓它效率更高呢？其中一個衡量標準是時間複雜度。透過理解時間複雜度，我們可以有標準評估程式的優劣。

Big O 表示法是時間複雜度的常用符號，也是軟體工程師應具備的基本知識之一。

時間複雜度

「時間複雜度」用來表示一個演算法隨著輸入大小（通常記作 n）增長時，運行所需的步驟數的變化。時間複雜度主要是用 O( ) 即 Big O 表示法來表達。

O(n) 念作 O of n，雖然有時可能會遇到像 O(n/2) 這樣的情況，但常數倍數（如 /2）在 Big O 表示法中並不影響複雜度的大小，因為對演算法的整體速度影響不大。因此，通常省略常數，直接用 O(n) 表示。

Big O 用來表示演算法在最壞情況下的時間複雜度上限，描述的是隨著資料量增大，運行步驟增長的趨勢。

例子：1 加到 100 如果使用迴圈來計算 1 加到 100，電腦就需要執行 99 次。如果是加到 1000，則需要執行 999 次，因此這是一個 O(n) 的演算法。而如果使用公式 [(1+100)∗100]/2，這只需要固定的 3 個步驟（加、乘、除），不管數字多大，因此這是一個 O(1) 的演算法。

各種時間複雜度的解釋：

O(n²)： 如果有 n 個資料，運行時間會是 n²（比如 n² 次運算）。常見於雙重巢狀迴圈，常用在處理圖像或是矩陣。
O(log n)： 如果有 n 個資料，運行時間是 log(n)。雖然技術上是 log₂(n)，但底數（2、10）在 Big O 表示法中是可以忽略的，所以我們通常簡單寫作 O(log n)。一個典型的例子是二元搜尋。
O(n)： 如果有 n 個資料，運行時間與資料量呈線性關係，即每個資料都需要處理一次。這樣的演算法就屬於 O(n)。

在演算法的時間複雜度會忽略常數，且只看最高次項，因為最高次項對演算法的執行時間影響最大，而常數和係數的影響相對較小。例如：

5n²+3n+2

5n^２是二次項，
3n 是一次項，
2 是常數項。

當我們分析時間複雜度時，我們會忽略常數 2 和低次項 3n，因為當 n 越來越大時，低次項就不重要。我們只會看最高次項，所以這個演算法的時間複雜度可以簡化為 O(n²)。

時間複雜度排序圖解：

最好的是綠色的 O(1)，不管輸入數值多大，步驟固定不變。
最差的是粉紅色的 O(n!)，也就是階乘增長，隨著輸入數量 n 增長，程式跑的步驟數會迅速增加。

不同 Big-O 常見的比較。圖片來源：devopedia

補充 Big O、Big Ω 和 Big Θ：

Big O：只關注演算法的上界，表示最大可能的運行時間。
Big Ω：只關注演算法的下界，表示最小可能的運行時間。
Big Θ：同時考慮上界和下界，表示演算法的精確時間複雜度，適用於上下界一致的情況。

** 注意：big O 可以代表所有上界，它是個範圍而不是定值，但我們只會取其最佳者。

假設某演算法的時間複雜度，最差是 2^ｎ最好是 n²，這張圖中，2^ｎ的右邊都是 Big O，n²的左邊都是 Big Ω

Big O 是最常用的，因為通常我們最關注演算法在上界的表現。

最後的總結：

Big O 表示法常用來描述演算法的最壞情況下的效率。雖然還有 Big Ω 和 Big Θ 這些表示法，但新手只需要記得 Big O 是用來分析時間複雜度的常見工具。在軟體工程師面試時會詢問「這種寫法的 Big O 是多少？」，並詢問有沒有更好的 Big O。

線型搜尋、二元搜尋的時間複雜度

線性搜尋（Linear）就是一頁一頁找

最佳情況：O(1)，第一格就找到。
最糟情況：O(n)，目標值在最後一格，要走過每筆資料才能找到。
平均情況：O(n/2)=O(n)。但是數字大到可忽略 /2 的差異。

二元搜尋（Binary search）

需要已排序的資料。直接從中間對半切，再根據該資料落在左邊或是右邊繼續找。

最佳情況：O(1)，切一次就找到。
最糟情況：O(log₂n)，目標值在最後一格，要走過每筆資料才能找到。
平均情況：O(1)+O(log₂n) 約略等於 O(logn)。

線性搜尋、二元搜尋程式碼

我一開始的寫法：

目的：一個一個讀，找到數字就回傳 found ，沒有就回傳 not found。

#include <cs50.h>
#include <stdio.h>

int main()
{
    int number[] = {1, 20, 4, 25, 50, 100};
    int n = get_int("Number: ");
    for (int i = 0; i < 6; i++)
    {
        if (number[i] == n)
        {
            printf("Found\n");
        }
        else
            printf("Not Found\n");
    }
}

結果跑出：

但我其實是需要只需要傳一次就好，要全部都讀完才告訴我有沒有。現在，再試一次另外一種寫法。

#include <cs50.h>
#include <stdio.h>

int main()
{
    int number[] = {1, 20, 4, 25, 50, 100};
    int n = get_int("Number: ");
    for (int i = 0; i < 6; i++)
    {
        if (number[i] == n)
        {
            printf("Found\n");
        }
    }
    printf("Not Found\n");
}

這次也同時跑出 Found 跟 Not Found ，原因是不管程式前面如何運行，結果都會產生 Not Found 。

所以要使用 return 0 表示成功不再繼續運行；而 return 1 表示失敗。

#include <cs50.h>
#include <stdio.h>

int main()
{
    int number[] = {1, 20, 4, 25, 50, 100};
    int n = get_int("Number: ");
    for (int i = 0; i < 6; i++)
    {
        if (number[i] == n)
        {
            printf("Found\n");
            return 0; // 成功，不用再繼續跑
        }
    }
    printf("Not Found\n");
    return 1; // 失敗，找不到
}

Pseudocode 偽代碼

在正式寫出可以運行的程式之前，我們可以先從第一步到最後一步想好如何解決問題，並使用接近程式邏輯的方式來思考。這就像寫英文作文時，先用英文擬出大綱，再補充內容，最後調整成正確的文法。

偽代碼（pseudocode）有助於梳理邏輯思路。它不屬於任何特定的程式語言，因此無論用哪種語言，偽代碼都能幫助我們組織和規劃解決問題的步驟。當邏輯清晰後，再根據所選的程式語言進行細節調整。例如，思考如何進行 1 到 7 的迴圈時，可以先寫出偽代碼：

for i from 1 to 7: 
    i++

這雖然不是正確的語法，但它幫助我們釐清迴圈的運作方式。而在實際的 C 語言中，這段偽代碼可以被改寫為：

for (int i = 0; i < 7; i++)

另外一個例子，我第一次寫 1 加到 100。可以先寫個步驟的思路再寫偽代碼：

將 sum 設為 0。
使用 for 迴圈，從 i = 1 開始，直到 i = 100 結束。
每次迴圈中，將目前的 i 值加到 sum 中，得到新的 sum 值。
注意，以下偽代碼不能在程式運行，因為沒有標頭檔，和主程式 int main()。

int sum = 0; 

for (int i = 1; i <= 100; i++) {
    sum = sum + i;  
}

如果以 Python 的概念可以寫成：

sum = 0 

for i in range(1, 101):
    sum += i  

print(sum)

C Structures (structs)

假設我今天要建立「學生」的資料庫，這個學生有多種不同類型的資料需要儲存，比如姓名、年齡、學號和成績。這些資料的類型可能是字串（姓名）、整數（年齡）、浮點數（成績）。如果不用 Structures，可能需要為每一個資料建立一個變數，這會讓程式變得很複雜。結構可以能把這些相關的資料整合在一起，像是「打包」成一個資料包一樣，更方便工程師管理跟使用。至於詳細的應用會在下篇詳述。