演算法導論題解

㈠ 演算法導論 習題

將集合排序，復雜度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值