演算法設計與分析第二版-ag真人国际官网
ⅰ 演算法設計與分析習題解答(第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章 在線演算法設計