lecture4(編輯修改稿)
2024-08-13 15:19 本頁面
【文章內(nèi)容簡介】 (m) = 2S(m/2) + m (把 m 換成 lg n) 因為我們知道 S(m) = O(m lg m)，所以可以推得T(n) = O(lg n lglg n) nRecurrences 12 The iteration(recursiontree) method 範例 : T(n)=3T(?n/4?) + n T(n) = n + 3(?n/4? + 3T(?n/16?)) = n + 3?n/4? + 9(?n/16? + 3T(?n/64?)) . . (note that n/( ?1) ? n + 3n/4 + 9n/16 + 27n/64 + ... + ?(1) = 4n+o(n) = O(n) )4 4log n)()43( 3l o g04nnii ??? ???Recurrences 13 Recursion trees: (for visualizing the iteration) ? T(n)=2T(n/2) + n2 T(n) ??????2nT ??????2nTn2 Recurrences 14 22??????n24??????n22??????n24??????n24??????n 24??????nn2 n2 221n241n? ?2n?lg n … … Total： Recurrences 15 範例 : T(n) = T(n/3) + T(2n/3) + n 32n9n3n94n92n92nn n ? ?nnlg?… … Total： n n n23logRecurrences 16 The master method Theorem (Master theorem) 令 a ? 1 及 b 1 為常數(shù)，令 f(n) 為一函數(shù)，且定義 T(n) 為非負的整
研究報告相關(guān)推薦
鄂ICP備17016276號-1