計算復雜性和算法分析計算機科學導論第六講(編輯修改稿)
2024-08-17 11:25 本頁面
【文章內(nèi)容簡介】 – 對于算法 A的 T(N)，一般來說， 當 N單調(diào) 遞增 且趨 于 ?時， T(N)也 單調(diào) 遞增 且趨于 ? – 對于 T(N)，若存在 T(N)，使得當 N? ?時有 (T(N) ? T(N)) / T(N) ? 0 則稱 T(N)是 T(N)當 N? ?時的漸近行為，或稱 T(N) 為算法 A的、當 N? ?時的 漸近復雜性 – 直觀上， T(N)是 T(N)略去低項后的主項 例：若 T(N)是 3N2+4Nlog2N+7時， T(N)可以是 3N2, 若 N ? ?， (4Nlog2N+7)/(3N2+4Nlog2N+7) ? 0 ～ ～ ～ ～ ～ ～ N2稱為階 20 復雜性的漸近行為及其階 ? 復雜性的漸近行為 – 對于 T(N)，若存在 T(N)，使得當 N? ?時有 (T(N) ? T(N)) / T(N) ? 0 則稱 T(N)為算法 A的當 N? ?時的 漸近復雜性 – 若用 T(N)代替 T(N)，作為算法 A在 N? ?時的復雜 性的度量，則復雜性分析明顯簡化 – 復雜性分析的目的：在于比較同一問題的不同算 法的效率，若兩個算法的階不同，則可知誰效率高 ～ ～ ～ ～ 21 復雜性的漸近行為及其階 ? 復雜性的漸近行為 – 對于 T(N)，若存在 T(N)，使得當 N? ?時有 (T(N) ? T(N)) / T(N) ? 0 則稱 T(N)為算法 A的當 N? ?時的 漸近復雜性 – 簡化 T(N)分析： 只需關心 T(N)的階，把其常數(shù)因 子忽略。如在 3N2中，不用關心系數(shù) 3 – 進一步簡化 T(N)分析：假設算法中用到的所有不 同的元運算執(zhí)行一次都只需一個時間單位 ～ ～ ～ ～ 22 ～ ～ 復雜性的漸近行為及其階 ? 算法復雜性的漸近分析方法 – 只要考察當問題規(guī)模充分大時，算法復雜性在漸近意義下的階。算法分析通常都是這么做的 – 與此簡化的復雜性分析相配套，需要引入一些漸近意義下的記號 23 復雜性的漸近行為及其階 ? 漸近意義下的 記號 O（代表 order of … ） 若 f 和 g是正整數(shù)集上的正函數(shù)，若存在大于 0的常 數(shù) C和自然數(shù) N0，使得 N ? N0時有 f(N) ? Cg(N), 則 稱：在 N充分大時， Cg(N)是函數(shù) f(N)的一個上界， 記為 f(N) = O(g(N))，并簡稱 f(N)不大于 g(N)的階 使用“ =”是不妥的，這是一種對“ =”的濫用 – f(N) = O(g(N))作為一個整體，表達函數(shù) f 和 g的一種關系 – “ =”在這里的含義是什么？ – 單獨的 O(g(N))記號的含義是什么？ 24 復雜性的漸近行為及其階 ? 漸近意義下的 記號 O（代表 order of … ） 若 f 和 g是正整數(shù)集上的正函數(shù)，若存在大于 0的常 數(shù) C和自然數(shù) N0，使得 N ? N0時有 f(N) ? Cg(N), 則 稱：在 N充分大時， Cg(N)是函數(shù) f(N)的一個上界， 記為 f(N) = O(g(N))，并簡稱 f(N)不大于 g(N)的階 – Intuitively this notation groups functions according to their growth respective to some parameter。 as such, the notation is abusive in two respects: It abuses =, and it invokes terms that are real numbers instead of function terms. 見 Abuse_of_notationBig_O_notation(網(wǎng)頁已被刪去 ) 25 復雜性的漸近行為及其階 ? 漸近意義下的 記號 O（代表 order of … ） 若 f 和 g是正整數(shù)集上的正函數(shù)，若存在大于 0的常 數(shù) C和自然數(shù) N0，使得 N ? N0時有 f(N) ? Cg(N), 則 稱：在 N充分大時， Cg(N)是函數(shù) f(N)的一個上界， 記為 f(N) = O(g(N))，并簡稱 f(N)不大于 g(N)的階 – 千萬不要把這里的“ =”理解成左右兩邊相等 – 對于函數(shù) g(N)，盡可能使用簡單的解析式。例如 N, N2等 – ?N. N ? 1 ? 3N ? 4N, 故 f(N) = O(N) (f(N) = 3N, g(N) = N, C =4, 下面略去 f和 g的定義 ) 26 復雜性的漸近行為及其階 ? 漸近意義下的 記號 O（代表 order of … ） 若 f 和 g是正整數(shù)集上的正函數(shù)，若存在大于 0的常 數(shù) C和自然數(shù) N0，使得 N ? N0時有 f(N) ? Cg(N), 則 稱：在 N充分大時， Cg(N)是函數(shù) f(N)的一個上界， 記為 f(N) = O(g(N))，并簡稱 f(N)不大于 g(N)的階 – ?N. N ? 10 ? 2N2+11N ?10 ? 3N2， 故 2N2+11N ?10 = O(N2)
環(huán)評公示相關推薦
鄂ICP備17016276號-1