演算法（Algorithm）

為了解決現實生活當中的各種問題，電腦科學家就把現實問題對應到數學問題，然後設計公式、把公式寫成程式，讓電腦執行程式計算答案 ── 這些公式就叫做演算法了。

如何衡量「好」的程式？

• 可以 AC？（正確性）
• 不會突然藍屏當掉？
• 符合正常邏輯？
• 程式碼可讀性？
• 有使用說明書？
• 跑得比別人快？

程式步數

• 與輸入規模無關的指令

d = a + b + c * c;            // 1 step
a = 2;                        // 1 step
std::cin >> n;                // 1 step
for (int i = 0; i < n; ++i) { // n + 1 step
    s += arr[i];              // n step
}
// total steps: 2n + 4

時間複雜度

• \(T_1(n)=500n\)
• \(T_2(n)=n^2\)

大 O 符號

• 上限漸近線，記作 \(f(n) = O(g(n))\)

常見時間複雜度

• \(O(1)\) 常數時間、\(O(n)\) 線性時間
• \(O(n^k)\) 多項式時間、\(O(2^n)\) 指數時間

如何搜尋

假設現在給你一個已經由小到大排好的陣列

1. 找出最大值
2. 找出最小值
3. 找出第二大的值
4. 找出第 K 大的值
5. 找出裡面有沒有 36

如何搜尋

假設現在給你一個已經由小到大排好的陣列

二分搜尋

• arr 排序過的數列

int binary_search(int arr[], int size, int goal) {
    int left = 0, right = size - 1, mid;
    while (left <= right) {
        mid = left + (right - left)/2;
        if (arr[mid] == goal)
            return mid;
        else if (arr[mid] > goal)
            right = mid - 1;
        else if (arr[mid] < goal)
            left = mid + 1;
    }
    return -1; // 找不到
}

比較時間複雜度

• 循序搜尋：\(O(n)\)
• 二分搜尋：\(O(log(n))\)