master公式

T(N) = a*T(N/b) + O(Nd)

N：样本量 T：时间复杂度 a：样本量发生的次数 b：将样本量进行分治 c：执行子过程之外其余过程的时间复杂度

用途：计算递归算法的时间复杂度

快速计算

  • logba > d -> 复杂度为O(Nlogba)
  • logba = d -> 复杂度为O(Nd * logN)
  • logba < d -> 复杂度为O(Nd)

适用范围 递归调用使，划分的子过程规模一样， 奇数问题：递归不看常数

任何递归行为都可以变成非递归 递归的本质是 压栈