shida's blog

随着分解的进行，每层复杂度求和的结果都是 cn，这是求得时间复杂度 nlgn 的关键，看到这豁然开朗的感觉！

主定理所谓主定理，就是用来解递归方程的一种方法，此方法可以用来求解大多数递归方程。设递归方程为T(n)=aT(n/b)+f(n)  （其中a≥1，b＞1）主定理：     1. 如果存在常数ε＞0有f(n)=O(n^(logb^a-ε)),则T(n)=Θ(n^(logb^a))；     2. 若f(n)=Θ(n^(logb^a))，则T(n)=Θ(n^(logb^a)logn...