Master定理-实用向简解

Master定理作用:处理函数的增长问题,整理由递推式表示的函数增长.主要应用于时间复杂度的化简.

一般形式:(b∈R)

整理到:(log的底视具体情况而定,一般不写)求l,m

情况1:
若f(N)中没有logN
即存在k>0使得

那么,

情况2:
若f(N)中有logN
即存在p≥1使得

那么,

以上.