算法
（1）一個算法應該具有以下五個重要的特征：
1、有窮性（Finiteness）
2、确切性(Definiteness) 算法的每一步驟必須有确切的定義；
3、輸入項(Input)
一個算法有0個或多個輸入，以刻畫運算對象的初始情況，所謂0個輸入是指算法本身定出了初始條件；
4、輸出項(Output)
一個算法有一個或多個輸出，以反映對輸入資料加工後的結果。沒有輸出的算法是毫無意義的；
5、可行性(Effectiveness)
算法中執行的任何計算步都是可以被分解為基本的可執行的操作步，即每個計算步都可以在有限時間内完成。（也稱之為有效性）
（2）算法原地工作的含義是指不需要任何額外的輔助空間 (x).
算法原地工作的含義是指不需要任何額外的輔助,算法所需要的輔助空間不随着問題的規模而變化，是一個确定的值。
1.複雜度
(1) 折半查找與二進制查找樹的時間性能在最壞的情況下是相同的(x)
數列有序，樹隻有左孩子或隻有右孩子，退化為線性表。
(2) 假設某算法的計算時間可用遞推關系式T(n)=2T(n/2)+n表示，則該算法的時間複雜度為（）
O(n*logn)
T(n)=
2^k*(T(n/(2^k)))+2^(k-1)*n/(2^(k-1))+2^(k-2)*n/(2^(k-2))+ ··· +2^0*n/(2^0))
= 2^k*(T(n/(2^k)))+k*n
令2^k = n,則k = log(n) (以2為底)
T(n)= n*T(1)+n*log(n)<= c*n*log(n) (c為常數）
是以是O(n*logn)
P: 能在多項式時間内解決的問題
NP: 不能在多項式時間内解決或不确定能不能在多項式時間内解決，但能在多項式時間驗證的問題
NPC: NP完全問題，所有NP問題在多項式時間内都能約化(Reducibility)到它的NP問題 ，即解決了此NPC問題，所有NP問題也都得到解決。NP ——> NP屬于NPC
NP hard: NP難問題， 所有NP問題在多項式時間内都能約化(Reducibility)到它的問題(不一定是NP問題)。NP ——> NP hard
2.排序
元素的移動次數與關鍵字的初始排列次序無關的是：基數排序
元素的比較次數與初始序列無關是：選擇排序
算法的時間複雜度與初始序列無關的是：選擇排序
排序算法的穩定性
- 不穩定：快選堆希
- 穩 定 ： 插冒歸基
與資料有序與否的關系：
與資料排序無關的有：
基選歸堆
- 直接插入排序是資料越有序越快，最快時間複雜度可達到O(n) .
- 選擇排序無論何時都是O（n^2）
- 快速排序越有序越慢
基于比較的排序算法的平均時間複雜度最少為？
1、基于比較的排序算法有：（1）直接插入排序；（2）冒泡排序；（3）簡單選擇排序；（4）希爾排序；（5）快速排序；（6）堆排序；（7）歸并排序。
2、基數排序、桶排序都屬于配置設定式排序，且都是穩定排序算法。
不能低于O(NlogN)
N個數有N!個可能的排列情況，也就是說基于比較的排序算法的判定樹有N!個葉子結點，比較次數至少為log(N!)=O(NlogN)。
總結：
堆排序最壞情況下比較次數為 O(nlog2n) ，
快速排序、簡單插入排序、冒泡排序最壞情況下比較次數為 n(n-1)/2 。
1.外部排序
指的是大檔案的排序，即待排序的記錄存儲在外存儲器上，待排序的檔案無法一次裝入記憶體，需要在記憶體和外部存儲器之間進行多次資料交換，以達到排序整個檔案的目的。
一般用歸并排序, 空間複雜度是O（n）。
2.初始序列有序時，快速排序效率最低。
3.折半查找屬于随機通路特性 連結清單不行
- 折半查找表必須有序,表可以順序方式存儲,也可以連結清單方式存儲（x）
4.拓撲排序
http://blog.csdn.net/lisonglisonglisong/article/details/45543451
在圖論中，拓撲排序（Topological Sorting）是一個有向無環圖（DAG, Directed Acyclic Graph）的所有頂點的線性序列。
該序列必須滿足下面兩個條件：
- 每個頂點出現且隻出現一次。
- 若存在一條從頂點 A 到頂點 B 的路徑，那麼在序列中頂點 A 出現在頂點 B 的前面。
有向無環圖（DAG）才有拓撲排序，非DAG圖沒有拓撲排序一說。
通常，一個有向無環圖可以有一個或多個拓撲排序序列。
拓撲排序通常用來“排序”具有依賴關系的任務。
拓撲排序還可以采用 深度優先搜尋（DFS）的思想來實作
題目：
1) 在用鄰接表表示圖時，拓撲排序算法時間複雜度為 o(n+e);
3.檢索
分塊查找
資料分成若幹塊
每塊内資料不必有序,但塊間必須有序
每塊内最大(或最小)的資料組成索引塊