演算法分析與設計導論答案

Ⅰ 《演算法導論》第三章-思考題（參考答案）

（多項式的漸進行為） 假設 是一個關於 的 次多項式，其中 ， 是一個常量。使用漸進符號的定義來證明下面的性質。

a. 若 ，則 。

b. 若 ，則 。

c. 若 ，則 。

d. 若 ，則 。

e. 若 ，則 。

已知： ，易得 。

故 。

情況 1：

，即： 。

故 。

情況 2：

，即： 。

故 。

情況 3：

，即： 。

故 。

情況 4：

，即： 。

故 。

情況 5：

，即： 。

故 。

（相對漸進增長） 為下表中的每對表達式 指出 是否是 的 或 。假設 且 均為常量。回答應以表格的形式，將「是」或「否」寫在每個空格中。

a.

令 代替 ，並令 代替 a，可得：

即： 。

又：若 。故： 。

b.

故， 。

令 。故 。

c.

。又 的值為在區間 中波動，故 與 無任何關系

d.

嚴格遞增，故對於任意正常量 ，總存在 ，使得 ，即：

也易證：故對於任意正常量 ，總存在 ，使得 ，即：

e.

。故 。

f.

故，

又， 是嚴格遞增的函數。故，

故， ，也即

也即

（根據漸進增長率排序）

a. 根據增長的階來排序下面的函數，即求出滿足 的函數的一種排列 。把你的表劃分成等價類，使得函數 和 在相同類中當且僅當 。

b.給出非負函數 的一個例子，使得對所有在（a）部分中的函數 ， 既不是 也不是 。

（漸進記號的性質） 假設 和 為漸進正函數。證明或反駁下面的每個猜測。

a. 蘊含 。

錯。例如： 。

b. 。

錯。例如： 。

c. 蘊含 ，其中對所有足夠大的 ，有 且 。

正確。

對於足夠大的 ，有 ；且 ，則存在正常量 ，使得 ，有

​

​

又 ，故當 ，且 足夠大，有：

​

故原問題成立。

d. 蘊含 。

錯。例如： 。

e. 。

當 時， ；其他條件下，不成立。

f. 蘊含 。

正確。 ，即存在正常量 ，使得 ，有

​ ，即

令 ，得 。

g. 。

錯。例如： 。

h. 。

正確。

易得， ，即存在正常量 ，使得 ，都有 。

令 ，即存在正常量 ，使得 ，都有 。

令 ，則 ，有 。

即 。

（ 與 的一些變形） 某些作者用一種與我們稍微不同的方式來定義 ；假設我們使用 （讀作「 無窮」）來標識這種可選的定義。若存在正常量 ，使得對無窮多個整數 ，有 ，則稱 。

a. 證明：對漸進非負的任意兩個函數 和 ，或者 或者 或者二者均成立，然而，如果使用 來代替 ，那麼該命題並不為真。

主要缺少了 這個條件；則若 ，必然有無窮多個正整數 ，使得 成立；

若 ，則上述兩者均成立；

反例： ，但 。

b. 描述用 代替 來刻畫程序運行時間的潛在優點與缺點。

優點： 對下屆的要求更寬松，可以兼容更多的情況；

缺點： 並非嚴格的漸進下界。因此實際意義並不大。

​ 某些作者也用一種稍微不同的方式來定義 ；假設使用 來標識這種可選的定義。我們稱 當且僅當 。

c. 如果使用 代替 但仍然使用 ，定理 3.1 中的「當且僅當」的每個方向將出現什麼情況？

沒有變化。 成立意味著 漸進非負，故 。

​ 有些作者定義 （讀作「軟 」）來意指忽略對數因子的 ：

：存在正常量 和 ，使得對所有 ，有 。

d. 用一種類似的方式定義 和 。證明與定理 3.1 相對應的類似結論。

：存在正常量 和 ，使得對所有 ，有 。

：存在正常量 和 ，使得對所有 ，有 。

（多重函數） 我們可以把用於函數 中的多重操作符 * 應用於實數集上的任意單調遞增函數 。對給定的常量 ，我們定義多重函數 為

​

該函數不必再所有情況下都是良定義的。換句話說，值 是為縮小其參數到 或更小所需函數 重復應用的數目。

​ 對如下每個函數 和常量 ，給出 的一個盡量緊確的界。

Ⅱ 演算法設計與分析習題解答（第2版）的內容提要

《演算法設計與分析習題解答》（第2版）是清華大學出版社出版的普通高等教育「十一五」國家級規劃教材《演算法設計與分析（第2版）》（主教材）配套的輔助教材，對《演算法設計與分析（第2版）》一書中的全部習題做了詳盡的解答。《演算法設計與分析習題解答》（第2版）的內容是對《演算法設計與分析（第2版）》的較深入的擴展，許多在主教材中無法講述的、較深入的主題通過習題的形式展現出來。為了加強學生靈活運用演算法設計策略解決實際問題的能力，《演算法設計與分析習題解答》（第2版）將主教材中的許多習題改造成演算法實現題，要求學生不僅設計出解決具體問題的演算法，而且能夠上機實現。作者的教學實踐反映出這類演算法實現題的教學效果非常好。作者還結合國家精品課程建設，進行了教材的立體化開發，包括主教材、輔助教材、實驗與設計、電子課件和教學網站建設。
《演算法設計與分析習題解答》（第2版）內容豐富，觀點新穎，理論聯系實際。不僅可以用作高等學校計算機科學與技術學科各專業本科生和研究生學習計算機演算法設計的輔助教材，而且也適合廣大工程技術人員和自學讀者學習參考。

Ⅲ 《計算機演算法設計與分析第5版習題及答案》pdf下載在線閱讀全文，求百度網盤雲資源

《計算機演算法設計與分析第5版習題及答案》網路網盤pdf最新全集下載:
鏈接：https://pan..com/s/1oxH2d3SdEUN0rx6LJRNBoA

Ⅳ 演算法設計與分析 試題求答案.求解遞歸方程T(n)=5T( n/3)+n.;

T(n)=1/10 ((2 c_1+15) 5^((log(n))/(log(3)))-15 n)
c_1是一個常數,需要初始值確定