1、數據結構和算法演講人2020-12-3001為什么要學習數據結構和算法為什么要學習數據結構和算法02如何高效學習數據結構和算法如何高效學習數據結構和算法學習技巧：0420個常用、基礎的數據結構和算法05書籍推薦 06概念：廣義上講，數據結構就是指一組數據的存儲結構。算法就是操作數據的一組方法01學習基礎：高中數學、基本編輯技巧02學習重點：復雜度分析03如何高效學習數據結構和算法學習技巧：010203041. 邊學邊練，適度刷題2. 多問、多思考、多互動3. 打怪升級學習法4. 知識需要沉淀，不要想試圖一下子掌握所有如何高效學習數據結構和算法20個常用、基礎的數據結構和算法單擊此處添加標題9,

2、300 Million單擊此處輸入你的正文，文字是您思想的提煉，為了最終演示發布的良好效果，請盡量言簡意賅的闡述觀點；根據需要可酌情增減文字，以便觀者可以準確理解您所傳達的信息。數據結構：數組、鏈表、棧、隊列、散列表、二叉樹、堆、跳表、圖、Trie 樹算法：遞歸、排序、二分查找、搜索、哈希算法、貪心算法、分治算法、回溯算法、動態規劃、字符串匹配算法03復雜度分析復雜度分析事后統計法的局限性 1. 測試結果非常依賴測試環境012. 測試結果受數據規模的影響很大02復雜度分析大 O 復雜度表示法031.公式：T(n) = O(f(n) 2.代碼的執行時間 T(n) 與每行代碼的執行次數 n 成正比

3、3.代碼執行時間隨數據規模增長的變化趨勢，也叫作漸進時間復雜度（asymptotic time complexity），簡稱時間復雜度。0201時間復雜度分析 知識點 最好情況時間復雜度最壞情況時間復雜度平均情況時間復雜度(又稱加權平均時間復雜度或者期望時間復雜度)均攤時間復雜度(一種特殊的平均時間復雜度)技巧 1. 只關注循環執行次數最多的一段代碼2. 加法法則：總復雜度等于量級最大的那段代碼的復雜度3. 乘法法則：嵌套代碼的復雜度等于嵌套內外代碼復雜度的乘積時間復雜度量級多項式 1. 常量O(1)2. 對數階O(logn)、O(nlogn)3. 兩個數據規模 O(m+n)、O(m*n)非多

4、項式 1. O(2n)2. O(n!)復雜度分析空間復雜度空間復雜度全稱就是漸進空間復雜度（asymptotic space complexity），表示算法的存儲空間與數據規模之間的增長關系。常見的空間復雜度就是 O(1)、O(n)、O(n2)04數組 數組（Array）是一種線性表數據結構。它用一組連續的內存空間，來存儲一組具有相同類型的數據。數組 定義特點1.線性表（Linear List）2.連續的內存空間和相同類型的數據3.時間復雜度 插入刪除O(n)查找O(1) 線性表：數組、鏈表、隊列、棧非線性表：二叉樹、堆、圖05鏈表鏈表LRU 緩存淘汰算法單擊此處添加標題9,300 Mill

5、ion先進先出策略 FIFO（First In，First Out）最少使用策略 LFU（Least Frequently Used）最近最少使用策略 LRU（Least Recently Used）單擊此處輸入你的正文，文字是您思想的提煉，為了最終演示發布的良好效果，請盡量言簡意賅的闡述觀點；根據需要可酌情增減文字，以便觀者可以準確理解您所傳達的信息。1.鏈表通過指針將一組零散的內存塊串聯在一起。其中，我們把內存塊稱為鏈表的“結點” 2.每個結點除了存儲數據之外，還需要記錄鏈上的下一個結點的地址，記錄下個結點地址的指針叫作后繼指針 next 3.第一個結點叫作頭結點，頭結點用來記錄鏈表的基地

6、址。 4.最后一個結點叫作尾結點，尾結點特殊的地方是：指針不是指向下一個結點，而是指向一個空地址 NULL，表示這是鏈表上最后一個結點。 5.時間復雜度 插入刪除O(1)查找O(n)單鏈表鏈表循環鏈表1.循環鏈表是一種特殊的單鏈表2.尾結點指針是指向鏈表的頭結點雙向鏈表1.每個結點不止有一個后繼指針 next 指向后面的結點，還有一個前驅指針 prev 指向前面的結點鏈表鏈表雙向環鏈表鏈表鏈表VS數組 1插入刪除：數組O(n)鏈表O(1) 2隨機訪問：數組O(1)鏈表O(n) 鏈表編寫鏈表代碼技巧01技巧一：理解指針或引用的含義02技巧二：警惕指針丟失和內存泄漏03技巧三：利用哨兵簡化實現難度

7、04技巧四：重點留意邊界條件處理05技巧五：舉例畫圖，輔助思考06技巧六：多寫多練，沒有捷徑鏈表常見的鏈表操作 01單鏈表反轉鏈表中環的檢測02030405兩個有序的鏈表合并刪除鏈表倒數第 n 個結點求鏈表的中間結點06棧棧棧在函數調用中的應用 棧在括號匹配中的應用 56%Option 247%Option 4特性 棧在表達式求值中的應用 1.后進者先出，先進者后出，這就是典型的“棧”結構2.一種“操作受限”的線性表3.用數組實現的棧，我們叫作順序棧，用鏈表實現的棧，我們叫作鏈式棧。30%Option 323%Option 107隊列 隊列 011.先進者先出，這就是典型的“隊列”2.操作受限

8、的線性表數據結構3.用數組實現的隊列叫作順序隊列，用鏈表實現的隊列叫作鏈式隊列。特性02 循環隊列03 阻塞隊列和并發隊列08遞歸遞歸14231. 一個問題的解可以分解為幾個子問題的解2. 這個問題與分解之后的子問題，除了數據規模不同，求解思路完全一樣3. 存在遞歸終止條件遞歸需要滿足的三個條件怎么將遞歸代碼改寫為非遞歸代碼？遞歸注意事項如何編寫遞歸代碼？寫遞歸代碼的關鍵就是找到如何將大問題分解為小問題的規律，并且基于此寫出遞推公式，然后再推敲終止條件，最后將遞推公式和終止條件翻譯成代碼 1.遞歸代碼要警惕堆棧溢出2.遞歸代碼要警惕重復計算09排序 如何分析一個“排序算法”冒泡排序（Bubbl

9、e Sort）插入排序（Insertion Sort）選擇排序（Selection Sort）歸并排序（Merge Sort）快速排序（Quick Sort）排序 單擊此處添加文本具體內容，簡明扼要的闡述您的觀點。根據需要可酌情增減文字，以便觀者準確的理解您傳達的思想。單擊此處添加標題排序 線性排序排序優化排序 如何分析一個“排序算法”ABC執行效率內存消耗穩定性執行效率1. 最好情況、最壞情況、平均情況時間復雜度2. 時間復雜度的系數、常數 、低階3. 比較次數和交換（或移動）次數內存消耗1. 通過空間復雜度衡量內存的消耗2. 原地排序算法，就是特指空間復雜度是 O(1) 的排序算法1. 如

10、果待排序的序列中存在值相等的元素，經過排序之后，相等元素之間原有的先后順序不變穩定性冒泡排序（Bubble Sort）冒泡排序只會操作相鄰的兩個數據。每次冒泡操作都會對相鄰的兩個元素進行比較，看是否滿足大小關系要求。如果不滿足就讓它倆互換。一次冒泡會讓至少一個元素移動到它應該在的位置，重復 n 次，就完成了 n 個數據的排序工作。最好情況時間復雜度O(n)最壞情況復雜度O(n)平均時間復雜度操作原子，比較和交換排序 有序度：數組中具有有序關系的元素對的個數逆序度：逆序度的定義正好跟有序度相反滿有序度：完全有序的數組的有序度公式：逆序度 = 滿有序度 - 有序度 公式：n*(n-1)/2推理方式

11、平均時間復雜度復雜度O(n)插入排序（Insertion Sort）將數組中的數據分為兩個區間，已排序區間和未排序區間。初始已排序區間只有一個元素，就是數組的第一個元素。插入算法的核心思想是取未排序區間中的元素，在已排序區間中找到合適的插入位置將其插入，并保證已排序區間數據一直有序。重復這個過程，直到未排序區間中元素為空，算法結束。最好情況時間復雜度O(n)最壞情況復雜度O(n)平均時間復雜度O(n)操作原子，比較和移動排序 排序 選擇排序（Selection Sort）01選擇排序算法的實現思路有點類似插入排序，也分已排序區間和未排序區間。但是選擇排序每次會從未排序區間中找到最小的元素，將其

12、放到已排序區間的末尾。02最好情況時間復雜度O(n)03最壞情況復雜度O(n)04平均時間復雜度O(n)排序 歸并排序（Merge Sort）歸并排序的核心思想還是蠻簡單的。如果要排序一個數組，我們先把數組從中間分成前后兩部分，然后對前后兩部分分別排序，再將排好序的兩部分合并在一起，這樣整個數組就都有序了。分治思想性能分析重點01030204分治，顧名思義，就是分而治之，將一個大問題分解成小的子問題來解決。小的子問題解決了，大問題也就解決了分治思想性能分析穩定的排序算法最好情況、最壞情況，還是平均情況，時間復雜度都是 O(nlogn)空間復雜度是 O(n)，非原地排序重點理解遞推公式和 mer

13、ge() 合并函數排序 快速排序（Quick Sort）1快排的思想是這樣的：如果要排序數組中下標從 p 到 r 之間的一組數據，我們選擇 p 到 r 之間的任意一個數據作為 pivot（分區點）。2性能分析3重點原地、不穩定時間復雜度也是 O(nlogn)性能分析重點理解遞推公式和 partition() 分區函數C基數排序（Radix sort）B計數排序（Counting sort）D線性時間復雜度可以達到 O(n)A桶排序（Bucket sort）排序 線性排序桶排序（Bucket sort）桶排序，顧名思義，會用到“桶”，核心思想是將要排序的數據分到幾個有序的桶里，每個桶里的數據再單

14、獨進行排序。桶內排完序之后，再把每個桶里的數據按照順序依次取出，組成的序列就是有序的了。桶排序比較適合用在外部排序中。所謂的外部排序就是數據存儲在外部磁盤中，數據量比較大，內存有限，無法將數據全部加載到內存中。計數排序（Counting sort）計數排序其實是桶排序的一種特殊情況。當要排序的 n 個數據，所處的范圍并不大的時候，比如最大值是 k，我們就可以把數據劃分成 k 個桶。每個桶內的數據值都是相同的，省掉了桶內排序的時間。計數排序只能用在數據范圍不大的場景中，如果數據范圍 k 比要排序的數據 n 大很多，就不適合用計數排序了。而且，計數排序只能給非負整數排序，如果要排序的數據是其他類型

15、的，要將其在不改變相對大小的情況下，轉化為非負整數。基數排序（Radix sort）基數排序對要排序的數據是有要求的，需要可以分割出獨立的“位”來比較，而且位之間有遞進的關系，如果 a 數據的高位比 b 數據大，那剩下的低位就不用比較了。除此之外，每一位的數據范圍不能太大，要可以用線性排序算法來排序，否則，基數排序的時間復雜度就無法做到 O(n) 了排序 排序優化如何選擇合適的排序算法？如何優化快速排序？qsort() 函數分析如何選擇合適的排序算法？1.一般都會首選時間復雜度是 O(nlogn) 的排序算法來實現排序函數 1. 三數取中法2. 隨機法原因：O(n2) 時間復雜度出現的主要原因

16、還是因為我們分區點選的不夠合理。區分算法 最理想的分區點是：被分區點分開的兩個分區中，數據的數量差不多。如何優化快速排序？10二分查找（Binary Search）二分查找（Binary Search）二分查找針對的是一個有序的數據集合，查找思想有點類似分治思想。每次都通過跟區間的中間元素對比，將待查找的區間縮小為之前的一半，直到找到要查找的元素，或者區間被縮小為 0。時間復雜度O(logn)實現應用場景的局限性四種二分查找的變形問題二分查找（Binary Search）實現非遞歸遞歸容易出錯的3個地方 1. 循環退出條件2.mid 的取值3.low 和 high 的更新遞歸實現非遞歸二分查找

17、（Binary Search）應用場景的局限性1.二分查找依賴的是順序表結構，簡單點說就是數組。012.二分查找針對的是有序數據。023.數據量太大也不適合二分查找。03應用場景的局限性1.二分查找依賴的是順序表結構，簡單點說就是數組。2.二分查找針對的是有序數據。3.數據量太大也不適合二分查找。二分查找（Binary Search）四種二分查找的變形問題變體一：查找第一個值等于給定值的元素變體三：查找第一個大于等于給定值的元素變體二：查找最后一個值等于給定值的元素變體四：查找最后一個小于等于給定值的元素四種二分查找的變形問題變體一：查找第一個值等于給定值的元素變體二：查找最后一個值等于給定值

18、的元素變體三：查找第一個大于等于給定值的元素變體四：查找最后一個小于等于給定值的元素11跳表（Skip list）跳表（Skip list）鏈表加多級索引的結構，就是跳表時間復雜度O(logn)12散列表（Hash Table）散列表用的是數組支持按照下標隨機訪問數據的特性，所以散列表其實就是數組的一種擴展，由數組演化而來。可以說，如果沒有數組，就沒有散列表。散列表（Hash Table）顧名思義，它是一個函數。我們可以把它定義成 hash(key)，其中 key 表示元素的鍵值，hash(key) 的值表示經過散列函數計算得到的散列值。 散列函數設計的基本要求 1.散列函數計算得到的散列值是

19、一個非負整數；2.如果 key1 = key2，那 hash(key1) = hash(key2)；3.如果 key1 key2，那 hash(key1) hash(key2)。著名的哈希算法 MD5、SHA、CRC散列函數散列沖突解決方法開放尋址法（open addressing） 線性探測（Linear Probing）二次探測（Quadratic probing）雙重散列（Double hashing）鏈表法（chaining）散列表（Hash Table）裝載因子：散列表的裝載因子=填入表中的元素個數/散列表的長度散列表（Hash Table）如何設計散列函數？1.散列函數的設計不能太

20、復雜。012.散列函數生成的值要盡可能隨機并且均勻分布02影響：裝載因子越大，說明散列表中的元素越多，空閑位置越少，散列沖突的概率就越大。不僅插入數據的過程要多次尋址或者拉很長的鏈，查找的過程也會因此變得很慢。動態散列表 動態擴容：當裝載因子過大時，重新申請一個更大的散列表，將數據搬移到這個新散列表中。動態縮容：隨著數據的刪除，散列表中的數據會越來越少，空閑空間會越來越多，裝載因子小于某個值之后，啟動縮容裝載因子過大了怎么辦？散列表（Hash Table）1.當裝載因子觸達閾值之后，我們只申請新空間，但并不將老的數據搬移到新散列表中。2.當有新數據要插入時，我們將新數據插入新散列表中，并且從老的散列表中拿出一個數據放入到新散列表。每次插入一個數據到散列表，我們都重復上面的過程。如何避免低效地擴容？成功散列表（Hash Table）1. 開放尋址法（當數據量比較小、裝載因子小的時候，適合采用開放尋址法。）2. 鏈表法（基于鏈表的散列沖突處理方法比較適合存儲大對象、大數據量的散列表，而且，比起開放尋址法，它更加靈活，支持更多的優化策略，比如用紅黑樹代替鏈表。）如何選擇沖突解決方法？成功散列表（Hash Table）工業級的散列表應該具有哪些特性？1.支持快速的查詢、插入、刪除操作；3.性能穩定，極端情況下，散列表的性能也不會退化到無法接受的情況。2.內存占用