递归的本质是系统帮我们进行了压栈,栈的名字叫做系统栈。但系统栈的空间十分有限,因此在工程上我们需要把递归改写成用内存中的栈来模拟系统压栈,以此来实现非递归。
master公式又叫主定理,是一种估算递归时间复杂度的公式。但有个前提条件:只有是子问题规模相同的递归才能使用。
T(N) = a * T(N / b)+ O(N ^ c), a 、b 、c都是常数。
a是调用的子问题的次数
b是问题被分为多少个子问题的个数
c是调用之外的时间复杂度
如果logba < c, 复杂度为: (N ^ c)。
如果logba > c, 复杂度为: (N ^ logba)。
如果logba == c, 复杂度为: (N ^ c * logN)。
补充:T(N) = a * T(N / b)+ O(N * logN),时间复杂度是O(N * (logN) ^ 2)。