## 常數操作 **一個操作 如果和數據量沒有關系，每次都是固定時間內完成，叫做常數操作。** > 如做加減操作，數組尋址等。 ## 時間復雜度 **一個算法流程中，常數操作數量的指標** ## 空間復雜度 **一個算法流程中，多申請的內存空間的指標** > 如： 多開一個為n的輔助數組：O(n) 多開一個輔助的二維數組：O(n^2) 多開常數空間(如臨時變量)：O(1) 注：遞歸調用是有空間代價的遞歸深度有多少 空間復雜度就有多少 ## 對數器  條件及元素： 1. 已知一個簡單的絕對正確的算法A 2. 需要測試的算法B 3. 輸入盡量隨機，數據規模盡量大的樣本 4. 如果A和B的輸出結果一致，則能確定算法B也是正確的 ## master公式 遞歸的時間復雜度公式：`T(n) = a * T(n/b) + O(n^d) `   ## 快速排序 1.0：選最右邊位置，小于或者等于的數放左邊，大的放右邊 2.0：選最右邊位置，小于放左邊，等于放中間，大于放右邊（荷蘭國旗問題） 3.0：隨機選擇位置，小于放左邊，等于放中間，大于放右邊（優化哨兵） ## 堆排序 ### 堆結構 堆是一顆完全二叉樹。 大根堆：父節點大于孩子節點 小根堆：父節點小于孩子節點 如果用數組實現堆結構，則下標關系滿足：（對于下標i位置） 父節點：`(i-1)/2` 左孩子：`2*i+1` 右孩子：`2*i+2` 堆操作： 入堆：heapInsert 堆化：heapify ### 排序 先將數組一次入堆，然后堆頂依次出堆，即可完成排序。 ## 比較器（Java內） 返回負數，第一個數排前面； 返回正數，第二個數排前面； ## 計數排序 統計次頻count，按順序一次打印，即可完成排序。  ## 基數排序 如果是十進制數排序，則用10個桶（是隊列，先進先出）： 1. 先對個位數入桶，然后出桶 2. 再對十位數入桶，然后出桶 3. 再對百位數入桶，然后出桶 4. 依次類推，最后有序