演算法設計與分析第二版

Ⅰ 演算法設計與分析習題解答（第2版）的介紹

《演算法設計與分析習題解答》（第2版）是清華大學出版社出版的普通高等教育「十一五」國家級規劃教材《演算法設計與分析（第2版）》（主教材）配套的輔助教材，對《演算法設計與分析（第2版）》一書中的全部習題做了詳盡的解答。

Ⅱ 計算機演算法設計與分析 王曉東第二版與第三版的差別

增加了一些內容如下：為突出教材的可讀性和可用性，章首增加了學習要點提示；章末配有難易適度的習題，分為演算法分析題和演算法實現題兩部分；配套出版了《演算法設計與實驗題解》；並免費提供電子課件和教學網站服務。

Ⅲ 快速排序的演算法復雜度分析

原文地址：
快速排序的演算法復雜度分析
以下是快排的java演算法：

大家都知道快排的時間復雜度是O(n*ln[n])，那麼這個復雜度是如何計算出來的呢？

最好的情況下，每次劃分對一個記錄定位後，要記錄的左側子序列與右側子序列的長度相同。在具有n個記錄的序列中，一次劃分需要對整個待劃分序列掃描一遍，所需的時間為O(n)。

設 是對n個記錄的序列進行排序的時間，每次劃分後，正好把劃分區域分為長度相等的連個子序列，顯然T(0)=T(1) =1,則有：

最壞的情況下，待排序的記錄序列正序或逆序，每次劃分只能得到一個比上一次劃分少一個記錄的子序列，（另一個子序列為空）。此時，必須經過n-1次遞歸調用才能把所有記錄定位，而且第i趟劃分需要經過n-i次比較才能找個才能找到第i個記錄的位置，因此時間復雜度為

平均情況下，設軸值記錄的關鍵碼第k小（1≤k≤n）,則有：

由上式可推出如下兩式：

兩式相減,然後兩邊同除以n(n+1)得

又因為f(n)單調遞減，單調有界數列極限定理，所以f(n)有界

此數稱為歐拉常數，

約為 0.57721566490153286060651209

所以

所以

**如果有何處不當，請不吝賜教，一定多加完善。謝謝 **

參考資料：

【1】《演算法設計與分析》第二版 王紅梅

Ⅳ 演算法設計與分析習題解答（第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章 在線演算法設計