acm算法教程(編輯修改稿)
2025-08-31 09:26 本頁面
【文章內(nèi)容簡介】 機(jī)資源 —— 時(shí)間和空間進(jìn)行估算 ? 時(shí)間復(fù)雜性（ Time Complexity） ? 空間復(fù)雜性（ Space Complexity） 算法分析的目的： ? 設(shè)計(jì)算法 —— 設(shè)計(jì)出復(fù)雜性盡可能低的算法 ? 選擇算法 —— 在多種算法中選擇其中復(fù)雜性最低者 算法設(shè)計(jì)與分析 淮海工學(xué)院 時(shí)間復(fù)雜性分析的關(guān)鍵： ?問題規(guī)模：輸入量的多少； ?基本語句：執(zhí)行次數(shù)與整個(gè)算法的執(zhí)行時(shí)間 成正比的語句 for (i=1。 i=n。 i++) for (j=1。 j=n。 j++) x++。 問題規(guī)模： n 基本語句： x++ 算法設(shè)計(jì)與分析 淮海工學(xué)院 漸進(jìn)符號(hào) 1. 大 O符號(hào) 定義 若存在兩個(gè)正的常數(shù) c和 n0，對于任意n≥ n0，都有 T(n)≤ c f(n)，則稱 T(n)=O(f(n)) n0 問題規(guī)模 n 執(zhí)行次數(shù) n0 之前的情況無關(guān)緊要 T(n) c f(n) 算法設(shè)計(jì)與分析 淮海工學(xué)院 2. 大 Ω符號(hào) 定義 若存在兩個(gè)正的常數(shù) c和 n0，對于任意n≥ n0，都有 T(n)≥ c g(n)，則稱 T(n)=Ω(g(n)) n0 問題規(guī)模 n 執(zhí)行次數(shù) n0 之前的情況無關(guān)緊要 T(n) c g(n) 漸進(jìn)符號(hào)（續(xù)） 算法設(shè)計(jì)與分析 淮海工學(xué)院 3. Θ 符號(hào) 定義 若存在三個(gè)正的常數(shù) c c2和 n0，對于任意 n≥ n0都有 c1 f(n)≥ T(n)≥ c2 f(n)，則稱 T(n)=Θ(f(n)) n0 問題規(guī)模 n 執(zhí)行次數(shù) n0 之 前 的情況無關(guān)緊要 T(n) c2 f(n) c1 f(n) 漸進(jìn)符號(hào)（續(xù)） 算法設(shè)計(jì)與分析 淮海工學(xué)院 例： T(n)＝ 5n2＋ 8n＋ 1 當(dāng) n≥ 1時(shí) ， 5n2＋ 8n＋ 1≤ 5n2＋ 8n＋ n ＝ 5n2＋ 9n≤ 5n2＋ 9n2≤ 14n2＝ O(n2) 當(dāng) n≥ 1時(shí) ， 5n2＋ 8n＋ 1≥ 5n2＝ Ω(n2) ∴ 當(dāng) n≥ 1時(shí) ， 14n2≥ 5n2＋ 8n＋ 1≥ 5n2 則： 5n2＋ 8n＋ 1＝ Θ(n2) 定理 若 T(n)=amnm +am1nm1 + … +a1n+a0（ am0），則有 T(n)=O(nm)且 T(n)=Ω(n m)，因此，有 T(n)=Θ(n m)。 算法設(shè)計(jì)與分析 淮海工學(xué)院 最好、最壞和平均情況
語文相關(guān)推薦
鄂ICP備17016276號(hào)-1