演算法 | Big O 複雜度| Pseudocode 偽代碼
演算法是一種解決問題的虛擬邏輯。
想像一下，今天要在字典裡面找到 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)。
在演算法的時間複雜度會忽略常數，且只看最高次項，因為最高次項對演算法的執行時間影響最大，而常數和係數的影響相對較小。例如：
5n2+3n+2
- 5n２是二次項，
- 3n 是一次項，
- 2 是常數項。
當我們分析時間複雜度時，我們會忽略常數 2 和低次項 3n，因為當 n 越來越大時，低次項就不重要。我們只會看最高次項 ，所以這個演算法的時間複雜度可以簡化為 O(n2)。
時間複雜度排序圖解：
- 最好的是綠色的 O(1)，不管輸入數值多大，步驟固定不變。
- 最差的是粉紅色的 O(n!)，也就是階乘增長，隨著輸入數量 n 增長，程式跑的步驟數會迅速增加。
補充 Big O、Big Ω 和 Big Θ：
- Big O：只關注演算法的上界，表示最大可能的運行時間。
- Big Ω：只關注演算法的下界，表示最小可能的運行時間。
- Big Θ：同時考慮上界和下界，表示演算法的精確時間複雜度，適用於上下界一致的情況。
** 注意：big O 可以代表所有上界，它是個範圍而不是定值，但我們只會取其最佳者。
假設某演算法的時間複雜度，最差是 2ｎ 最好是 n2 ，這張圖中，2ｎ的右邊都是 Big O，n2 的左邊都是 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(log2n)，目標值在最後一格，要走過每筆資料才能找到。
- 平均情況：O(1)+O(log2n) 約略等於 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，可能需要為每一個資料建立一個變數，這會讓程式變得很複雜。結構可以能把這些相關的資料整合在一起，像是「打包」成一個資料包一樣，更方便工程師管理跟使用。至於詳細的應用會在下篇詳述。
補充資料
Big O 在面試的情境。
【工程師求職攻略】 面試流程大解析 找工作照著這5步 Coding Interview like a PRO!
你可能也想看
