數(shù)據(jù)結(jié)構(gòu)時(shí)間復(fù)雜度總匯

1、(1) 冒泡排序冒泡排序就是把小的元素往前調(diào)或者把大的元素往后調(diào)。 比較是相鄰的兩個(gè)元素比較， 交換也發(fā)生在這兩個(gè)元素之間。 所以相同元素的前后順序并沒有改變， 所以冒泡排序是一種 穩(wěn)定 排序算法。(2) 選擇排序選擇排序是給每個(gè)位置選擇當(dāng)前元素最小的，比如給第一個(gè)位置選擇最小的。例子說明好多了。序列 5 8 5 2 9， 我們知道第一遍選擇第 1個(gè)元素 5會和 2 交換，那么原序 列中 2個(gè) 5的相對前后順序就被破壞了， 所以選擇排序 不穩(wěn)定 的排序算法。(3) 插入排序 插入排序是在一個(gè)已經(jīng)有序的小序列的基礎(chǔ)上，一次插入一個(gè)元素。比較是從有序序列的末尾開始， 也就是想要插入的元素和已經(jīng)有序

2、的最大者開始比起， 如果比它大則直接插入 在其后面， 否則一直往前找直到找到它該插入的位置。 如果和插入元素相等， 那么插入元素 把想插入的元素放在相等元素的后面。 所以， 相等元素的前后順序沒有改變。 所以插入排序 是 穩(wěn)定 的。(4) 快速排序快速排序有兩個(gè)方向，左邊的 i 下標(biāo)一直往右走(往后)，當(dāng) ai <= acenter_index ， 其中center_index是中樞元素的數(shù)組下標(biāo)，一般取為數(shù)組第0個(gè)元素。而右邊的j下標(biāo)一直往左走(往前)，當(dāng) aj > acenter_index 。如果 i 和 j 都走不動了， i <= j, 交換 ai 和 aj, 重復(fù)上

3、面的過程， 直到i>j。交換aj和acenter_index,完成一趟快速排序。在中樞元素和aj交換的時(shí)候，很有可能把前面的元素的穩(wěn)定性打亂，比如序列為5 3 3 4 3 8 9 10 11 ,現(xiàn)在中樞元素 5和 3(第 5個(gè)元素，下標(biāo)從 1 開始計(jì))交換就會把元素 3的穩(wěn)定性打亂，所以快 速排序是一個(gè)不穩(wěn)定的排序算法。(不穩(wěn)定發(fā)生在中樞元素和aj交換的時(shí)刻)(5) 歸并排序歸并排序是把序列遞歸地分成短序列，遞歸出口是短序列只有1 個(gè)元素 (認(rèn)為直接有序 )或者 2 個(gè)序列 (1 次比較和交換 ),然后把各個(gè)有序的段序列合并成一個(gè)有序的長序列。不斷合并直到原序列全部排好序。相等時(shí)不發(fā)生交

4、換。所以，歸并排序也是穩(wěn)定的排序算法。(6) 基數(shù)排序基數(shù)排序是按照低位先排序，然后收集；再按照高位排序，然后再收集；依次類推，直到 最高位。有時(shí)候有些屬性是有優(yōu)先級順序的， 先按低優(yōu)先級排序， 再按高優(yōu)先級排序， 最后 的次序就是高優(yōu)先級高的在前， 高優(yōu)先級相同的低優(yōu)先級高的在前。 基數(shù)排序基于分別排序， 分別收集，所以其是 穩(wěn)定的排序算法。(7) 希爾排序 (shell)希爾排序是按照不同步長對元素進(jìn)行插入排序，當(dāng)剛開始元素很無序的時(shí)候，步長最大， 所以插入排序的元素個(gè)數(shù)很少， 速度很快；當(dāng)元素基本有序了，步長很小， 插入排序?qū)τ谟?序的序列效率很高。所以，希爾排序的時(shí)間復(fù)雜度會比o(n

5、A2)好一些。由于多次插入排序，我們知道一次插入排序是穩(wěn)定的， 不會改變相同元素的相對順序， 但在不同的插入排序過程 中，相同的元素可能在各自的插入排序中移動，最后其穩(wěn)定性就會被打亂，所以shell 排序是不穩(wěn)定 的。(8) 堆排序我們知道堆的結(jié)構(gòu)是節(jié)點(diǎn) i 的孩子為 2*i 和 2*i+1 節(jié)點(diǎn)，大頂堆要求父節(jié)點(diǎn)大于等于其 2 個(gè)子節(jié)點(diǎn)， 小頂堆要求父節(jié)點(diǎn)小于等于其 2 個(gè)子節(jié)點(diǎn)。 在一個(gè)長為 n 的序列， 堆排序的過程 是從第 n/2 開始和其子節(jié)點(diǎn)共 3 個(gè)值選擇最大 (大頂堆 )或者最小 (小頂堆 ),這 3 個(gè)元素之間的 選擇當(dāng)然不會破壞穩(wěn)定性。 但當(dāng)為 n/2-1, n/2-2,

