快速分類演算法設計與分析

A. 結合二叉樹的快速排序演算法分析

對 3，9，1，6，5，4，8，2，10，7 進行從小到和悄遲大的快速排序

對於第一次遍歷，如下圖所示：

對應的二叉樹結果是：

那麼經過後幾次遍歷比較可以得到如下二叉樹：

這運灶時我們可以計算一下我們的快速排序演算法進行了多少次比較:

，即每個節點到根結點的距離之和。

由上例可知，快排可視為一個二叉樹構建的過程，那麼這個二叉樹構建的速度就決定了我們快排的效率。可以確定的是，對於同樣的數據元素在不同的原始排列條件下，構建的二叉樹越矮，則排序效率越高。

通過這一理論，我們可以更具體的分析其不同情況下的時間復雜度：

完全二叉樹滿足如下公式：

對於深度為h的完全二叉樹，若為滿二叉樹，比較次數為：

這里的葉子數量m與深度h的關系：

那麼葉子到根的距離d為：

即， ，

由於 為整數，即可認為 ，

而對於完全二叉樹來說，葉子數 ，與內點（帶有葉子節點的頂點）數 的關系為 ，則頂點數

那麼由上述公式可得：

即， ，時間復雜度為： 。

那麼若節點數為n，則：

，即時間復雜度為： 。

由於分割標準的選取概率完全相同，那麼可以得到平均比較次數為：

由於這里的 ，以及

由 ，以及 ，得：

令 ，得：

令 ，得：

令 ，得：

整理得：

由 ，故

則：喚李

即，

綜合來看，快排的時間復雜度最理想狀態與最糟糕狀態分別為 、 ，但是對於一般隨機情況而言時間復雜度仍為 。

B. 《演算法分析與設計》課程講什麼內容

《演算法分析與設計》課程是理論性與應用性並重的專業課程。本課程以演算法設計策略為知識單元，系統地介紹計算機演算法的設計方法和分析技巧。課程教學主要內容包括：第一章，演算法概述；第二章，遞歸與分治策略；第三章，動態規劃；第四章，貪心演算法；第五章，回溯法；第六章，分支限界法。通過介紹經典以及實用演算法讓同學掌握演算法設計的基本方法。結合實例分析，讓同學深入理解演算法設計的技巧，以及分析演算法的能力。

C. 演算法設計與分析的內容簡介

本書內容基本上涵蓋了目前程序設計競賽所要掌握的演算法，並在書後精選了部分ACM國際大學生程序設計競賽的題目，供大家練習。
本書可作為計算機科學系、數學系、軟體學院等專業本科及研究生課程的教材，特別適合於有志於參加程序設計競賽的學生學習和訓練。

D. 演算法設計與分析習題解答（第2版）的目錄

第1章演算法引論
習題1-1 實參交換
習題1-2 方法頭簽名
習題1-3 數組排序判定
習題1-4 函數的漸近表達式
習題1-5 O（1）和O（2）的區別
習題1-7 按漸近階排列表達式
習題1-8 演算法效率
習題1-9 硬體效率
習題1-10 函數漸近階
習題1-11 n！的階
習題1-12 平均情況下的計算時間復雜性
演算法實現題1-1 統計數字問題
演算法實現題1-2 字典序問題
演算法實現題1-3 最多約數問題
演算法實現題1-4 金幣陣列問題
演算法實現題1-5 最大間隙問題
第2章 遞歸與分治策略
習題2-1 Hanoi塔問題的非遞歸演算法
習題2-2 7個二分搜索演算法
習題2-3 改寫二分搜索演算法
習題2-4 大整數乘法的O（n1Og（3/2））演算法
習題2-5 5次7//3位整數的乘法
習題2-6 矩陣乘法
習題2-7 多項式乘積
習題2-8 不動點問題的O（1O9n）時間演算法．
習題2-9 主元素問題的線性時間演算法
習題2-10 無序集主元素問題的線性時間演算法
習題2-11 O（1）空間子數組換位演算法
習題2-12 O（1）空間合並演算法
習題2-13 n段合並排序演算法
習題2-14 自然合並排序演算法
習題2-15 最大值和最小值問題的最優演算法
習題2-16 最大值和次大值問題的最優演算法
習題2-17 整數集合排序
習題2-18 第k小元素問題的計算時間下界」
習題2-19 非增序快速排序演算法
習題2-20 隨機化演算法
習題2-21 隨機化快速排序演算法
習題2-22 隨機排列演算法」
習題2-23 演算法qSort中的尾遞歸
習題2-24 用棧模擬遞歸
習題2-25 演算法se1ect中的元素劃分
習題2-26 O（nlogn）時間快速排序演算法
習題2-27 最接近中位數的k個數
習題2-28 X和y的中位數
習題2-29 網路開關設計
習題2-32 帶權中位數問題
習題2-34 構造Gray碼的分治演算法
習題2-35 網球循環賽日程表
演算法實現題2-1 輸油管道問題（習題2-3O）
演算法實現題2-2 眾數問題（習題2-31）
演算法實現題2-3 郵局選址問題（習題2-32）
演算法實現題2-4 馬的Hami1tOn周遊路線問題（習題2-33）
演算法實現題2-5 半數集問題
演算法實現題2-6 半數單集問題
演算法實現題2-7 士兵站隊問題
演算法實現題2-8 有重復元素的排列問題
演算法實現題2-9 排列的字典序問題
……
第3章 動態規劃
第4章 貪心演算法
第5章 回溯法
第6章 分支限界法
第7章 概率演算法
第8章 NP完全性理論
第9章 近似演算法
第10章演算法優化策略
第11章 在線演算法設計