<!-- 簡報宣告 --> # 時間複雜度 & greedy #### 第5週社課 ### 講者：鄭勝宇、郭久銘 --- ## 一天刷三題 三年TOI --- # 時間複雜度 ---- 用來表示程式運算時間與資料大小關係的一個函式 更明確的說，它代表當$n$變大時，運算時間跟著變大的「趨勢」，所以$n$越大，它越準確 通常以大O(Big O)符號表示 它是客觀的，所以不會使用任何單位 ---- ## 表示方法 如果$f(n)$代表程式的總操作次數 (變數賦值、加法運算...) 則我們去掉它的低階(最高階以外的)項和首項係數後 就是它的時間複雜度 Ex:$O(n^3+100n^{2}+n+1000)=O(n^3)$ 表示程式的計算次數的曲線和$n^3$的曲線十分相近 ---- 範例 ```cpp for (int i = 1; i <= n; i++) { // code } for (int i = 1; i <= n; i++) { for (int j = 1; j <= n; j++) { // code } } for (int i = 1; i <= n; i++) { // code } ``` $O(n^2+2n))=O(n^2)$ 因為當$n$極大時，$n^2+2n\approx n^2$ ---- ## 討論 為什麼低階項和首項係數可以被省略？ 因為隨著資料大小的增長， 這些對於運算時間的影響就越來越少，如圖 而且不同的電腦效率也不同 為了客觀，我們忽略這些相差的倍數 ---- ### 不同複雜度下$n$對運算時間的關係圖  圖源：維基百科 ---- ## $O(1)$ 常數時間，不論$n$多大，執行的操作次數都差不多 Ex：判斷$n$是否整除於$k$ ---- ## $O(n)$ 線性時間，執行的操作次數和$n$正比 Ex：輸入一個$n$項陣列 Ex：計算整個陣列有幾個$1$ ---- ## 預備條件：$\log_a{b}$ $\log_2{1}=0~~~\log_{10}{1}=0~~~~~~$ $\log_2{2}=1~~~\log_{10}{10}=1~~~~$ $\log_2{4}=2~~~\log_{10}{100}=2~~$ $\log_2{8}=3~~~\log_{10}{1000}=3$ $~~$在資訊中，如果省略$a$，通常表示$a=2$ 但在數學中，如果省略$a$，通常表示$a=10$ ---- ## $O(\log n)$ Ex：給定數字範圍$1～n$， 每次猜數字都會知道太大還太小 要以最少次數找到答案 (因為每次範圍都能砍一半) ----  ---- 前綴和：$O(n)$ 線段樹：$O(n\log n)$ 當$n$到$2^{63}$時，$\log n$也才63而已 (正常不會有人出到$2^{63}$啦) 所以說它是常數好像也不是不行XD 這就是我放這個梗圖的目的 ---- ## $O(n^2)$ Ex：Selection Sort 把最大的數移到最右邊(n次運算) 把第二大的數移到右邊第二項(n-1次運算) 直到最小的數(1次運算) $O(\small\frac{n(n-1)}{2}$$)=O(n^2)$ ---- ## $O(n\log n)$ Ex：用好的演算法排序一個$n$項陣列 Ex：Merge Sort, Quick Sort ---- ## $O(2^n)$ Ex：$n$種物品中，取或不取的所有組合 ---- ## $O(n!)$ Ex：輸出所有重新排列陣列[1,2,3,...,n]的組合數 ---- ## 遞迴的複雜度 舉例:費氏數列（$\leq 2^n$） ---- ### 不同複雜度下$n$對運算時間的關係圖  圖源：維基百科 ---- 對於不同的$n$，可以AC的時間複雜度  圖源：Competitive Programmer’s Handbook --- # greedy 貪婪演算法 ---- greedy演算法應該算是競程裡面最早學到的演算法之一，對於打競程的人來說，greedy應該就是跟沒打競程的人最大的差距 ---- 如果要刷greedy題，codeforces裡面難度小於1400的大部分都是，就盡量練習吧 ---- ## 直覺的算法，越貪心越好 ---- ### 觀察問題特徵，擬定一個看似最好的<br>原則，依照原則填答案、改答案 ---- #### 實際的例子：收銀員演算法 Cashier Algorithm 如果你給收銀員$100買了一個$24的健達出奇蛋， 他要怎麼用最少的硬幣找你$76？ 顯然用台幣的話會找你$50、$10、$10、$5、$1 很簡單對吧，就是：先找給你面額較高的硬幣 ---- ## 反例 如果找得到反例，那greedy就不能用 如果我們把幣值改成$40、$15、$1呢？ greedy:76 = 40×1 + 15×2 + 1×6 共9個 正確: 76 = 15×5 + 1×1 共6個 ---- 所以使用greedy的前提， 就是要先確定它對於這個題目不會出錯 ---- 剛學greedy時， 你可以試試看每題都證明它能不能用， 當然到最後你一看就知道能不能用了 通常證明greedy都是用反證法 ---- <!--偷爛--> ## 活動選擇問題 暑假到了，有好多好多有趣的營隊可以參加囉！ 攀岩、潛水、單車環島團、吉他營、電腦營、 …… 每個營隊都好有趣，好想每個營隊都參加 ── 可是卻有好多營隊的活動期間都互相卡到， 沒辦法同時參加。 到底要參加哪些營隊活動才好呢？ 當然是越多種越好！ ---- ## 思考一下... 要使用什麼策略？  <!-- 陷阱OK --> 圖源：Competitive Programmer’s Handbook ---- ## 對!沒錯!就是那樣! 選擇結束時間越早的越好(前一頁的圖是騙你的)  圖源：Competitive Programmer’s Handbook ---- ## 好了，來點抽象的問題 ---- #### 給定整數數列$A_1$～$A_n$，試求"連續區間"元素最大和，區間可為空 (相當於找到一組$l,r$，使$A_l+A_{l+1}+A_{l+2}+...+A_r$有最大值) ---- ## 思考兩分鐘 $[2,1,-4,7,-5,6]$ ---- ## 演算法：Kadane's Algorithm 對於陣列的每一項，我們先嘗試取它看看(以temp 變數儲存取之後的總和)，看能不能使答案變大 (以ans變數儲存目前答案的最大值) 當temp < 0時，表示目前的拿的部分對它後面的 區間和貢獻為負(見下頁圖片)， 所以我們索性把目前取到的區間捨去，把temp歸零 時間複雜度：顯然$O(n)$ 空間複雜度：也是$O(n)$ ----  ---- ## code ```cpp int ans = 0, temp = 0; for(int i = 0; i < n; i++){ temp += a[i]; if(temp < 0) temp = 0; ans = max(ans, temp); } ``` ---- ## 實際上來看 紀錄到現在的"連續元素最大和"以及到現在的"最大和" 連續元素最大和小於0時歸0 $a_i$ $2 ,1 , -4 , 7 , -5 , 6$ $temp_i$ $2,3,0,7,2,8$ $globalmax_i$ $2,3,3,7,7,8$ ---- ## 10分鐘實作時間：有問題直接問 ---- 對於不能使用greedy的題目， 我們就要使用其他的方法， 通常是另類的「求出所有組合」， 之後會教 ---- ## 下次課程：STL們