jnqaaaalgorithm-chapter--文庫吧
2025-07-09 13:01 本頁面
【正文】 ering 7 分析框架 —— 算法的最優(yōu)、最差和平均效率 ?算法的最優(yōu)、最差和平均效率 ?最差效率 是指在輸入規(guī)模為 n時，算法在最壞情況下的效率。 ?最優(yōu)效率 是指在輸入規(guī)模為 n是，算法在最優(yōu)情況下的效率。 ?平均效率 是指在“典型”或“隨機”輸入的情況下，算法具有的行為（效率）。 ?攤銷效率 是指對于同樣的數(shù)據(jù)結(jié)構(gòu)執(zhí)行多次操作，然后分攤到每一次上。 Analysis and Design of Computer Algorithms Yunnan University School of Information Science amp。 Engineering 8 漸進符號 ?算法效率的主要指標是基本操作次數(shù)的 增長次數(shù) 。 ?為了對這些增長次數(shù)進行比較和歸類，計算機科學家們使用了 3種符號： ?O（讀 “ O”）：上界 ?Ω（讀 ” omega”）：下界 ?Θ（讀 ” theta”）：近似 Analysis and Design of Computer Algorithms Yunnan University School of Information Science amp。 Engineering 9 符號 O ? 定義 1 對于足夠大的 n， t(n)的上界由 g(n)的常數(shù)倍來確定，即： ? 記為 t(n) ∈ O(g(n)) t(n) ≤ cg(n)， c為常數(shù) n ∈ O(n2) 100n+5 ∈ O(n2) n(n1)/2 ∈ O(n2) Analysis and Design of Computer Algorithms Yunnan University School of Information Science amp。 Engineering 10 符號 Ω ? 定義 2 對于足夠大的 n， t(n)的下界由 g(n)的常數(shù)倍來確定，即： ? 記為 t(n) ∈ Ω(g(n)) t(n) ≥ cg(n)， c為常數(shù) n3∈ Ω (n2) n(n+1)∈ Ω (n2) 4n2+5 ∈ Ω (n2) Analysis and Design of Computer Algorithms Yunnan University School of Information Science amp。 Engineering 11 符號 Θ ? 定義 3 對于足夠大的 n， t(n)的上界和下界由 g(n)的常數(shù)倍來確定，即： ? 記為 t(n) ∈ Θ(g(n)) c2g(n) ≤ t(n) ≤ c1g(n)， c1,c2為常數(shù) n2+3n+2∈ Θ (n2) n(n1)/2∈ Θ (n2) 4n2+5 ∈ Θ (n2) Analysis and Design of Computer Algorithms Yunnan University School of Information Science amp。 Engineering 12 漸進符號的有用特性 ?定理 如果 t1(n) ∈ O(g1(n))并且 t2(n) ∈ O(g2(n))，則 t1(n)+ t2(n)
環(huán)評公示相關(guān)推薦
鄂ICP備17016276號-1