[農(nóng)學(xué)]第1章緒論-在線瀏覽
2024-12-03 17:48本頁面
【正文】 問題規(guī)模： n 基本語句： x++ 算法設(shè)計(jì)與分析 漸進(jìn)符號 1. 大 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ì)與分析 2. 大 Ω符號 定義 若存在兩個(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)符號（續(xù)） 算法設(shè)計(jì)與分析 3. Θ 符號 定義 若存在三個(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)符號（續(xù)） 算法設(shè)計(jì)與分析 [例 ]： 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)。 in。 return i。 算法設(shè)計(jì)與分析 非遞歸算法的分析 算法 —— 非遞歸算法 、 遞歸算法 * [例 ]：求數(shù)組最小值算法 int ArrayMin(int a[ ], int n) { min=a[0]。 in。 return min。 算法設(shè)計(jì)與分析 遞歸算法的分析 1. 猜測技術(shù) :對 遞推關(guān)系式估計(jì)一個(gè)上限 ，然后 （ 用數(shù)學(xué)歸納法 ） 證明它正確 。 算法設(shè)計(jì)與分析 2. 擴(kuò)展遞歸技術(shù) [例 ] ? ? ? + = = 1 5 ) 2 ( 2 1 7 ) ( 2 n n n T n n T ) ( 10 3 10 ) 2 1 2 ( 5 7 2 5 7 ) ( 2 2 2 1 2 1 0 2 n O n n n n n n n n T k k i i = ? = + = ?
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1