① 《演算法導論》第二版和第三版的區別大嗎有中文版的嗎
第三版比第二版去掉了幾章，例如排序網路之類的冷門演算法，加入了並行演算法等熱門的內容。
動態規劃這一章做了些修改，論述的內容不變，就是選的例子更好一些。
另外第三版更新了一些習題和思考題，所以習題編號肯定有變化。說實話，思考題才是此書最精彩的地方，但是一般人看《演算法導論》，能把前面的演算法描述搞清楚就不錯了，90%的讀者會略過演算法復雜度分析部分，而最後的每一章的思考題部分，99%的讀者都不會去看的。
因為之前看過第二版的大部分，所以我第三版讀起來沒有太多障礙。
如果你能把思考題都解決了，你在簡歷上寫個精通《演算法導論》也是理直氣壯的。
② 演算法導論 第二版 第三版的區別
第三版比第二版去掉了幾章，例如排序網路之類的冷門演算法，加入了並行演算法等熱門的內容。
動態規劃這一章做了些修改，論述的內容不變，就是選的例子更好一些。
另外第三版更新了一些習題和思考題，所以習題編號肯定有變化。說實話，思考題才是此書最精彩的地方，但是一般人看《演算法導論》，能把前面的演算法描述搞清楚就不錯了，90%的讀者會略過演算法復雜度分析部分，而最後的每一章的思考題部分，99%的讀者都不會去看的。
因為之前看過第二版的大部分，所以我第三版讀起來沒有太多障礙。
如果你能把思考題都解決了，你在簡歷上寫個精通《演算法導論》也是理直氣壯的。
③ 求演算法導論16章3-5，3-8的答案
3-8 Show that we cannot expect to compress a file of randomly chosen bits. Notice that the number of possible source files S using n bits and compressed files E using n bits is 2n+1 - 1. Since any compression algorithm must assign each element s 屬於 S to a distinct element e 屬於 E the algorithm cannot hope to actually compress the source file.
④ 《演算法導論》第三章-思考題（參考答案）
（多項式的漸進行為） 假設 是一個關於 的 次多項式，其中 ， 是一個常量。使用漸進符號的定義來證明下面的性質。
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 相對應的類似結論。
：存在正常量 和 ，使得對所有 ，有 。
：存在正常量 和 ，使得對所有 ，有 。
（多重函數） 我們可以把用於函數 中的多重操作符 * 應用於實數集上的任意單調遞增函數 。對給定的常量 ，我們定義多重函數 為
該函數不必再所有情況下都是良定義的。換句話說，值 是為縮小其參數到 或更小所需函數 重復應用的數目。
對如下每個函數 和常量 ，給出 的一個盡量緊確的界。
⑤ 《演算法導論》第二章-思考題（參考答案）
插入排序的漸進時間復雜度為 ，也即 。所以對於 個長度為 的數組，總代價為：
此時，遞歸樹高為 ，除最後一層外其餘層的代價為 ；最後一層代價為 。故，合並子表的總代價為：
故 ；當 時， 相對 被忽略；故 的最大值為 。
選擇插入排序比合並排序快的最大列表長度。
證明 BUBBLESORT 的正確性，除了證明不等式（2.3），還需要證明 A′ 中的元素全部來自於 A。
內循環-循環不變式 ：for 循環每次迭代開始，子數組 A[j..A.length] 中第 j 個元素是最小的，即 A[j] <= A[k], k > j；同時元素 A[j..A.length] 是原來在位置 j 到 A.length的元素，但是已經挑選出最小元素的。
初始化 ： 第一次循環迭代之前（當 j = A.length 時），循環不變式成立。因為此時循環不變式中只有一個元素，也是最小元素。
保持 ： 假設此次迭代之前，有循環不變式 A[j..A.length] 為真。則再次進入循環體，我們檢查 A[j], A[j − 1] 的大小，並保持了 j − 1 位置為 A[j], A[j − 1] 中最小的一個。由於已經有 A[j] 為 A[j..A.length] 中最小的元素了，所以 A[j − 1] 也應為 A[j − 1..A.length] 中最小的元素。此時子數組 A[j - 1..A.length] 是由原來 A[j - 1..A.length] 中的元素組成的。那麼 for 循環這次迭代增加位於 j - 1 的元素保持了循環不變式。
終止 ： 循環終止時，j = i + 1。也就是 A[i..A.length] 是由原來 A[i..A.length] 元素組成，但已經挑選出最小的元素，且最小元素為 A[i]。
外循環-循環不變式： for 循環每次迭代開始，A[1..i − 1] 構成升序數組，且剩餘子數組 A[i..A.length] 中的元素都大於等於 A[i − 1]。
初始化 ： 第一次循環迭代之前（當 i = 1 時），此時數組 A[1..i - 1] 為空數組，故循環不變式成立。
保持 ： 假設第 i 次迭代之前，循環不變式成立，即 A[1..i−1] 已排好序，且剩餘子數組 A[i..A.lenght] 中的元素都大於等於 A[i - 1]。則再次進入循環體，根據 b 可得，A[i..A.length] 是由原來 A[i..A.length] 元素組成，但已經挑選出最小的元素，且最小元素為 A[i]。故 A[1..i] 也已升序排好，且 A[i + 1..A.length] 中的元素均大於 A[i]。
終止 ： 循環終止時，i = A.length - 1。也就是 A[1..A.length - 1] 已升序，且 A[A.length] 大於 A[1..A.length - 1] 中的任意一個元素；所以 A[1..A.length] 已排好升序。
最壞情況運行時間和插入排序一樣，都是 。
但是插入排序最好情況運行時間為 ，即只執行 n - 1 次比較；冒泡排序的比較次數則沒有減少，故時間復雜度仍為 。
同時，若使用數組數據結構，則冒泡排序與插入排序的交換操作數量一致，均為逆序對數；但若使用鏈表數據結構的話，其交換操作會比插入操作數量多很多。
故，冒泡排序所需的平均運行時間比插入排序多的多。
運行時間為： 。比霍納規則相比要慢。
可以優化一下：
。與霍納規則相同。
初始化 ：在第一次迭代之前， i = n，y = 0，滿足條件。
保持 ：第 i 次迭代， 。
終止 ：i = -1，則 ，滿足題意。
可根據 c 中循環不變式的終止段，得出該結論。
{2, 1}, {3, 1}, {8, 6}, {8, 1}, {6, 1}
降序集合 {n, n - 1, ..., 1} 具有最多的逆序對。逆序對數量： 。
逆序對數量即為 while 循環內的交換操作數量。也就是有多少個逆序對，就要執行多少次 while 內循環。所以，含有逆序對的數組排序時間為 ，其中 d 為數組中含有逆序對的數量。
⑥ 演算法導論上31章數論演算法的證明題
由ed=1(mod φ(n))，可設 ed = k*φ(n)+1，k∈Z
由e = 3，0<d<φ(n)得：0<ed<3*φ(n)
因此 0 < k*φ(n)+1 < 3*φ(n)，0<k<3，k=1或2
即 ed = φ(n)+1 或 ed = 2φ(n)+1，φ(n) = ed-1或φ(n) = 2ed-1
現已知φ(n)=(p-1)(q-1)和n=pq
可求得 p+q=n+1-φ(n)
即 p,q 是方程 x² - (n+1-φ(n)) x + n = 0的兩根
可解得：p,q = ((n+1-φ(n) ± √((n+1-φ(n))²-4n)) / 2
以上計算僅涉及n, d, e的有限次加減乘除和開方運算。
每種運算都能夠在關於n的位數的多項式時間內完成。
（設n的位數是d，加減法和除2運算可在O(d)時間內完成，乘法可在O(d²)時間內完成，
開方模擬手算也可以在O(d²)時間內完成）
因此能夠在關於n的位數的多項式時間內對Alice的模n進行分解。
⑦ 誰有演算法概論的習題答案（Algorithms)
http://blog.163.com/lancelotds/blog/static/11371583420096134752720/
我在別人的博客上找得哦！
⑧ MST性質證明。疑問
你對MST的割定理裡面有一個重要前提沒有顧及到
找安全邊需要割不妨礙邊集U及邊集V，且U,V都屬於生成樹T
這時，因為T聯通，所以U，V之間有且只有一條邊通過割.
這時就不存在有兩條紫邊都在T內的情況
於是就不存在你所說的情況了
有關這一部分..你可以參考一下演算法導論第23章..講得很清楚
⑨ 演算法導論第三版第十章怎麼沒有答案
第三版要好些，調整了一部分內容順序讓人更好接受，層次遞進由易到難更合理些。不過如果你不習慣英文書就還是看第二版沒有關系的，第三版暫時沒有權威中譯版。而且相對來說，內容的變化並不是非常大，即使看第二版也不會有太大影響。