<style> h2{ color:#8B4746; } .blue{ color:#4A919E } </style> <font color="#4A919E">DSA 第七週講義</font> === >[name= 沈奕呈、林德恩][time= Feb 25,2022 ] ###### tags:`DSA` `資料結構` `演算法` `Data Structure` `Algorithm` `Data Structure and Algorithm` `tcirc39th` `社課` `臺中一中電研社` [TOC] --- ## <div class="blue">電研社</div> 社網:[tcirc.tw](https://tcirc.tw) online judge:[judge.tcirc.tw](https://judge.tcirc.tw) IG:[TCIRC_39th](https://www.instagram.com/tcirc_39th) --- ## 演算法 (Algorithm) --- ### 介紹 指一個被定義好的、計算機可施行其指示的有限步驟或次序 必須要有輸入、輸出、明確性、有限性、有效性 ---- > * 輸入：一個演算法必須有零個或以上輸入量。 > * 輸出：一個演算法應有一個或以上輸出量，輸出量是演算法計算的結果。 > * 明確性：演算法的描述必須無歧義，以保證演算法的實際執行結果是精確地符合要求或期望，通常要求實際執行結果是確定的。 ---- > * 有限性：依據圖靈的定義，一個演算法是能夠被任何圖靈完備系統類比的一串運算，而圖靈機只有有限個狀態、有限個輸入符號和有限個轉移函式（指令）。而一些定義更規定演算法必須在有限個步驟內完成任務。 > * 有效性：又稱可行性。能夠實現，演算法中描述的操作都是可以通過已經實現的基本運算執行有限次來實現。 ---- 簡單來講，演算法就是果汁機的藍圖 而藉由藍圖所設計出的果汁機要... - 有洞可以放入水果 --> 輸入資料 - 有另一個洞可以流出果汁 --> 輸出運算後的結果 - 要有把水果變成果汁的功能 --> 明確性 > >https://i.imgur.com/M1IklKM.jpg(圖源) --- ### 時間複雜度 時間複雜度通常會用到一個函式O(n)來表示花的時間，n代表輸入值，是以執行的次數去計算，時間複雜度越高，代表效率越不好，其考慮的是n趨近無窮大的情形，也就是不看低階項和首項的係數，如$2n^2+10000n$，其漸進時間複雜度是O($n^2$) ----  [<div style= "font-size:1px">由 Cmglee - 自己的作品, CC BY-SA 4.0, https://commons.wikimedia.org/w/index.php?curid=50321072</div>](https://commons.wikimedia.org/w/index.php?curid=50321072) ---- #### TLE Oline Judge 表示程式未通過的評分結果之一是TLE TLE (Time Limit Exceed): 表示執行超過時間限制 在每個測資點會限制執行時間，如果超過，就視為錯誤，所以要降低執行時間 而降低執行時間的方法就是減少程式的時間複雜度 ---- #### 計算時間複雜度 學會計算時間複雜度的好處之一，就是讓你在寫Judge的時候不會吃TLE(夠現實吧) 由於時間複雜度是看執行的次數 計算的方法就是關注重複次數多的部分(通常是迴圈) 單層迴圈的時間複雜度就是 O(n)，雙層就是O($n^2$)，依此類推 - 可以看一下題目的輸入個數，如果大於 $5000$ ，時間複雜度要小於 O($n^2$)，不然肯定會吃TLE ----  ----  黃色那個就是單個測資點所限制的時間 ---- ### 空間複雜度 用來表示程式用的儲存空間用量，也是用O(n)來表示，n是輸入的長度，如:有一程式不論輸入的n為多少，都建立一樣的變數，其複雜度是O(1);另一程式是根據輸入n建立大小為n的陣列，其空間複雜度是O(n) ---- #### MLE MLE (Memory Limit Exceed): 表示程序執行超過記憶體限制 因為在每個測資點會限制記憶體大小，如果超過，就視為錯誤，所以要降低記憶體使用量 ----  藍色那個就是單個測資點所限制的記憶體用量 --- ## I/O I/O就是指input和output，而如果在有多次輸入輸出時，可以用一些方法減少I/O的時間，如cin、cout改成printf、scanf，不過這兩個彈性較低。 ---- 另一個方法是將自動flush取消，因為分次輸出很耗資源，先來講一下在文字輸出前會送到緩衝區，會在一定的時間一次輸出，而cin會自動flush，而這時就要取消自動它們的自動flush，endl也會自動flush，所以改用'\n'。 ```cpp= cin.tie(nullptr); cout<<'\n';p ``` ---- 還有一點可以關掉iostream和studio.h的同步，也可以增加效率，記得關掉後不能混用到studio.h的東西 ```cpp= ios_base::sync_with_stdio(false); ``` [縮短I/O的時間](https://cp.wiwiho.me/io-optimize/) [37th學長的說明](https://judge.tcirc.tw/ShowThread?postid=7&reply=0) --- ## STL ---- ### 介紹 STL(Standard Template Library)，中文是**標準模板庫**，是一個軟體庫(Software Library)，並不是C\++的標準程式庫的一部分，且大量影響了C\++的標準程式庫 ※C\++的模板，本身即是一套複雜的巨集語言（macro language），巨集語言最大的特色為所有工作在編譯時期就已完成 ---- ### 組成 * 演算法(algorithm) * 函式(function) * 容器(container) * 迭代器(iterator) ---- ### 演算法(algorithm) 在STL有內建一些常見的演算法，如:排序、搜尋 <!-- 之後你們講到排序和搜尋時再教STL內建的排序和搜尋 --> ---- ### 容器(container) * Sequence containers * Container adaptors * Associative containers * Unordered associative containers [容器分類](http://cplusplus.com/reference/stl/) ---- * Sequence containers * array * vector * deque * list ---- * Container adapters * stack * queue ---- * Associative containers * set * map ---- * Unordered associative containers * unordered_set * unordered_map ---- ### 迭代器(iterator) 迭代器是用來在容器中指出一個位置或成對使用以劃定一個區域，來限定操作所涉及到的資料範圍。 --- ## 容器 容器是用來儲存多項資料的資料結構 ---- 使用stl容器記得引入該容器的標頭檔 ``` cpp= #include< stl容器名稱 > ``` ---- 等一下講的除了array、pair都可以用這些方法 ，而array可以用.size和.empty - `.size()` :讀取容器的大小 - `.clear()` :清空容器 - `.empty()` :確認容器是否為空 --- ## Sequence containers ### (序列容器)0️⃣1️⃣2️⃣3️⃣4️⃣ 序列容器可以依容器的「位置順序」存取元素， 就像有著一格格插座的延長線，或是一節一節的車廂 恩...這個比喻和 emoji 好像有點熟悉🤔 沒錯!陣列就是一種序列容器😂 ---- 以下列出的都是序列容器，以 "通用" 為特色 - array - vector - list - deque 除了list都可以像陣列一樣用索引來存取該位置的值 ---- ### array <!-- 不是STL容器 --> 陣列這個在[上學期](https://hackmd.io/@tcirc39th/r1-_5RhJ9/https%3A%2F%2Fhackmd.io%2Fl-6_ncqAT5aeJG8qMRpHog%3Fview#陣列array)講過了，複習一下，是用來儲存多筆資料，但開了就不能改長度，不過array不屬於STL容器 ---- ### vector 如果用vector就可以解決開了之後不能改長度這點，vector可以將它視為一個動態的陣列，都是以連續儲存資料，vector還可以刪除最尾端的元素，或新增元素在最尾端。 如果要指定刪除第幾個或指定在第幾個位置插入元素，可以用iterator來輔助。 是STL容器的一種 ---- 此頁是常用的基本操作 - `vector<資料型態> name`:宣告 - `.push_back(x)` :加入尾端的元素 - `.pop_back()` :移除尾端的元素 ---- - `vector<資料型態> name(陣列+x,陣列+y)`:宣告 可以建立一個含有從陣列第x個值到第y個值的vector ---- 插入元素：vec.insert(v.begin()+n,x); 清除指定元素(從頭端)：vec.erase(v.begin()+n); 清除指定元素(從尾端)：vec.erase(v.end()-1-n); ---- ```cpp= #include<iostream> #include<vector> using namespace std; int main(){ vector<int> a;//using like stack a.push_back(1); a.push_back(100); a.push_back(123); a.push_back(87);//1 100 123 87 cout<<a[1]<<' '<<a[3]<<' ';//可以像陣列一樣操作 a.pop_back();//1 100 123 a.push_back(2);//1 100 123 2 cout<<a[3]<<' '; a[1]=4; cout<<a[1]<<' '; } ``` ---- ``` /*---output 100 87 2 4 ---------*/ ``` ---- [b030: 健康檢查（Ⅰ）](https://judge.tcirc.tw/ShowProblem?problemid=b030) ---- ### list 和vector的其中一個差別是儲存方式用指向前一個和後一個資料，而非連續儲存，也因為這個關係，如果要找指定位置的資料，只能從頭或尾去找，因為它和vector不同，只會指向前一個和後一個資料 是STL容器的一種 ---- - `list<資料型態> name`:宣告 - `.push_back(x)` :加入尾端的元素 - `.pop_back()` :移除尾端的元素 - `.push_front(x)` :加入首端的元素 - `.pop_front()` :移除首端的元素 ---- ### deque 類似不只可以在尾端加入元素，同時也可以在最前端加入元素的vector，不過不能保證一定是儲存連續的位址。 是STL容器的一種 ---- - `deque<資料型態> name`:宣告 - `.push_back(x)` :加入尾端的元素 - `.pop_back()` :移除尾端的元素 - `.push_front(x)` :加入首端的元素 - `.pop_front()` :移除首端的元素 ---- ```cpp= #include<iostream> #include<deque> using namespace std; int main(){ deque<int> a;//using like queue a.push_back(1); a.push_back(100); a.push_back(123); a.push_back(87);//1 100 123 87 cout<<a[1]<<' '<<a[3]<<' ';//可以像陣列一樣操作 a.pop_front();//100 123 87 a.push_back(2);//100 123 87 2 cout<<a[0]<<' '<<a[3]<<' '; } ``` ``` /*---output 100 87 100 2 ---------*/ ``` --- ## Container adapters ### (容器配接器)✅❎❎❎✅ adapter就像整流器，能將通用的交流電，轉換成有特定用途的直流電 所以說穿了 Container adapters 就只是拿前面提到的 Sequence containers 的功能做組合、去除，讓我們方便進行特定的操作。 ---- <font color="#f00">注意 : Container adapters 去除了隨機存取(索引)的功能，只能對容器的頭或尾進行操作 </font> 以下列出的為 Container adapters - stack - queue ---- ### stack stack是種「Last-In-First-Out」的資料結構(後進先出) 可以把它想像為洋芋片的罐子，最後放進去的洋芋片一定是第一個被拿出來，且只能看到最上面的洋芋片 是STL容器的一種 ---- > https://online.carrefour.com.tw/zh/%E5%93%81%E5%AE%A2/1402005300101.html ---- #### stack 常用操作 - `stack<資料型態> name`:宣告 - `.push(x)` :加入尾巴的元素 - `.pop()` :移除尾巴的元素 - `.top()` :存取尾巴的值 ---- ```cpp= #include<iostream> #include<stack> using namespace std; int main(){ stack<int> a; //use push_back() if you use vector or deque a.push(1); a.push(100); a.push(123); a.push(87);//1 100 123 87 cout<<a.top()<<' '; //cout<<a[1]<<' '<<a[3]<<' '; //只能讀取尾巴的值 a.pop();//1 100 123 a.push(2);//1 100 123 2 cout<<a.top()<<' '; /* cout<<a[3]<<' '; a[1]=4; cout<<a[1]<<' ';*/ } ``` ---- ``` /*---output 87 2 ---------*/ ``` ---- [b039: Stack 模板題](https://judge.tcirc.tw/ShowProblem?problemid=b039) ---- ### queue queue是種「First-In-First-Out」的資料結構(先進先出) 可以把它想像為排隊，先排的人一定先走 是STL容器的一種 ---- #### queue 常用操作 - `queue<資料型態> name`:宣告 - `.push(x)` :加入尾巴的元素 - `.pop()` :移除頭的元素 - `.front()` :存取頭的值 - `.back()` :存取尾巴的值 ---- ```cpp= #include<iostream> #include<queue> using namespace std; int main(){ queue<int> a; //use push_back() pop_front() if you use deque a.push(1); a.push(100); a.push(123); a.push(87);//1 100 123 87 cout<<a.front()<<' '<<a.back()<<' '; //cout<<a[1]<<' '<<a[3]<<' '; //只能讀取頭尾的值 a.pop();//100 123 87 a.push(2);//100 123 87 2 cout<<a.front()<<' '<<a.back()<<' '; //cout<<a[0]<<' '<<a[3]<<' '; } ``` ---- ``` /*---output 1 87 100 2 ---------*/ ``` ---- ### Stack、Queue 的除錯技巧 實作的時候建議 - 使用 vector、deque 實作 stack 的概念 - 使用 deque 實作 queue 的概念 ---- 因為 stack、queue 本來就是從序列容器的原理做出來的，所以都有對應的函式可以使用 但使用序列容器才能用迴圈一格一格印出來 debug 所以才會建議用序列容器來實作 stack、queue ---- ### 使用STL容器時遇到RE怎麼辦 在「查看」或「pop」頭尾的值之前，建議先用.empty()判斷容器是否為空 尤其不能確定容器甚麼時候會空時更是如此!! <font color="#f00">否則當容器空了，沒有數能被查看或pop，就會發生run time error(RE)</font> ---- ```cpp= vector<int> v; int num,n; cin>>n; for(int i=0;i<n;i+=1){ cin>>num; while(v.empty()==0 and v.top()<num){ //當不符合第一個條件(容器不是空的)，會直接結束while迴圈 //不會判斷 v.top()<num ，有效避免RE v.pop(); } v.push_back(num); } ``` --- ## Associative containers ### (關聯式容器)🗝️🔒 關聯式容器可以依容器的 「key」 存取元素(value) 就像靠著特定的索書號，找到對應的書 如同索書號是照順序排的，key值會被系統自動排序且不能重複 所以每種操作，實際都需要「log n次」的操作次數來將key排序 ---- ### map 建立多個一對一的資料，可以用key值來找value <font color="#f00">key值不能重複</font> 是STL容器的一種 ---- - `map<key的資料型態,value的資料型態> name`:宣告 - `name[要設定的key]=value` :設定、更改 value沒設定的話會是空值，如果value型態是數字，其值會是0 - `.find(要找的key)` :尋找是否有這個key，是則回傳iterator，否則回傳.end() ---- ```cpp= #include<iostream> #include<map> using namespace std; int main() { map<char, int> m; m['1'] = 321; m['n'] = 123; cout << m['n']<<' ' << m['1']; } ``` ``` /*---output 123 321 ---------*/ ``` ---- ### set set 其實就是 key 等於 value 的 map 所以有以下幾個特性 - 放入的元素，系統會自動幫你照大小排好(很方便吧) - <font color="#f00">不能放重複的值</font> - <font color="#f00">沒辦法隨機存取(沒辦法用索引找第幾大的數)</font> 是STL容器的一種 ---- - `set<資料型態> name`:宣告 - `.insert(x)` :加入指定的元素x - `.erase(x)` :移除指定的值x - `.upper_bound()` :回傳第一個大於指定的值的元素 iteritor(沒有就回傳.end()) - `.lower_bound()` :回傳第一個大於等於指定的值的元素 iteritor(沒有就回傳.end()) ---- ```cpp= #include<iostream> #include<set> using namespace std; int main(){ set<int> s; s.insert(9); s.insert(7); s.insert(8); cout<<*s.begin()<<endl; s.insert(3); cout<<*s.begin(); } ``` ---- output ``` 7 3 ``` ---- ### multiset 是可以放重複數值的set 是STL容器的一種 ---- ### pair 兩個值組成的容器，可以想成map的key和value，不過只有一對。 ---- - `pair<第一個的資料型態,第二個的資料型態> name(第一個的值,第二個的值)` :定義 括號可不寫，如: - `pair<第一個的資料型態,第二個的資料型態> name` :定義 - `.first` : 第一個值，可視為一個變數 - `.second` : 第二個值，可視為一個變數 - `pair<第一個的資料型態,第二個的資料型態> name = make_pair(第一個值,第二個值);` : 定義、更改 ---- ```cpp= #include<iostream> using namespace std; int main() { pair<char, int> p('n', 3); cout << p.first<<endl; p.first = 'a'; p.second = 123; cout << p.first << endl; p = make_pair('b', 456); cout << p.first; } ``` ``` /*---output n a b ---------*/ ``` --- ## 迭代 迭代的功能類似於指標 好...大家應該忘記什麼是指標了，我們來複習一下 ---- ### 指標([複習](https://hackmd.io/smdIMOc-TUCz8YKEXree8A#指標)) 箭頭左邊為 ----- 在變數名稱前面加的東西 箭頭右邊為 ----- 其代表的意義 - 1. ` * `出現在宣告且在等號左邊 -> 指標(儲存記憶體位置的資料型態) - 2. ` * `出現其他地方 -> 取「儲存記憶體位置的變數」的值 - 3. ` & `出現在宣告且在等號左邊 -> 參考(將某一變數取別名) - 4. ` & `出現其他地方 -> 該變數的記憶體位置 ---- ### 迭代 迭代器的功能類似於指標，但是是專門設計用來遍歷stl容器(探訪容器的每個元素) 迭代器的意義是記憶體位置，隨然使用方法如指標，但並不是像指標一樣，將記憶體位置當作值來儲存，而是直接指向該元素。 所以只能用 '*' 輸出該記憶體位置的值，而無法將自身輸出 ---- 正向迭代器可以在的「最初元素 ` .begin() `和最末元素的下一個位置` .end()`之間」透過加減一個數字指向指定元素(加法向最末元素走) ex. 藉由 ` .begin()+3 ` 向右指向第四個元素 ---- > ---- 反向迭代器可以在的「最末元素 ` .rbegin() `和最初元素的上一個位置` .rend()`之間」透過加減一個數字找到指定元素(加法向最初元素走) ex. 藉由 ` .rbegin()+3 ` 向左指向倒數第四個元素 --- ## STL遍歷 ### vector ```cpp= int len = vec.size(); for(int i=0 ; i<len ; i++){ cout << vec[i] << endl; } ``` ---- 或用iterator ```cpp= vector<int>::iterator begin = vec.begin();//vec是陣列名稱 vector<int>::iterator end = vec.end(); vector<int>::iterator it; for(it=begin ; it!=end ; it++){ cout << *it << endl; } ``` ---- ### map(iterator) ```cpp= map<int,int>::iterator begin = m.begin();//m是陣列名稱 map<int,int>::iterator end = m.end(); map<int,int>::iterator it; for(it=begin ; it!=end ; it++){ cout << it->first<<' '<<it->second<< endl; } ``` ---- ### set(iterator) ```cpp= set<int>::iterator begin = s.begin();//s是陣列名稱 set<int>::iterator end = s.end(); set<int>::iterator it; for(it=begin ; it!=end ; it++){ cout << *it << endl; } ``` ---- ### 通用 ```cpp= for(auto &i : 要進行遍歷的容器名稱) { cout << i << " "; } ``` ---- #### 比較一下 auto 自動判斷資料型態 注意版本C\++11後 auto & 用於遍歷STL容器 注意版本C\++14後<!--多媒體教室好像是C++98-->