【正文】 Ω(n2) 故當(dāng) n≥1，有 n2 ≤f(n)≤ 30n2 令 g(n)=n2，因?yàn)楫?dāng) n≥1時(shí)有 g(n)≤f(n)≤30g(n) 所以 f(n)= Θ(n2) 解 2：令 g(n)=n2 )()(),()(),()(102022lim323lim)()(lim22222nnfnnfnnfnnnnnngnfnnn???????????????????70 例 （ Page 17） 令 f(n) =aknk+aknk+…+a kn+a0 ， 則 f(n) =Θ(nk)= f(n)=Ｏ (nk), f(n)= Ω(nk) 例 （ Page 17） 例 （ Page 17） 任一常函數(shù)是 Θ (1),Ｏ (1),Ω (1) )()(),()(),()(),()(0l o glim2l o g2l o glim22222nnfnnfnonfnnfnnnnnnnn??????????? ?????71 證明當(dāng) n≥？時(shí)有 2n＜ n! 證： )4(!28:424l o g2l o g2l o g22l o g2l o g2l o g2:,2)2(:)2()12) . . . (2)(1(1*2) . . .12(2)12) . . . (2)(1(!22就成立實(shí)際上當(dāng)有時(shí)當(dāng)由此可得即即等式變換二邊取對(duì)數(shù)后有根據(jù)要求??????????????????nn，nnnnnnnnnnnnnnnnnnnnnnnn由此可得： 2n=o(n!) 72 例 （ Page 17） )l o g(l o g)l o g(l o g2l o g22l o g22l o gl o g)l o g(l o gl o gl o g11211111nnjnnjnnnnnnjnnjnjnjnjnjnjnjnjnj????????????????????????????????????????????????????????????????????njj1log !log)( nnf ?73 例 （ Page 18） 同理： ? ?!2!2!l o g)l o g(2l o g2l o g),l o g(!l o gnonnnnnnnnnnnn????????????? ?? ?22!!2nnonno??? ?22222!!2!l o g2l o g!l o gl o g2l o g2nnnnonnnnnnn??????????74 75 空間復(fù)雜性 空間復(fù)雜性定義（ P19） 為了求解問題的實(shí)例，執(zhí)行計(jì)算步驟所需要的內(nèi)存空間的數(shù)目，它不包括分配用來存儲(chǔ)輸入的空間。換句話說，僅僅是算法需要的工作空間。 空間復(fù)雜性的計(jì)算要比時(shí)間復(fù)雜性簡單得多，可將時(shí)間復(fù)雜性的定義和符號(hào)移植到空間復(fù)雜性的表示。 例 1：在算法 LinearSearch中，僅需要一個(gè)內(nèi)存單元保存搜索結(jié)果。如果加上局部變量，可以得出需要的空間數(shù)量為 Θ(1)。同理算法 BinarySearch、 SelectionSort和InsertionSort。 76 例 2： 在算法 Merge中，需要和輸入大小相同的存儲(chǔ)器 n個(gè)，因此空間復(fù)雜性為 Θ(n)。同理算法 BottomUpSort。 ?許多問題的處理需要在時(shí)間和空間之間平衡。一般來說，給算法分配的空間越大，算法運(yùn)行速度就越快，反之亦然。 ?迄今為止所討論的大多數(shù)算法中，增加空間并不可能導(dǎo)致算法速度的加快，有可能反而降低。但是，減小空間會(huì)導(dǎo)致算法速度的降低是毫無疑問的。 77 如何估計(jì)算法運(yùn)行時(shí)間 通過計(jì)算迭代次數(shù)估計(jì)算法運(yùn)行時(shí)間 算法 LinearSearch（ Page 3） 輸入： n個(gè)元素的數(shù)組 A[1..n]和元素 x 輸出：如果 x=A[j]（ 1≤j≤n），則輸出 j，否則輸出 0。 1. j←1 2. while (jn) and (x≠A[j]) 3. j←j+1 4. end while 5. if x=A[j] then return j else return 0 78 算法 BinarySearch（ Page 4） 輸入： n個(gè)元素的數(shù)組 A[1..n]（按升序排列）和元素 x。 輸出：如果 x=A[j]， 1≤j≤n，則輸出 j，否則輸出 0。 1. low←1 : high←n : j←0 //j=0表示未找到 2. while (low≤high) and (j＝ 0) 3. mid← ?(low+high)/2? //? ?表示向下 取整 (Page 45) 4. if x＝ A[mid] then j←mid 5. else 6. if x＜ A[mid] then high←mid 1 7. else low←mid+1 //x＞ A[mid] 8. end if 9. end if 10. end while 11. return j 79 當(dāng) ?n/2j1? =1， j為最大迭代次數(shù)（或稱最大循環(huán)次數(shù)、或稱最大比較次數(shù)） ?n/2j1?＝ 1 等價(jià)于 1≤n/2j1＜ 2 等價(jià)于 2j1≤n＜ 2j 等價(jià)于（取對(duì)數(shù)） j1≤Log2n＜ j 考慮 ?Log2n?≤Log2n＜ ?Log2n ?+1 因?yàn)?j是整數(shù)，故有 j1＝ ?Log2n ? 或 j＝ ?Log2n ?+1 二者均有 j＝ ?Log2n ?+1 80 算法 SelectionSort（參見 Page 8） 輸入：數(shù)組 A[1..n] 輸出：按升序排列的數(shù)組 A[1..n] 1. for i←1 to n 1 2. k←i 3. for j←i+1 to n 4. if A[j]A[k] then k←j 5. end for 6. if k≠i then 交換 A[i]和 A[k] 7. end for 81 算法 InsertionSort(參見 Page 89) 輸入：數(shù)組 A[1..n] 輸出：按升序排列的數(shù)組 A[1..n] 1. for i←2 to n 2. x←A [i] 3. j←i 1 4. while (j0) and (A[j]x) 5. A[j+1]←A[j] 6. j←j 1 7. end while 8. A[j+1]←x 9. end for 82 算法 InsertionSort(參見 Page 89) 輸入：數(shù)組 A[1..n] 輸出：按升序排列的數(shù)組 A[1..n] 1. for i←2 to n 2. x←A [i] 3. j←i 1 4. while (j0) and (A[j]x) 5. A[j+1]←A[j] 6. j←j 1 7. end while 8. A[j+1]←x 9. end for 83 算法 COUNT1(Page 21) 輸入： n=2k,k為正整數(shù) 輸出：執(zhí)行次數(shù) count 1. count ←0 2. while n≥1 3. for j←1 to n 4. count ← count +1 5. end for 6. n ←n/2 7. end while 8. return count 算法運(yùn)行時(shí)間： ? ?nnP a g ennnkkjjkjj?????????? ??? ????12))(50(212212 0084 算法 COUNT3(Page 2223) 輸入： k為正整數(shù) 輸出：執(zhí)行次數(shù) count 1. count ←0 2. for i←1 to n 3. j← 2 4. while j≤n 5. j← j2 6. count ← count +1 7. end while 7. end for 8. return count 算法運(yùn)行時(shí)間： ? ?nn lo glo g?kn 22?85 算法 PSUM(Page 23) 輸入： k為正整數(shù) 輸出：對(duì)于 1和 n之間的每個(gè)完全平方數(shù) j，輸出 1. 2. for j←1 to k 3. sum[j]← 0 4. for i←1 to j2 5. j← j2 6. sum[j]← sum[j] + i 7. end for 7. end for 8. return sum[1…k] 算法運(yùn)行時(shí)間： ? ? ? ?126)12)(1( nkkkkjkj?????????2kn???jii1nk