<style> .reveal .slides { font-size: 40px; } </style> # 南大附中資訊研究社 NFIRC 1st ## 第 11 次社課講義 2024/04/24 主講：ShiYu、正宗老師 ---- ## 課前準備 - 點名 - 繳社費 <!-- - 幹部徵選：[表單連結](https://forms.gle/jfNZH6jM2Y91komF6)  --> --- 學會了程式的基礎語法後 我們為什麼還要學演算法？ （開放式問題） ---- 在下學期的第一堂社團課 教到了如何分析時間複雜度 ---- 我們除了利用電腦解決問題以外 還關心用哪種方法能更有效率的解決問題 ---- 今天要利用幾個問題 促進大家的思考能力 並教大家一些技巧和算法 讓程式更有效率 --- ## 本次社課內容 - 前綴和、差分 - 補充：二維前綴和 - 單調性 - 雙指針 - 二分搜尋法 - 補充各種搜尋 --- ## 暖身問題 給你一串數字 [ 1, 2, 6, 4, -1, 5 ] 請問 第 2 個數字 到 第 5 個數字 總和是多少？ ---- ### 答案：11 你算對了嗎？用什麼方法？ ---- ## 慢慢加 [ 1 , 2 , 6 , 4 , -1 , 5 ] 第 2 個數字 到 第 5 個數字 總和 2 + 6 + 4 + (-1) = 11 ---- 那再問 第 3 個數字 到 第 6 個數字 的總和呢？ [ 1, 2, 6, 4, -1, 5 ] ---- 你是否又再重新加了一次？ ---- 該如何快速算出區間的總和？ ---- ## 錢墜河？ ---- ## 前綴和 prefix-sum 將數列由前往後加總形成新數列  ---- 當我們要查詢某段區間的總和  例如：從 L 到 R 的總和 直接 $A[R] - A[L-1]$ 就好 ---- ## 時間複雜度 比較兩種做法的效率 1. 從左到右一個一個加起來 2. 用前綴和直接算右邊減掉左邊 ---- 1. $O(n)$ 2. $O(1)$ $O(n) > O(1)$ ---- 所以當我們事先把數列都先加起來放著 不管多少次詢問 我們都不用再重新加總一次 而是可以直接用扣的就好 ---- 所以解決這種問題很重要的技巧是 <span style="color:red">預處理</span> 的概念 事先處理好你想要的資訊並儲存起來 能在以後就用到 這樣的做法會大大提升效率 ---- ## 建出前綴和的程式碼  ---- ## 完成  ---- 當我們要查詢區間和時  ---- ## 進階：二維前綴和 能快速算出子矩陣面積  有時間再補充講解 --- ## 差分 數列相鄰元素的差值 ---- 數列： [ 1, 2, 6, 4, -1, 5 ] 差分： [ 1, 4, -2, -5, 6 ] ---- ## 差分的應用 將某段區間 L 到 R 都加上 n，有什麼方法？ ---- 例如：[ 1, 2, 6, 4, -1, 5 ] 區間 2 ~ 5 都加上 10 變成 [ 1, <span style="color:green">12, 16, 14, 9</span>, 5 ] ---- 換個角度思考 我們可以在差分數列上 把 <span style="color:green">L - 1 加上 n</span>，並在 <span style="color:red">R 減掉 n</span> ---- 數列： <span style="color:yellow">[ 1, 2, 6, 4, -1, 5 ]</span> 差分： <span style="color:blue">[ 1, 4, -2, -5, 6 ]</span> ---- 數列： <span style="color:yellow">[ 1, 2, 6, 4, -1, 5 ]</span> 差分： <span style="color:blue">[ 1, 4, -2, -5, 6 ]</span> 如果要區間 2 ~ 5 都加上 10 可以在差分數列的<span style="color:green">第 1 項加上 10</span> 並在<span style="color:red">第 5 項減掉 10</span> ---- 數列： <span style="color:yellow">[ 1, 2, 6, 4, -1, 5 ]</span> 差分： <span style="color:blue">[ 1, 4, -2, -5, 6 ]</span> 如果要區間 2 ~ 5 都加上 10 可以在差分數列的<span style="color:green">第 1 項加上 10</span> 並在<span style="color:red">第 5 項減掉 10</span> 新差分： <span style="color:blue">[ <span style="color:green">11</span>, 4, -2, -5, <span style="color:red">-4</span> ]</span> ---- 數列： <span style="color:yellow">[ 1, 2, 6, 4, -1, 5 ]</span> 差分： <span style="color:blue">[ 1, 4, -2, -5, 6 ]</span> 如果要區間 2 ~ 5 都加上 10 可以在差分數列的<span style="color:green">第 1 項加上 10</span> 並在<span style="color:red">第 5 項減掉 10</span> 新差分： <span style="color:blue">[ <span style="color:green">11</span>, 4, -2, -5, <span style="color:red">-4</span> ]</span> 再加起來得到新數列 <span style="color:yellow">[ 1, <span style="color:green">12, 16, 14, 9</span>, 5 ]</span> ---- 一樣可以達到效果 而且不管區間多長 都只要在差分數列上做一次加法跟一次減法就好 不用一個一個都加上同個數字 ---- 不管是前綴和還是差分 我們都是為了想簡化沒效率且重複的計算 所以先把資料都處理好 以便之後可以馬上求出答案 ---- 這些技巧可以延伸到進階的資料結構 例如：線段樹 Segment tree 、 BIT 樹狀數組 但這難度較高 社課不會教到 --- <!-- :::warning 如果在這老師還沒來就講二維前綴和 等老師來了我再開始講單調性 單調性和雙指針講完換老師講二分搜 ::: ---- --> ### 除了 預處理 和 枚舉(剪枝) ### 我們還能用什麼技巧提升效率呢？ ---- ## 從 觀察性質 下手 例如： 這些數字都是偶數 這些數字都是質數 這些數字由小排到大 ---- ## 單調性 一個保持順序關係的重要性質 可以是 遞增 或 遞減 簡單來說就是由小排到大 或 由大排到小 ---- ## 什麼東西具有單調性 - 爬山 - 溫度 - 身高 - 成績 - 排序過後的數列 ---- ## 單調性可以做什麼 提升搜尋效率 ---- ## 問題思考 給一串數字 請找出哪對數字加起來是 10 [ 5 , 2 , 7 , 6 , 11 , 3 , 9 ] ---- [ 5 , 2 , <span style="color:green">7</span> , 6 , 11 , <span style="color:green">3</span> , 9 ] ---- 枚舉太沒效率 時間複雜度 $O(n^2)$ 或許我們可以將數列先排序好 [ 2 , 3 , 5 , 6 , 7 , 9 , 11 ] 運用 <span style="color:red">雙指針</span> 的技巧找到哪對數字加起來是 10 ---- 在排序後的數列頭尾各有一個指針 | <span style="color:red">L</span> | | | | | | <span style="color:blue">R</span> | | --- | --- | --- | --- | --- | --- | --- | | 2 | 3 | 5 | 6 | 7 | 9 | 11 | 2 + 11 = 13 > 10 太大了 把 <span style="color:blue">R</span> 往左移 ---- | <span style="color:red">L</span> | | | | | <span style="color:blue">R</span> | | | --- | --- | --- | --- | --- | --- | --- | | 2 | 3 | 5 | 6 | 7 | 9 | 11 | 2 + 9 = 11 > 10 還是不行 再左移 ---- | <span style="color:red">L</span> | | | | <span style="color:blue">R</span> | | | | --- | --- | --- | --- | --- | --- | --- | | 2 | 3 | 5 | 6 | 7 | 9 | 11 | 2 + 7 = 9 < 10 <span style="color:blue">R</span> 可以不動了 換移 <span style="color:red">L</span> 去湊出 10 ---- | | <span style="color:red">L</span> | | | <span style="color:blue">R</span> | | | | --- | --- | --- | --- | --- | --- | --- | | 2 | 3 | 5 | 6 | 7 | 9 | 11 | 3 + 7 = 10 ✅ ---- 透過單調性 我們可以運用雙指針去找出答案 ---- ## 雙指針還是太慢了 ## 有沒有更快的搜尋方法？ ---- ## 經典遊戲：終極密碼 1 ~ 100 猜數字 每次猜都會告訴你太小或太大 怎樣才能更快猜中答案？ ---- ## 每次都猜中間 ## 能快速縮小範圍 ---- ## 二分搜尋法 Binary Search 每次都將數列中間點切分為兩半 再捨棄掉其中一半 重複直到找到答案 提升搜尋效率 ---- ## 原理圖像化 在一個有單調性的柱子中找到高度為 35 的柱子  試看看逐一檢查 會發現效率很慢 所以我們來學用二分搜尋法快速找到 35 ---- 先找到中間點 28 < 35  ---- 答案不可能在左半部 捨棄掉  ---- 再找右半部的中間點 34 < 35  ---- 一樣將不可能的那一半捨棄  ---- 繼續找中間點 40 > 35 這次要捨棄右半部  ---- 找到 35 了！  ---- 我們每次都將數列切一半 捨棄不可能成為答案的那部分 重複直到找到答案 ---- ## 時間複雜度 哪種方法比較快？ 1. <span style="color:red">逐一檢查</span> 2. <span style="color:blue">二分搜尋法</span> ---- ## 時間複雜度 1. <span style="color:red">逐一檢查</span> $O(n)$ 2. <span style="color:blue">二分搜尋法</span> $O(\log_2 n)$ $O(n) > O(\log_2 n)$ <span style="color:blue">二分搜尋法</span>比較快 每次都 <span style="color:blue">$\div 2$</span> 當然比 每次都 <span style="color:red">-1</span> 速度快 ---- ## 二分搜尋法的重要前提 ### 數列具有單調性 也就是要先排序過 沒排序過就用二分搜尋法 答案可能會不小心被捨棄掉 ---- ## C++ 實作 二分搜尋法  --- ## 延伸思考 因為有時數列不一定存在要找的數字 如果想要找數列中第一個大於某數的數字是多少呢？ 例如：在班上同學中找到第一個身高大於 170cm 的人 ---- ## 二分搜的變形 ### upper_bound：找第一個 > x 的數字 ### lower_bound：找第一個 >= x 的數字 只要稍微修改一下二分搜的程式碼即可達成 ---- ## C++ 實作 upper_bound  ---- ## C++ 實作 lower_bound  ---- 可以發現這三份程式碼只有些微的差別 而且實作細節多 很容易寫錯 所以我們可以使用 C++ 內建函式來幫我們完成 ---- ## C++ 內建函式使用方法 ```cpp= int a[10] = {4,7,4,2,5,8,8,9,3,4}; sort(a, a + 10); // 使用前一定要先排序 cout << binary_search(a, a + 10, 4) << '\n'; cout << binary_search(a, a + 10, 6) << '\n'; cout << upper_bound(a, a + 10, 4) - a << '\n'; cout << lower_bound(a, a + 10, 4) - a << '\n'; ```  ---- ## 算某元素有幾個 可以用 upper_bound 去減掉 lower_bound 留給大家思考原因 ---- 還有其他各種二分搜尋的變種 算滿有趣的 有興趣的同學可以自己查詢 就不多做教學 - 對答案二分搜 - 跳躍二分搜 - 三分搜 - 黃金比例搜 ---- 其實還有很重要的 - DFS 深度優先搜尋 - BFS 廣度優先搜尋 不過這也需要一次社課才能講完 所以今天的內容到此結束