做网站_没内容,网站建设太金手指六六二八,平面图设计软件,赣州编程培训机构主定理#xff08;Master Theorem#xff09;是用于分析递归算法时间复杂度的一个重要工具。它适用于形式化定义的一类递归关系#xff0c;通常采用分治策略解决问题的情况。 目录 主定理简化版的局限主定理一般形式情况1#xff1a; n l o g b a n^{log_{b}{a}} nlogba … 主定理Master Theorem是用于分析递归算法时间复杂度的一个重要工具。它适用于形式化定义的一类递归关系通常采用分治策略解决问题的情况。 目录 主定理简化版的局限主定理一般形式情况1 n l o g b a n^{log_{b}{a}} nlogba 比 f ( n ) f(n) f(n) 增长的快情况2 n l o g b a n^{log_{b}{a}} nlogba 与 f ( n ) f(n) f(n) 增长率类似情况3 n l o g b a n^{log_{b}{a}} nlogba 比 f ( n ) f(n) f(n) 增长的慢 主定理不适用的情况 主定理简化版的局限
主定理简化版的三种情况 I F IF IF f ( n ) O ( n l o g b ( a − ε ) ) f(n) O(n^ {log_b(a - ε)}) f(n)O(nlogb(a−ε))and ε 0 ε 0 ε0Then T ( n ) Θ ( n l o g b ( a ) ) T(n) Θ(n^{log_b(a)}) T(n)Θ(nlogb(a)) I F IF IF f ( n ) Θ ( n l o g b ( a ) ⋅ l o g k n ) f(n) Θ(n^{log_b(a)} ·log^k n) f(n)Θ(nlogb(a)⋅logkn)and k ≥ 0 k ≥ 0 k≥0Then T ( n ) Θ ( n l o g b ( a ) ⋅ l o g k 1 n ) T(n) Θ(n^{log_b(a)} · log^{k1} n) T(n)Θ(nlogb(a)⋅logk1n) I F IF IF f ( n ) Ω ( n l o g b ( a ε ) ) f(n) Ω(n^{log_b(a ε)}) f(n)Ω(nlogb(aε))and ε 0 ε 0 ε0 a ⋅ f ( n b ) ≤ c ⋅ f ( n ) a · f(\frac{n}{b}) ≤ c · f(n) a⋅f(bn)≤c⋅f(n) 对于某个常数 c 1 c 1 c1 和所有足够大的 n n n 成立Then T ( n ) Θ ( f ( n ) ) T(n) Θ(f(n)) T(n)Θ(f(n)) 简化形式具有一定的限制条件比如形式上必须是 T ( n ) a ⋅ T ( n b ) f ( n ) T(n)a·T(\frac{n}{b})f(n) T(n)a⋅T(bn)f(n) 并且 f ( n ) n c f(n) n^{c} f(n)nc 三个反例
子问题数量不是常数 T ( n ) n ⋅ T ( n 2 ) n 2 T(n)n \cdot T(\frac{n}{2})n^{2} T(n)n⋅T(2n)n2 子问题数量小于1 T ( n ) 1 2 T ( n 2 ) n 2 T(n)\frac{1}{2}T(\frac{n}{2})n^{2} T(n)21T(2n)n2 分解问题和合并解的时间不是 n c n^{c} nc T ( n ) 2 T ( n 2 ) n l o g n T(n)2T(\frac{n}{2})nlogn T(n)2T(2n)nlogn 主定理一般形式 T ( n ) a ⋅ T ( n b ) f ( n ) , a 0 , b 1 T(n)a·T(\frac{n}{b})f(n),a0,b1 T(n)a⋅T(bn)f(n),a0,b1 I F IF IF ∃ ε 0 \exists ε 0 ∃ε0 使得 f ( n ) O ( n l o g b ( a − ε ) ) f(n) O(n^ {log_b(a - ε)}) f(n)O(nlogb(a−ε)) Then T ( n ) Θ ( n l o g b ( a ) ) T(n) Θ(n^{log_b(a)}) T(n)Θ(nlogb(a)) I F IF IF ∃ k ≥ 0 \exists k ≥ 0 ∃k≥0 使得 f ( n ) Θ ( n l o g b ( a ) ⋅ l o g k n ) f(n) Θ(n^{log_b(a)} ·log^k n) f(n)Θ(nlogb(a)⋅logkn)Then T ( n ) Θ ( n l o g b ( a ) ⋅ l o g k 1 n ) T(n) Θ(n^{log_b(a)} · log^{k1} n) T(n)Θ(nlogb(a)⋅logk1n) I F IF IF ∃ ε 0 \exists ε 0 ∃ε0 使得 f ( n ) Ω ( n l o g b ( a ε ) ) f(n) Ω(n^{log_b(a ε)}) f(n)Ω(nlogb(aε)) 且对于某个常数 c 1 c 1 c1 和所有足够大的 n n n 有 a ⋅ f ( n b ) ≤ c ⋅ f ( n ) a · f(\frac{n}{b}) ≤ c · f(n) a⋅f(bn)≤c⋅f(n) Then T ( n ) Θ ( f ( n ) ) T(n) Θ(f(n)) T(n)Θ(f(n))
主要考虑 函数 n l o g b a n^{log_{b}{a}} nlogba 与 f ( n ) f(n) f(n) 的增长率关系
情况1 n l o g b a n^{log_{b}{a}} nlogba 比 f ( n ) f(n) f(n) 增长的快 T ( n ) 9 T ( n 3 ) n T(n)9T(\frac{n}{3})n T(n)9T(3n)n n l o g b a n 2 n^{log_{b}{a}}n^{2} nlogban2, f ( n ) n O ( n 2 − ϵ ) , ϵ ≤ 1 f(n)nO(n^{2-\epsilon }),\epsilon \le1 f(n)nO(n2−ϵ),ϵ≤1 ⇒ T ( n ) O ( n 2 ) \Rightarrow T(n)O(n^{2}) ⇒T(n)O(n2) 情况2 n l o g b a n^{log_{b}{a}} nlogba 与 f ( n ) f(n) f(n) 增长率类似 T ( n ) T ( 2 n 3 ) 1 T(n)T(\frac{2n}{3})1 T(n)T(32n)1 n l o g b a n l o g 3 / 2 1 n 0 1 n^{log_{b}{a}}n^{log_{3/2}1}n^{0}1 nlogbanlog3/21n01, f ( n ) 1 Θ ( n l o g b a l o g 0 n ) f(n)1Θ(n^{log_{b}{a}}log^{0}n) f(n)1Θ(nlogbalog0n) ⇒ T ( n ) O ( l o g n ) \Rightarrow T(n)O(log n) ⇒T(n)O(logn) 情况3 n l o g b a n^{log_{b}{a}} nlogba 比 f ( n ) f(n) f(n) 增长的慢 f ( n ) f(n) f(n)比 n l o g b a n^{log_{b}{a}} nlogba 增长的更快至少要快 Θ ( n ϵ ) Θ(n^{\epsilon}) Θ(nϵ) 倍且 a f ( n b ) ≤ c f ( n ) af(\frac{n}{b}) \le cf(n) af(bn)≤cf(n) T ( n ) 3 T ( n 4 ) n l o g n T(n)3T(\frac{n}{4})nlogn T(n)3T(4n)nlogn n l o g b a n l o g 4 3 n 0.793 n^{log_{b}{a}}n^{log_{4}3n^{0.793}} nlogbanlog43n0.793, f ( n ) n l o g n Ω ( n l o g 4 3 ϵ ) , ϵ ≤ 0.207 f(n)nlognΩ(n^{log_{4}3\epsilon }),\epsilon \le0.207 f(n)nlognΩ(nlog43ϵ),ϵ≤0.207 a f ( n b ) 3 ( n 4 ) l o g ( n 4 ) ≤ 3 4 n l o g n c f ( n ) , c 3 4 af(\frac{n}{b})3(\frac{n}{4})log(\frac{n}{4}) \le \frac{3}{4}nlogncf(n),c\frac{3}{4} af(bn)3(4n)log(4n)≤43nlogncf(n),c43 ⇒ T ( n ) O ( n l o g n ) \Rightarrow T(n)O(nlogn) ⇒T(n)O(nlogn) 主定理不适用的情况 n l o g b a n^{log_{b}{a}} nlogba 与 f ( n ) f(n) f(n) 的增长率不可比 n l o g b a n^{log_{b}{a}} nlogba 比 f ( n ) f(n) f(n) 增长的快但没有快 O ( n ϵ ) O(n^{\epsilon}) O(nϵ) 倍 n l o g b a n^{log_{b}{a}} nlogba 比 f ( n ) f(n) f(n) 增长的慢但没有慢 O ( n ϵ ) O(n^{\epsilon}) O(nϵ) 倍
