个人网站备案材料填写,公司做网站一般多少钱运营,python基础教程在线阅读,免费电商网站建设平台主定理#xff08;Master Theorem#xff09;是用于分析递归算法时间复杂度的一个重要工具。它适用于形式化定义的一类递归关系#xff0c;通常采用分治策略解决问题的情况。 假设我们有一个递归算法#xff0c;它将问题分解成 a a a 个子问题#xff0c;每个子问题的规模…主定理Master Theorem是用于分析递归算法时间复杂度的一个重要工具。它适用于形式化定义的一类递归关系通常采用分治策略解决问题的情况。 假设我们有一个递归算法它将问题分解成 a a a 个子问题每个子问题的规模是原问题的 1 b \frac{1}{b} b1解决每个子问题的代价是 f ( n ) f(n) f(n)而将子问题的解合并成原问题的解的代价是 g ( n ) g(n) g(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) 其中 a ≥ 1 b 1 a ≥ 1b 1 a≥1b1 是常数 f ( n ) f(n) f(n) 是解决一个规模为 n n n 的问题所需的工作量 g ( n ) g(n) g(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 ) 4 T ( n 2 ) n T(n)4T(\frac{n}{2})n T(n)4T(2n)n 其中 a 4 ≥ 1 b 2 1 f ( n ) n l o g 2 4 2 1 a 4\ge1b 21f(n) nlog_{2}421 a4≥1b21f(n)nlog2421。
根据主定理的第一种情况 f ( n ) O ( n l o g b ( a − ε ) ) f(n) O(n^ {log_b(a - ε)}) f(n)O(nlogb(a−ε))
可得 n O ( n l o g 2 4 − ε ) O ( n 2 ) nO(n^{log_{2}4−ε})O(n^{2}) nO(nlog24−ε)O(n2) ∴ T ( n ) Θ ( n 2 ) \therefore T(n)Θ(n^{2}) ∴T(n)Θ(n2) 情况二 T ( n ) 4 T ( n 2 ) n 2 T(n)4T(\frac{n}{2})n^{2} T(n)4T(2n)n2 其中 a 4 ≥ 1 b 2 1 f ( n ) n 2 l o g 2 4 2 a 4\ge1b 21f(n) n^{2}log_{2}42 a4≥1b21f(n)n2log242。
根据主定理的第二种情况 f ( n ) O ( n l o g b ( a ) l o g k n ) f(n) O(n^ {log_b(a )}log^{k}n) f(n)O(nlogb(a)logkn)
可得 n 2 Θ ( n l o g 2 4 l o g 0 n ) Θ ( n 2 ) n^{2}Θ(n^{log_{2}4}log^{0}n)Θ(n^{2}) n2Θ(nlog24log0n)Θ(n2) ∴ T ( n ) Θ ( n 2 l o g n ) \therefore T(n)Θ(n^{2}logn) ∴T(n)Θ(n2logn) 情况三 T ( n ) 2 T ( n 2 ) n 2 T(n)2T(\frac{n}{2})n^{2} T(n)2T(2n)n2 其中 a 2 ≥ 1 b 2 1 f ( n ) n 2 l o g 2 2 1 2 a 2\ge1b 21f(n) n^{2}log_{2}212 a2≥1b21f(n)n2log2212。
根据主定理的第三种情况 f ( n ) Ω ( n l o g b ( a ) ε ) f(n) Ω(n^ {log_b(a )ε }) f(n)Ω(nlogb(a)ε)
可得 n 2 Ω ( n l o g 2 2 ε ) Ω ( n 1 ε ) n^{2}Ω(n^{log_{2}2ε})Ω(n^{1ε}) n2Ω(nlog22ε)Ω(n1ε)
但我们还需要检查是否满足 a ⋅ f ( n b ) ≤ c ⋅ f ( n ) a · f(\frac{n}{b}) ≤ c · f(n) a⋅f(bn)≤c⋅f(n) 的条件 2 ⋅ ( n / 2 ) 2 ≤ c ⋅ n 2 n 2 / 2 ≤ c ⋅ n 2 1 / 2 ≤ c 2·(n/2)^{2}≤c·n^{2}\\ n^{2}/{2}≤c·n^{2}\\ 1/2≤c 2⋅(n/2)2≤c⋅n2n2/2≤c⋅n21/2≤c
对于任何小于 1/2 的常数 c c c上述不等式都成立 ∴ T ( n ) Θ ( n 2 ) \therefore T(n)Θ(n^{2}) ∴T(n)Θ(n2)
