文章目录
- 使用主定理求时间复杂度
- 主定理
- 直接可用主定理
- 转化之后可以利用主定理
使用主定理求时间复杂度
很多算法最后都可以写出 T ( n ) = a T ( n b ) + f ( n ) ) ( a ≥ 1 , b ≥ 1 ) T(n)=aT(\frac{n}{b}) + f(n)) (a\ge1,b\ge1) T(n)=aT(bn)+f(n))(a≥1,b≥1) 的递推式。针对这种形式的递推式，通常情况下我们直接可以用主定理求解复杂度，而不需要笔和纸的帮助。
主定理
直接可用主定理
-
例1： T ( n ) = 2 T ( n 4 ) + 1 T(n)=2T(\frac{n}{4})+1 T(n)=2T(4n)+1
-
解：由题目得： a = 2 , b = 4 , f ( n ) = 1 a=2,b=4,f(n)=1 a=2,b=4,f(n)=1 ,此时 l o g b a = l o g 4 2 = 0.5 log_{b}a=log_{4}2=0.5 logba=log42=0.5 ,
则 只需要比较 n 0.5 n^{0.5} n0.5和 f ( n ) = 1 f(n)=1 f(n)=1 的大小。
可以利用主定理的第一种情况：
存在常数 ε = 0.5 \varepsilon =0.5 ε=0.5 使得有 f ( n ) = O ( n 0.5 − 0.5 ) f(n)=O(n^{0.5-0.5}) f(n)=O(n0.5−0.5),则 T ( n ) = Θ ( n 0.5 ) T(n)=\Theta(n^{0.5}) T(n)=Θ(n0.5)
-
-
例2： T ( n ) = 2 T ( n 4 ) + n T(n)=2T(\frac{n}{4})+\sqrt{n} T(n)=2T(4n)+n
-
解：由题目得： a
-
