時間複雜度 === https://pse.is/3bb8vp ---- # 語法/算法 --- ## 複雜度 ---- ## 做每件事情都有他的花費時間 - 長大一歲 需要365.25天 - 寫考卷可能需要 0.04天 - 寫10張考卷可能需要0.4天 ---- ### 時間複雜度 在執行一個程式的時候 根據輸入的數字範圍 所推估的時間長度 通常會是用多項式表示 ---- ex. $4n^3+8n^2+4$ 這個時候可以發現當$n$很大時 可以只注意$4n^3$ (後面成長速度太低) 又因為4是常數 所以可以忽略 最後得到 $O(n^3)$ ---- ### 空間複雜度 如同時間複雜度 拿來估計記憶體使用量 --- ## 計算時間複雜度 ---- ## $O(1)$ 做一件事情 - 判斷true false - 弄一個變數or賦值 - 輸入/出一個東西 - 公式計算1~N的總和($\frac{N(N-1)}{2}$) ---- ## $O(N)$ 迴圈重複 - 印出1~N - 暴力計算1~N的總和($1+...+N$) ---- ## $O(N^2)$ 雙重迴圈/其他 - 印出NN乘法表 - 重複O(N) N次 - 給二維陣列賦值 - 遞迴計算費氏數列 ---- ## 其他常見複雜度 - $\sqrt{N}$ 確定是否為質數 - $log(N)$ 快速排序 ---- ## 成長圖  --- ## 搜尋 ---- ## 終極密碼 常見的猜數字遊戲 從範圍(0-100)中猜出對方的數字 ->策略 每次從範圍中找中間的數字 ---- ## 範例 [0,100]50 -> 太大 [0,50]25 -> 太小 [25,50]37 -> 太大 [25,37]31 -> 太大 [31,37]34 -> 太小 [34,37]36 猜對ㄌ ---- ## 二分搜尋 對於一個排序過後的數列 如果要找數值x，可以用上面的方法 ---- 在arr中找出數字x在第幾個 ```cpp= l = 0, r = N; mid =(l + r)/2 x < arr[mid] ? r = mid : l = mid ``` ----  ----  ----  ----  ----  ---- ## CODE ```cpp= int l = 0, r =n; while (l != r - 1) { int mid = (l + r) / 2; if (x < arr[mid]) r = mid; else l = mid; } cout << "find:" << l <<endl; ``` ---- ## 簡單搜尋 ```cpp= for(int i = 0; i < n; i++){ if(arr[i] == x){ cout << "find:" << i << endl; break; } } ``` ---- ## 時間複雜度！ 二分搜尋每次可以減少一半的範圍 $N\Rightarrow\frac{N}{2}\Rightarrow\frac{N}{4}\Rightarrow\frac{N}{8}\Rightarrow...\Rightarrow\frac{N}{2^A}$ $2^A = N$ 取$log_2 \Rightarrow log_22^A=log_2N$ $A = log_2N$ $O(log_2N):O(N)$ --- ## 排序 ---- ## 選擇排序 {%youtube xWBP4lzkoyM %} ---- ## CODE ```cpp= for(int i = 0; i < n; i++){ for(int j = i + 1; j < n; j++){ if(arr[i] > arr[j]){ swap(arr[i], arr[j]); } } } ``` $O(N^2)$ ---- ## 合併排序 請看白板>< ---- ## 快速排序 {%youtube 5nXrEBhBFpU%} ---- ## CODE ```cpp= sort(arr, arr+n); ``` --- ## 各種奇怪的排序影片 {%youtube kPRA0W1kECg %} --- ## 題目們 --- ## 手寫一次二分搜 --- ## 氣泡排序 ---