算法导论题解

㈠ 算法导论 习题

将集合排序，复杂度O(nlogn)。
从小到大遍历整个数组的每个数i，计算出X-i是否存在，复杂度O(n)。
于是就是复杂度O(nlogn) + O(n) = O(nlogn)

㈡ 关于<算法导论>这本书的一些问题(主要针对oi)

1没必要，太难了，主要都是理论知识。考noi都可以不需要看呢。主要是讲算法的，但是理论多实践少，例题也少
2一般来说英语要求不是很高呢，但是数学好会有点优势（不单单是看书，还有整一个竞赛），最好数学竞赛的内容学一点。高代会很有用。
3说实话啊，算法只要会用就可以了不需要太严格证明的，而且一般高级算法要证明的话需要很强大的数学基础啊，像我们学校以前一个国家集训队的学生，他搞懂那些证明都是找我们学校数学进国家集训队的同学讨论的。你买的话，看《奥赛经典》系列和《全国青少年信息学奥林匹克竞赛培训教程》系列吧，通俗易懂
4实力运气和心态

㈢ [算法导论]根据渐近增长率排序

参考网上的一篇博客，经过整理汇总成下面这个表，请参考指正。

㈣ 算法导论上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进行分解。

㈤ 算法导论里面的大师解法是什么 用大师解法计算下面递归表达式的时间复杂度. T(n)=2T(n/2) + Θ(n^0.1)

#a i从0循环到n，算法复杂度为O(n)。
#b 一共要做n^2/2次加法，算法复杂度为O(n^2)。
#c 要求一个k，满足2^k>=n ，算法复杂度为O(log(n))
#d 注意到这个函数做的事跟#c的函数恰好相反，算法复杂度相同，也是O(log(n))
#e 因为已算出#g每次做3(n-3)次加法，那么i从1到n，一共做2/3*(n^2-5n+6)次加法，所以复杂度为O(n^2)。
#f 这个函数可以写成公式T(n)=T(n-2)+T(n-1)，这个递归式跟黄金分割有关系，解这个递归式，可以知道 T(n) = O((√5-1/2)^n)
#g 函数调用一共做3(n-3)次加法，所以复杂度为O(n)
PenitentSin 这位兄台的#c 算的不对啦，#g也不对。还有#f，这个虽然是递归，但不是递归就等于指数级的复杂度，要解递归方程才能断定的。
关于算法复杂度，《算法导论》一书中第四章有一个主定理，记住这个定理之后，这些问题就小case了（除了复杂递归之外）。

㈥ 解答算法导论问题8-2

a.Counting sort
b.Similiar to parition procere, traverse and swap 1,0
c.Quicksort
d.Use a or b, each time the sorting method uses O(n), there is b-bit, so the total time is O(bn)
e.Not stable
int[] c = new int[k + 1];
int i = 0;
for (; i < c.length; ++i) {
c[i] = 0;
}
for (i = 0; i < a.length; ++i) {
++c[a[i]];
}
for (i = 1; i < c.length; ++i) {
c[i] += c[i - 1];
}
for (i = k; i >= 1; --i) {
a[c[i] - 1] = i;
--c[i];
}

㈦ 《算法导论》第三版 16.3-9怎么解啊望高手指点！

对于一个k字节的文件而言，合理的压缩应该得到一个不超过k字节的文件，也就是说我们假定对于任何一个文件压缩结果都不能变长
然后考虑所有长度不超过k字节的文件，这样的文件总共有T=256^k+256^{k-1}+...+256+1个，它们两两不同，总长度是L=k*256^k+(k-1)*256^{k-1}+...+1*256+0*1
把这些文件每个都压缩一下，得到T个新的文件总长度不超过L，且也必须两两不同（否则无法解压），真正的压缩结果应该得到总长度严格小于L的情况
但是由排序不等式知L是优化问题 min sum x_j*256^j 在约束条件0<=x_j<=256^j且 sum x_j=T 的最优解（这里0<=j<=k），取到这个最优解当且仅当 x_j=256^j，
（直观的讲法就是T个两两不同的文件总长度最短的情况只能是0字节的有1个，1字节的有256个，……，k字节的有256^k个）
所以压缩后总长度不变，也就是说没有真的压缩掉什么信息

㈧ 求算法导论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.

㈨ 算法导论第1章的思考题题意不明白。

就相当于 f(n) = lgn,sqrt(n),n 等等 求f(n) = 1s,1min,1hour,1day等时n的值

㈩ 算法导论的问题

1.就是求8n^2>64nlgn时，n的取值
2.n^2<2^n，求n值