# 複雜度概念、二分搜尋法 ###### 05.06 鄭余玄 --- # 複雜度概念 ---- ## 演算法（Algorithm） 為了解決現實生活當中的各種問題，電腦科學家就把現實問題對應到數學問題，然後設計公式、把公式寫成程式，讓電腦執行程式計算答案 ── 這些公式就叫做演算法了。 ---- ## 如何衡量「好」的程式？ - 可以 AC？（正確性）<!-- .element: class="fragment" data-fragment-index="1" --> - 不會突然藍屏當掉？<!-- .element: class="fragment" data-fragment-index="2" --> - 符合正常邏輯？<!-- .element: class="fragment" data-fragment-index="3" --> - 程式碼可讀性？<!-- .element: class="fragment" data-fragment-index="4" --> - 有使用說明書？<!-- .element: class="fragment" data-fragment-index="5" --> - 跑得比別人快？<!-- .element: class="fragment" data-fragment-index="6" --> ---- ## 程式步數 - 與輸入規模無關的指令 ```c++ 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. 找出最大值 1. 找出最小值 1. 找出第二大的值 1. 找出第 K 大的值 1. 找出裡面有沒有 36 ---- ## 如何搜尋 假設現在給你一個已經由小到大排好的陣列  ---- ## 二分搜尋 - ```arr``` 排序過的數列 ```c++ 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))$