分治法时间复杂度求解秘籍

        分治法的道理非常简单，就是把一个大的复杂的问题分为a(a>1)个形式相同的子问题，这些子问题的规模为n/b，如果分解或者合并的复杂度为f(n)，那么总的时间复杂度可以表示为：

     那么如何求解时间复杂度呢？

我们上面的求解方式都是递推求解，写出其递推式，最后求出结果。

例如：合并排序算法的时间复杂度递推求解：

递归树求解方式其实和递推求解一样，只是递归树更清楚直观的显示出来，更能够形象的表达每层分解的结点和每层产生的成本有多少。例如：如图1所示。

图1 分治递归树

大师解法

图2 大师解法递归树

时间复杂度=叶子数*T(1)+成本和

时间复杂度=成本和。

现在我们只需要观察每层产生的成本的发展趋势，是递减的还是递增的，还是每层都一样？每层成本的公比为。     

成本的公比小于1，时间复杂度按第1层计算；

成本的公比大于1，时间复杂度按最后1层计算；

成本的公比等于1，时间复杂度按第1层*树高计算；

大师解法：

递归树如图3所示。

图3 大师解法递归树

    首先从递归树中观察每层产生的成本发展趋势，每层的成本有时不是那么有规律，需要仔细验证才行。比如我们得到第3层是(5/16)2n2，需要验证第4层是(5/16)3n2，…。经过验证，我们发现每层成本是一个等比数列，公比为5/16