[農(nóng)學]第1章緒論-預覽頁
【正文】 n≥ 1時 ， 5n2＋ 8n＋ 1≤ 5n2＋ 8n＋ n ＝ 5n2＋ 9n≤ 5n2＋ 9n2≤ 14n2＝ O(n2) 當 n≥ 1時 ， 5n2＋ 8n＋ 1≥ 5n2＝ Ω(n2) ∴ 當 n≥ 1時 ， 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)。 return i。 in。 算法設(shè)計與分析 遞歸算法的分析 1. 猜測技術(shù) :對 遞推關(guān)系式估計一個上限 ，然后 （ 用數(shù)學歸納法 ） 證明它正確 。 ? ? ? + = = 1 ) ( 1 ) ( n b n aT n c n T k ? ? ? ? ? = = k k k b k k a b a n O b a n n O b a n O n T b ) ( ) log ( ) ( ) ( log 算法設(shè)計與分析 通用分治遞推式推導過程： + = ) ( ) ( b n aT n T k = a(T(n/b2)+c(n/b)k)+k = amT(1)+am1c(n/bm1)k+…+ac(n/b) k +k = c? ami (n/bmi)k = c? ami bik = cam ? (bk/a)i 算法設(shè)計與分析 上式中根據(jù)比率 r= bk/a的取值不同，有三種可能的情況需要討論： 注意引用如下關(guān)系式： n=bm， m=logbn, am=alogbn =nlogba (1) r1： ? ri 1/(1r)，由于 am=nlogba，所以， T(n)=O(nlogba)； (2)r=1： ? ri=m+1=logbn+1，由于 am =nlogba= nk，所以， T(n)=O(nk logbn)； (3)r1： ? ri =(rm+11)/(r1)=O(rm)，所以， T(n)=O(amrm)=O(bkm)=O(nk) 算法設(shè)計與分析 ? ? ? ? ? = = k k k b k k a b a n O b a n n O b a n O n T b ) ( ) log ( ) ( ) ( log 算法設(shè)計與分析 算法的后驗分析 算法的后驗分析（ Posteriori）也稱算法的實驗分析，它是一種事后計算的方法，通常需要將算法轉(zhuǎn)換為對應(yīng)的程序并上機運行。
教學課件相關(guān)推薦
鄂ICP備17016276號-1