該文章為清華大學數據結構與算法設計MOOC課程讀書筆記.
1. 抽象數據類型 VS 數據結構
2. 向量ADT
2.1 有自己的一套接口操作
2.2 可擴充性
-
靜態(tài)空間管理 Static Memory Management
靜態(tài)空間管理 動態(tài)空間管理 Dynamic Memory Management
思路：即將上溢時檩咱，容量加倍
為什么是容量加倍策略而不是容量遞增個常數而已呢召锈？
容量遞增 -> 每次擴容操作的amortized time 為O(N)
容量加倍 -> 每次擴容操作的amortized time 為O(1)
容量遞增 VS 容量加倍
- 加倍擴容的耗時僅為紫色條的和
- 加倍擴容是犧牲一定的空間利用率來換取時間的效率
3. 分攤復雜度
舉個??：
在擴容分析的中溪猿，若只考慮獨立操作，那么最壞情況復雜度都為O(N)（遞增擴容中由n-1擴到n带迟；加倍擴容由n/2到n)
然而解恰，考慮了連續(xù)的一系列操作時鲫剿，單次遞增擴容的分攤時間為O(N^2 / N) = O(N)掐暮；加倍擴容的分攤時間為O(N / N) = O(1)。??
4. 無序向量
實現(xiàn)了各種對應的操作...
其中一個比較有趣的是deduplicate() ---> 無序向量remove duplicate
- 算法1：暴力
思路：從前往后check每個元素愿卒，在它之前的元素中查重缚去。若有重復，remove它琼开，后面元素前移病游；若無重復，check下一個元素。
時間復雜度：O(N^2)
優(yōu)化1：減少元素移動的次數
思路：先對要刪除的元素的標記衬衬，之后再統(tǒng)一刪除。
好處：保持了unique元素的穩(wěn)定性改橘。
時間：O(N^2) 比較次數沒有變優(yōu)化2：利用排序
思路：因為重復元素肯定緊鄰滋尉，因此可以在O(1)時間內找到duplicate
時間：O(NlgN)
5. 有序向量
5.1 有序性以及逆序程度
5.2 去重uniquify()
- 高效 O(N)
- 思路：雙指針
-
關鍵："隱式刪除"
需要刪除的元素（即重復元素）并不會直接被remove，因此不會導致之后元素的前移飞主。當發(fā)現(xiàn)非重復元素時狮惜，把該元素直接賦值到與之比較的元素之后，因此它們之前重復的元素相當于“被刪除了”碌识！
有序向量高效去重
5.3 二分查找 search(e, lo, hi）--版本A
-
原理
二分原理 -
實現(xiàn)
實現(xiàn) -
復雜度 O(lgN)
二分復雜度 -
更精細的分析-查找長度
摳系數分析 O(1.5lgN)
查找長度
5.4 Fibonacci 查找
-
原理
Fib查找原理
與二分查找的本質區(qū)別：pivot(即mid)按黃金分割比例取
-
實現(xiàn)
Fib查找實現(xiàn) -
復雜度-在系數上優(yōu)于二分
Fib查找長度
5.5 二分查找--版本B
- 原理
- 思路：對于每個向量(即每個比較區(qū)間)碾篡，無論向左還是向右，需要的比較長度都是1筏餐。
-
關鍵：只有兩個分支：要么[lo, mi),要么[mi, hi]魁瞪，沒有對x[mi]的比較导俘。只有在hi - lo == 1是才終止旅薄。
原理
5.6 二分查找--版本C
該版本能夠滿足語義約定
-
語義約定
語義約定 -
實現(xiàn)
-
關鍵：
要么[lo, mi)，要么(mi, hi]樟遣；hi - lo == 0時終止
實現(xiàn)
-
5.7 插值查找 Interpolation Search
-
原理
思路：按照個元素的概率分布來確定pivot（即mid）的取值
關鍵：秩的比例與值得比例一致
差值查找
舉個形象的??：比如我們事先知道，一本字典中每個字母的所有單詞所占的篇幅可能是一定的，比如說50頁，那么我們要查一個以b開頭的單詞時，不用將mid設為字典的重點或者黃金分割點來查作谭，可以將它設為字典中大概2/26的位置怨酝。 -
性能
最好：O(1)
最壞：O(N)
平均：O(lg(lgN))
缺點：易受到“干擾”
插值查找效率
問題規(guī)模以開方的方式遞減，這樣的復雜度如何分析？
【字寬折半分析法】
可以把n映射為為計算機中二進制數的字節(jié)長度lgN。因此，問題規(guī)模以開方的方式減少，相當于字節(jié)長度減半。因此相當于是在lgN的基礎上問題規(guī)模不斷減半，因此是lg(lgN)
5.8 關于各查找算法的使用
6 ?無序向量到有序向量：排序
6.1 冒泡排序 Bubble Sort
思路：無序部分在前，有序部分在后腕巡。有序部分不斷增加车伞，無序部分不斷減少。
實現(xiàn)1：掃描N次另玖，每次把掃描區(qū)間內最大的元素排在區(qū)間最后谦去。
缺點：必須掃描N次鳄哭，若區(qū)間內大部分元素是有序的話宣脉，則實際上沒比必要掃描這么多次谈跛。即掃描了一定次數后區(qū)間就已經有序了。-
改進1：掃描的過程中判斷掃描區(qū)間是否已經sorted塑陵，如果是阻桅，則不需要進一步掃描，可以及時退出兼都。
關鍵：利用一個標志sorted來說實現(xiàn)對掃描區(qū)間是否已經有序的判斷嫂沉。
冒泡排序-改進1 -
改進2：若區(qū)間的只有前一小部分是無序的，后綴一大部分是有序的扮碧，那么實際上只需要對前面這一小部分進行掃描交換趟章。
關鍵：hi跳過已經有序的后綴部分
冒泡排序-改進2 -
性能對比
- 效率：最好O(N)，最壞O(N^2)慎王。不同的算法只在各自的特例中才能有各自的優(yōu)勢蚓土。
- 穩(wěn)定性Stability：相同元素的相對順序是否能得到保證。
由于只有在大小差異的情況下才能有交換赖淤，因此是穩(wěn)定的蜀漆。
冒泡排序性能分析
6.2 歸并排序 Merge Sort
-
原理
利用分治的思想進行：排序 + 歸并
歸并排序原理 排序：利用遞歸知道遞歸基（即只含有1個元素）
-
二路歸并（2-way merge）
-
思想
二路歸并思路 -
實現(xiàn)
關鍵：3個指針i, j, k
i -> 合并向量A中待填充位置
j -> 子向量B中待比較元素的位置
k -> 子向量C中待比較元素的位置
二路歸并實現(xiàn) -
性能
最好與最壞：O(NlgN)
歸并排序性能
-
