analysisofalgorithms(2)(編輯修改稿)
2025-08-11 17:42 本頁面
【文章內(nèi)容簡介】 h=Θ(logbn) 換底公式 : logbn=log2n/log2b = h=Θ(logn) Substitution methods ? The most general method: 1. Guess the form of the solution. 2. Verify by induction. 3. Solve for constants. Example1 ? T (n) = 4T (n/2) + n （ n=2h） ? [Assume that T (1)=Θ(1).] ? Guess O(n3) :歸納 假定 為 T (n)≤3. c是待定常 數(shù) . ? 應(yīng) 用假定有 :T (k) ≤ck3 for k n . ? 歸納證 明 : T (n) ≤ 3 并 確定常 數(shù) c. Example(continued) ? T(n)=4T(n/2)+n ≤4c(n/2)3+n =(c/2)n3+n =3((c/2)n3n) ≤ 3 取 c≥2 and n≥1,不等式 (c/2)n3–n≥0成立 , Example(continued) ? 還要檢驗初始條件是否滿足歸納假設(shè) . ? 初始條件為 : T(n)=Θ(1),當(dāng) nn0 ,n0為常數(shù) . ? 因為有常數(shù) n01個 T的值 :T(1),┅ ,T(n01) ? 所以我們可取 c足夠大 ,使得 T(n)≤3, 對nn0 成立 . ? This bound is not tight! Example(continued) ? We shall prove that T(n)=O(n2). ? Assume that T(k)≤ck2 for kn: ? T(n)=4T(n/2)+n ≤4c(n/2)2+n =2+n ? 歸納不能往下進行！ Continued ? IDEA: Strengthen the inductive hypothesis. ? Subtract a loworder term. ? Inductive hypothesis: T(k)≤c1k2– c2k for kn. ? T(n)=4T(n/2)+n ≤4[c1(n/2)2c2(n/2)]+n =c1n2c2n(c2
范文總結(jié)相關(guān)推薦
鄂ICP備17016276號-1