网站地图制作怎么做,wordpress 登录 验证码,管理微信软件,wordpress设置文章排序编写算法时#xff0c;可能因为对自己代码的复杂度的不清晰而导致错失良机#xff0c;对于普通的递推或者说循环的代码#xff0c;仅用简单的调和级数或者等差数列和等比数列即可分析#xff0c;但是对于递归的代码#xff0c;简单的递归树法并不方便#xff0c;理解并记…编写算法时可能因为对自己代码的复杂度的不清晰而导致错失良机对于普通的递推或者说循环的代码仅用简单的调和级数或者等差数列和等比数列即可分析但是对于递归的代码简单的递归树法并不方便理解并记下Master定理可以让事情变得轻松。
写此文以作笔记如有错误请联系博主。
Master 定理基本形式
对于一个递归式 T ( n ) a T ( n b ) f ( n ) T(n) aT(\frac{n}{b}) f(n) T(n)aT(bn)f(n)其中 a ≥ 1 a \geq 1 a≥1 和 b 1 b 1 b1 是常数 f ( n ) f(n) f(n) 是一个给定的函数 Master 定理帮助我们确定 T ( n ) T(n) T(n) 的渐进界。
有三种情况
如果 f ( n ) O ( n c ) f(n) O(n^c) f(n)O(nc)其中 c log b a c \log_b{a} clogba 那么 T ( n ) Θ ( n log b a ) T(n) \Theta(n^{\log_b{a}}) T(n)Θ(nlogba)。如果 f ( n ) Θ ( n c ) f(n) \Theta(n^c) f(n)Θ(nc)其中 c log b a c \log_b{a} clogba 那么 T ( n ) Θ ( n c log n ) T(n) \Theta(n^c\log{n}) T(n)Θ(nclogn)。如果 f ( n ) Ω ( n c ) f(n) \Omega(n^c) f(n)Ω(nc)其中 c log b a c \log_b{a} clogba且满足一定的平滑条件即 a f ( n / b ) ≤ k f ( n ) af(n/b) \leq kf(n) af(n/b)≤kf(n) 对于某个常数 k 1 k 1 k1 和充分大的 n n n 那么 T ( n ) Θ ( f ( n ) ) T(n) \Theta(f(n)) T(n)Θ(f(n))。
特定的例子
考虑 T ( n ) 2 T ( n 2 ) O ( n log n ) T(n) 2T(\frac{n}{2}) O(n\log{n}) T(n)2T(2n)O(nlogn)这里 a 2 a 2 a2, b 2 b 2 b2, 和 f ( n ) n log n f(n) n\log{n} f(n)nlogn。显然 f ( n ) f(n) f(n) 不符合 Master 定理的标准形式中的 f ( n ) O ( n c ) f(n) O(n^c) f(n)O(nc)因为增长速度比任何 n c n^c nc 形式要快。因此直接应用标准 Master 定理的三种情况并无法获得解答。
在这种特殊情况下 T ( n ) 2 T ( n 2 ) n log n T(n) 2T(\frac{n}{2}) n\log{n} T(n)2T(2n)nlogn 的时间复杂度实际上是 O ( n ( log n ) 2 ) O(n(\log{n})^2) O(n(logn)2)。如有兴趣请自行查找证明过程。
