【正文】 ，每對(duì)合并需要的比較次數(shù)，最少是 2j1，最多為 2j1 。執(zhí)行該算法的元素賦值次數(shù)為 2nlog2n。即當(dāng)給出合法的輸入時(shí)，為了得到輸出，該算法執(zhí)行時(shí)所需要的時(shí)間和空間，其中時(shí)間尤為重要。因?yàn)橛绊懸粋€(gè)算法的實(shí)際運(yùn)行時(shí)間與諸多因素有關(guān)（例機(jī)器性能、語(yǔ)言選擇、編譯程序優(yōu)劣、程序員素質(zhì)等），甚至無(wú)需計(jì)算出算法運(yùn)行時(shí)間的近似數(shù)。 ②算法可以用各種語(yǔ)言來(lái)表示，甚至使用人類(lèi)語(yǔ)言。 ④算法分析不拘泥小規(guī)模數(shù)據(jù)的輸入，主要關(guān)心在大的輸入實(shí)例時(shí)，算法運(yùn)行狀況。觀(guān)察函數(shù) n2log2n+10n2+n 中的低階項(xiàng) 10n2和 n ，當(dāng) n值越大，10n2+n對(duì)函數(shù)值的影響就越小。 在進(jìn)一步的簡(jiǎn)化抽象中，即對(duì)運(yùn)行時(shí)間的增長(zhǎng)率簡(jiǎn)化。如：an2+bn+c簡(jiǎn)化為 an2。 另外，還可以忽略最高次項(xiàng)的常數(shù)系數(shù)，因?yàn)樵诳紤]較大規(guī)模輸入下的率相對(duì)于增長(zhǎng)率來(lái)說(shuō)系數(shù)是次要的。 ②時(shí)間復(fù)雜性 在算法分析中，通常是用漸近運(yùn)行時(shí)間來(lái)度量一個(gè)算法。 ③算法分析中的漸近符號(hào)有： O、 Ω 、 Θ 、 o。 次線(xiàn)性函數(shù)： log2n（簡(jiǎn)記為 log n) 線(xiàn)性函數(shù)： n 次平方函數(shù)： n log2n（簡(jiǎn)記為 n log n) 平方函數(shù)： n2 立方函數(shù)： n3 指數(shù)函數(shù)： 2n 運(yùn)行時(shí)間是爆炸性的 階乘函數(shù)（超指數(shù)函數(shù)）： n! 運(yùn)行時(shí)間是爆炸性的 56 定義 （ Page 16） 令 f(n)和 g(n)是從自然數(shù)集到非負(fù)實(shí)數(shù)集的二個(gè)函數(shù)。 ㈡ O符號(hào)（讀作大 O） ))(()()( )(l i m ngOnfng nfn ????? 蘊(yùn)含著因此若 若極限為非 0正常數(shù)，則函數(shù) f(n)和 g(n)增長(zhǎng)速度至多相差常數(shù)倍，或稱(chēng)為同一級(jí)別；若極限為 0，說(shuō)明隨著 n的增大，函數(shù) f(n)的增長(zhǎng)要比 g(n)的增長(zhǎng)慢得多。 ?57 例 1： f(n)=3n+2，求 g(n)，使得 f(n)=O(g(n))。 解 1： 當(dāng) n≥2，有 f(n)≤10n2+4n+n=10n2+5n 當(dāng) n≥5，有 f(n)≤10n2+5n≤10n2+n2 =11n2 令 g(n)=n2，因?yàn)楫?dāng) n≥5時(shí)有 f(n)≤11g(n) 所以 f(n)=O(g(n))=O(n2) 解 2：令 g(n)=n2 )()(2410lim102410lim)()(lim22222nOnfnnnnnnngnfnnn?????????????????同理可證： f(n)=O(nk)， k≥2 59 例 3： f(n)=6*2n+n2，求 g(n)，使得 f(n)=O(g(n))。只要當(dāng)排序元素的個(gè)數(shù)不小于某個(gè)閾值 n0時(shí)，運(yùn)行時(shí)間最多為 2； ?應(yīng)強(qiáng)調(diào)的是，即使當(dāng)輸入很大時(shí)，也不能說(shuō)運(yùn)行時(shí)間恰好為 2，因?yàn)楫?dāng)輸入已經(jīng)按升序排列，排序算法InsertionSort執(zhí)行的比較次數(shù)為 n1。如果存在一個(gè)自然數(shù) n0和一個(gè)正常數(shù) c，使得 n≥n0 ， f(n)≥cg(n) 則稱(chēng) f(n) =Ω(g(n))， n0稱(chēng)為閾值 。 可以是正常數(shù)或 ∞ ?61 例 1： f(n)=3n+2，求 g(n)，使得 f(n)=Ω(g(n))。 令 g(n)=n，因?yàn)楫?dāng) n0時(shí)有 f(n)≥3g(n) 所以 f(n)=Ω(g(n))=Ω(n) 例 2： f(n)=10n2+4n+2，求 g(n)，使得 f(n)=Ω(g(n))。 ?排序算法 InsertionSort的元素比較次數(shù)至少是 (n1 )，在這種情況下，稱(chēng)算法 InsertionSort的運(yùn)行時(shí)間是 Ω(n)。 ?稱(chēng)排序問(wèn)題的比較次數(shù)為 Ω(nlog n)，是指無(wú)法設(shè)計(jì)出一個(gè)新的基于比較的排序算法，它的時(shí)間復(fù)雜性小于nlog n。如果存在一個(gè)自然數(shù) n0和二個(gè)正常數(shù) c1和 c2，使得 n≥n0 ， c1g(n)≤f(n)≤c2g(n) 則稱(chēng) f(n)= Θ(g(n))， n0稱(chēng)為閾值 。 ?64 例： f(n)=3n+2，求 g(n)，使得 f(n) =Θ(g(n))。而 SelectionSort算法和 BottomUpSort算法可分別使用 Θ(n2)和 Θ(nlog2n)精確描述。 例： f(n)=3n+ g(n)=n，顯然有 f(n)=Θ(g(n))。 ㈤ o符號(hào)（讀作小 o） 由等價(jià)關(guān)系 f(n)=Θ(g(n)) 導(dǎo)出了一個(gè)等價(jià)類(lèi)，為了說(shuō)明二個(gè)函數(shù)屬于不同類(lèi)，引入了 o符號(hào)。 66 定義 （ Page 19） 令 f(n)和 g(n)是從自然數(shù)集到非負(fù)實(shí)數(shù)集的二個(gè)函數(shù)。 ))(()(0)( )(l i m ngonfng nfn ???? 蘊(yùn)含著因此若 形式地說(shuō)明了當(dāng) n→∞ 時(shí)， f(n)對(duì)于 g(n)來(lái)說(shuō)可以忽略不計(jì)。 例如：“ n是 o(n2)的 ”等價(jià)于“ n是 O(n2)，但 n2≠O(n)”。用該記號(hào)可簡(jiǎn)明地表示復(fù)雜性的層次 。例如： 100n≥n 100n=O(n) n≤100n 100n=Ω(n) n≠100n 100n=Θ(n) 一般地，設(shè) f(n)=aknk+ak1nk1+…+a 1n+a0，則 f(n)=Θ(nk)，它蘊(yùn)含著 f(n)=O(nk)， f(n)=Ω(nk) 。 解： 當(dāng) n≥1， f(n)= 10n2+20n ≤30n2 ， f(n)=Ｏ (n2) 當(dāng) n≥1， f(n)=10n2+20n ≥n2 ， f(n)= Ω(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） 為了求解問(wèn)題的實(shí)例，執(zhí)行計(jì)算步驟所需要的內(nèi)存空間的數(shù)目，它不包括分配用來(lái)存儲(chǔ)輸入的空間。 空間復(fù)雜性的計(jì)算要比時(shí)間復(fù)雜性簡(jiǎn)單得多，可將時(shí)間復(fù)雜性的定義和符號(hào)移植到空間復(fù)雜性的表示。如果加上局部變量，可以得出需要的空間數(shù)量為 Θ(1)。 76 例 2： 在算法 Merge中，需要和輸入大小相同的存儲(chǔ)器 n個(gè)，因此空間復(fù)雜性為 Θ(n)。 ?許多問(wèn)題的處理需要在時(shí)間和空間之間平衡。 ?迄今為止所討論的大多數(shù)算法中，增加空間并不可能導(dǎo)致算法速度的加快，有可能反而降低。 77 如何估計(jì)算法運(yùn)行時(shí)間 通過(guò)計(jì)算迭代次數(shù)估計(jì)算法運(yùn)行時(shí)間 算法 LinearSearch（ Page 3） 輸入： n個(gè)元素的數(shù)組 A[1..n]和元素 x 輸出：如果 x=A[j]（ 1≤j≤n），則輸出 j，否則輸出 0。 輸出：如果 x=A[j]， 1≤j≤n，則輸出 j，否則輸出