剖析递归行为和递归行为时间复杂度的估算

剖析递归行为和递归行为时间复杂度的估算 master公式：也叫主定理。它提供了一种通过渐近符号表示递推关系式的方法。 应用Master定理可以很简便的求解递归方程。

master公式的使用 递归行为形如: T(N) = a*T(N/b) + O(N^d) 均可用下面推到出时间复杂度

• (1) log(b,a) > d -> 复杂度为O(N^log(b,a))
• (2) log(b,a) = d -> 复杂度为O(N^d * logN)
• (3) log(b,a) < d -> 复杂度为O(N^d)

T(N)：       递归的时间复杂度 N：            递归行为的规模|样本数量 N/b：         递归后子过程的规模 (b指的是子过程分为几块,比如递归比较运算是左右两块) a:               子过程调用次数 aT(N/b):    所有子过程的时间复杂度 O(N^d) :    除去子过程之外剩下过程的时间复杂度

注意： 1.使用master公式推到时间复杂度必须保证每次划分的子工程的规模是一样的 如果形如:T(N) = T(N/3) + T(N/2) 这样一次分3份 一次份2份,是不可以用master推导的