① 《算法导论》第二版和第三版的区别大吗有中文版的吗
第三版比第二版去掉了几章，例如排序网络之类的冷门算法，加入了并行算法等热门的内容。
动态规划这一章做了些修改，论述的内容不变，就是选的例子更好一些。
另外第三版更新了一些习题和思考题，所以习题编号肯定有变化。说实话，思考题才是此书最精彩的地方，但是一般人看《算法导论》，能把前面的算法描述搞清楚就不错了，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章..讲得很清楚
⑨ 算法导论第三版第十章怎么没有答案
第三版要好些，调整了一部分内容顺序让人更好接受，层次递进由易到难更合理些。不过如果你不习惯英文书就还是看第二版没有关系的，第三版暂时没有权威中译版。而且相对来说，内容的变化并不是非常大，即使看第二版也不会有太大影响。