递归的时间复杂度
Master定理
有些算法在处理一个较大规模的问题时，往往会把问题拆分成几个子问题，对其中的一个或多个问题递归地处理，并在分治之前或之后进行一些预处理、汇总处理。这时候我们可以得到关于这个算法复杂度的一个递推方程，求解此方程便能得到算法的复杂度。其中很常见的一种递推方程就是这样的：
设常数a >= 1，b > 1，f(n)为函数，T(n)为非负整数，T(n) = a T(n / b) + f(n)，则有：
递归树
没事间写QAQ………
有些算法在处理一个较大规模的问题时，往往会把问题拆分成几个子问题，对其中的一个或多个问题递归地处理，并在分治之前或之后进行一些预处理、汇总处理。这时候我们可以得到关于这个算法复杂度的一个递推方程，求解此方程便能得到算法的复杂度。其中很常见的一种递推方程就是这样的：
设常数a >= 1，b > 1，f(n)为函数，T(n)为非负整数，T(n) = a T(n / b) + f(n)，则有：
没事间写QAQ………
评论