計(jì)算復(fù)雜性和算法分析計(jì)算機(jī)科學(xué)導(dǎo)論第六講(參考版)
2025-07-24 11:25本頁(yè)面
【正文】 整個(gè)程序的復(fù)雜性函數(shù)還是以整個(gè)程序的輸入規(guī)模為自變量 – 對(duì)串行算法 ， 其時(shí)間復(fù)雜性等于相應(yīng)程序每個(gè)語(yǔ)句的時(shí)間復(fù)雜性之和 。 其中 sk(k =1, 2, 3, 4)都是賦值語(yǔ)句 – 外循環(huán)執(zhí)行 N次，需時(shí)間 (5a +t) ? N(N+1)/2 + (a +t) ? N – 因此上界為 O(N2) – 這是規(guī)模充分大時(shí)的上界 – 這個(gè)上界的階越低，則評(píng)估就越精確，結(jié)果就越有價(jià)值 32 復(fù)雜性的漸近行為及其階 ? 關(guān)于記號(hào) O(g(N))的討論 – 當(dāng)討論復(fù)雜算法上界時(shí)，很希望上界記號(hào) O(g(N)) 能參與到復(fù)雜性計(jì)算中 – 例如，上例內(nèi)循環(huán)的上界 O(i)，則累加起來(lái)便是外循環(huán)的時(shí)間復(fù)雜性 T(N) = ?O(i) = O(?i) = O(N(N+1)/2) = O(N2) – 若希望如此，則需要有一些演算規(guī)則，并證明其正確性 i=1 n i=1 n 33 復(fù)雜性的漸近行為及其階 ? 關(guān)于記號(hào) O(g(N))的討論 記號(hào) O的運(yùn)算規(guī)則（某書(shū)給出） – O(f(N)) + O(g(N)) = O(max(f(N), g(N))) – O(f(N)) + O(g(N)) = O(f(N) + g(N)) – O(f(N)) ? O(g(N)) = O(f(N) ? g(N)) – … … – 問(wèn)題：在 O(… )未定義時(shí)，等號(hào)左邊 +和 ?的含義？ f(N), 若 f(N) ? g(N) 其中 max(f(N) , g(N)) = g(N), 若 f(N) g(N) 34 復(fù)雜性的漸近行為及其階 ? 關(guān)于記號(hào) O(g(N))的討論 一種解釋（另一本書(shū)給出）： O(g(N)) = { f(N) | ?C 0.?N0 0.?N ?N0. 0 ? f(N) ? Cg(N) } – 符號(hào) O(g(N)) 在此給出了明確的數(shù)學(xué)意義 – 寫(xiě) f(N) ? O(g(N))容易理解 ( 而不是 f(N) = O(g(N)) ) – 但解釋 O(f(N)) + O(g(N)) 和 O(f(N)) ? O(g(N))中的+和 ?（尤其是 ?）仍然有困難 – 導(dǎo)致各書(shū)仍繼續(xù)使用 f(N) = O(g(N))記號(hào)，使得讀者難理解 35 復(fù)雜性的漸近行為及其階 ? 其他漸近意義下的記號(hào) – 下界記號(hào) ? 若 f 和 g是正整數(shù)集上的正函數(shù)，若 存在大于 0的常 數(shù) C和自然數(shù) N0，使得 N ? N0時(shí)有 f(N) ? Cg(N), 則 稱： 在 N充分大時(shí)， Cg(N)是函數(shù) f(N)的一個(gè) 下 界，記為 f(N) =? (g(N))， 并簡(jiǎn)稱 f(N)不 小 于 g(N)的階 – 記號(hào) ? f(N) =?(g(N)) ? f(N) = O(g(N)) ? f(N) =?(g(N)) 此時(shí)稱 f(N)和 g(N)同階 – 還有其他記號(hào) 36 復(fù)雜性的漸近行為及其階 ? 算法與漸近時(shí)間復(fù)雜性的關(guān)系 算法 漸近復(fù)雜 在 C1上可 在 C2上可 N1和 N2的關(guān)系 性 T(N) 解規(guī)模 N1 解規(guī)模 N2 ? 方程 Ti(N2i)=10Ti(N1i)是求解 N2i和 N1i之間的關(guān)系 ? 等式 Ti(N2i)=10Ti(N1i)的含義是：第 i個(gè)算法在 C1上運(yùn)行 10倍于 C2上運(yùn)行的時(shí)間 ， 則等號(hào)兩邊效果一樣 同一問(wèn)題六個(gè)算法 , 在 C1和 C2上運(yùn)行 , C2的速度是 C1 10倍 . 從 Ti(N2i)=10Ti(N1i)(i =1, … , 6)解出關(guān)系式 37 復(fù)雜性的漸近行為及其階 ? 算法與漸近時(shí)間復(fù)雜性的關(guān)系 算法 漸近復(fù)雜 在 C1上可 在 C2上可 N1和 N2的關(guān)系 性 T(N) 解規(guī)模 N1 解規(guī)模 N2 A1 N N11 N21 N21 = 10N11 A2 NlogN N12 N22 N22 ? 10N12 A3 N2 N13 N23 N23 = 10N13 A4 N3 N14 N24 N24 = 10N14 A5 2N N15 N25 N25 = N15+ log10 A6 N! N16 N26 N26=N16+小的常數(shù) 同一問(wèn)題六個(gè)算法 , 在 C1和 C2上運(yùn)行 , C2的速度是 C1 10倍 . 從 Ti(N2i)=10Ti(N1i)(i =1, … , 6)解出關(guān)系式見(jiàn)上表 3 38 復(fù)雜性的漸近行為及其階 ? 復(fù)雜性漸近分析的重要性 – 對(duì)于低效算法 ， 計(jì)算機(jī)速度數(shù) 10甚至 100倍的增長(zhǎng)基本上不帶來(lái)求解規(guī)模的增益 – 限制求解問(wèn)題規(guī)模的主要根源是算法漸近復(fù)雜性的階 ? 前四個(gè)算法的漸近時(shí)間復(fù)雜性與規(guī)模 N的一個(gè)確定的冪同階 ， 機(jī)器速度的乘法增長(zhǎng)帶來(lái)求解規(guī)模的乘法增長(zhǎng) 。 s3。 j++) s1。 i++) for(j = 1。 其中 sk(k =1, 2, 3, 4)都是賦值語(yǔ)句 –
環(huán)評(píng)公示相關(guān)推薦
鄂ICP備17016276號(hào)-1