6、.1 這些個(gè)父節(jié)點(diǎn)選擇元素時(shí)， 就會破壞穩(wěn)定一、排序排序法平均時(shí)間最差情形穩(wěn)定度冒泡0(n2)0(n2)交換0(n2)0(n2)選擇0(n2)0(n2)插入O(nj20(n )排序時(shí)較好Shell0( nlogn)s0(n ) 1<s<2不穩(wěn)定快速0( nlogn)0(n2)歸并0( nlogn)0( nlog n)穩(wěn)定堆0( nlogn)0( nlogn)不穩(wěn)定基數(shù)0(log rB)0(log rB)穩(wěn)定不穩(wěn)定的排序算法額外空間備注穩(wěn)定0(1)n小時(shí)較好不穩(wěn)定0(1)n小時(shí)較好不穩(wěn)定0(1)n小時(shí)較好穩(wěn)定0(1)大部分已0(1)s是所選分組不穩(wěn)定O(nlogn)n大時(shí)較好0(1)

7、n大時(shí)較好0(1)n大時(shí)較好0(n)B是真數(shù)(0-9)，R是基數(shù)(個(gè)十百)性。有可能第n/2個(gè)父節(jié)點(diǎn)交換把后面一個(gè)元素交換過去了，而第n/2-1個(gè)父節(jié)點(diǎn)把后面一所以，堆排序是個(gè)相同的元素沒有交換， 那么這2個(gè)相同的元素之間的穩(wěn)定性就被破壞了。二、查找二分法平均查找效率是O(logn)，但是需要數(shù)組是排序的。如果沒有排過序，就只好先用0(nlogn)的預(yù)處理為它排個(gè)序了。而且它的插入比較困難，經(jīng)常需要移動整個(gè)數(shù)組，所以動 態(tài)的情況下比較慢。哈希查找理想的插入和查找效率是0(1)，但條件是需要找到一個(gè)良好的散列函數(shù)，使得分配較為平均。另外，哈希表需要較大的空間，至少要比0(n)大幾倍，否則產(chǎn)生沖突

8、的概率很高。二叉排序樹查找也是 O(logn)的，關(guān)鍵是插入值時(shí)需要做一些處理使得它較為平衡(否則容 易出現(xiàn)輕重的不平衡，查找效率最壞會降到0(n),而且寫起來稍微麻煩一些，具體的算法你可以隨便找一本介紹數(shù)據(jù)結(jié)構(gòu)的書看看。當(dāng)然，如果你用的是c語言，直接利用它的庫類型map multimap就可以了，它是用紅黑樹實(shí)現(xiàn)的，理論上插入、查找時(shí)間都是O(logn)，很方便，不過一般會比自己實(shí)現(xiàn)的二叉平衡樹稍微慢一些。三樹圖克魯斯卡爾算法的時(shí)間復(fù)雜度為0 (eloge)普里姆算法的時(shí)間復(fù)雜度為0 (n2)迪杰斯特拉算法的時(shí)間復(fù)雜度為0 (n2)拓?fù)渑判蛩惴ǖ臅r(shí)間復(fù)雜度為 0 (n+e) 關(guān)鍵路徑算法的時(shí)間復(fù)雜度為 0 (n+e)8. 從具有 n 個(gè)結(jié)點(diǎn)的二叉排序樹中查找一個(gè)元素時(shí)，在平均情況下的時(shí)間復(fù)雜度大致為 ( c ) 。A. O(n) B. O(1) C. O(log2n)D. O(n2)9. 從具有 n 個(gè)結(jié)點(diǎn)的二叉排序樹中查找一個(gè)元素時(shí)，在最壞情況下的時(shí)間復(fù)雜度為 ( a ) 。A. O(n) B. O(1) C. O(log2n)D. O(n2)2.根據(jù) n 個(gè)元素建立一棵二叉排序樹，其時(shí)間復(fù)雜度大致為(b)2A. O(n) B. O(n