当 n = 1 时，f(n) = 1;
当 n > 1 时，f(n) = 2*f(n/2) + n ；
求f(n)的递归式
首先为什么要求递归式呢？ 是因为在计算机中有些算法是使用递归方式实现，我们需要计算该递归方式的时间复杂度，来评定算法的优劣。
下面我们来求f(n)的递归式，什么是递归式呢？就是等号左边只有f(n),等号右边只有关于n的表达式。
看到f(n) = 2*f(n/2) + n 这个式子你想到了什么，是不是将f(n/2)变掉。
如何将f(n/2) 变掉呢？
可以假设 n = 2k ，那么 f(n) = f(2k) 然后假设 f(2k) = h(k), f(n/2) = f(k) = h(k/2) 显然这么做毫无意义。
也可以假设 n = 2^k ,那么 f(n) = f(2^k) 然后假设 f(2^k) = h(k), f(n/2) = f(2^(k-1)) = h(k-1)。
那么 f(n) = 2*f(n/2) + n => h(k) = 2*h(k-1) + 2^k ;
另外 n = 1 时，f(n) = 1 ，1 = 2^k => k = 0 时 h(k) = 1 ;
换句话说就是
将
当 n = 1 时，f(n) = 1;
当 n > 1 时，f(n) = 2*f(n/2) + n ；
=>
n = 2^k ；
当 k = 0 时 h(k) = 1 ;
当 k > 0 时 h(k) = 2*h(k-1) + 2^k ；
h(1) = 2*h(0) + 2^1
h(2) = 2*h(1) + 2^2
h(3) = 2*h(2) + 2^3
h(3）= 2*(2*h(1) + 2^2) + 2^3
= 2^2 * h(1) + 2^3 + 2^3
= 2^2 * (2*h(0) + 2^1) + 2^3 + 2^3
= 2^3 * h(0) + 2^3 + 2^3 + 2^3
= 4 * 2^3
h(k) = 2^k * h(0) + k * (2^k)
= (k + 1) * 2^k
我们得到了 h(k) = (k + 1) * 2^k ,因为 n = 2^k => k = log2 n , f(n) = h(k)
f(n) = (log2 n + 1) * 2^log2 n
= (log2 n + 1) * n
= n * log2 n + n
于是得到了 f(n) = n * log2 n + n 。
在得到了递归式之后，时间复杂度 O(nlog2 n)
延伸知识：
求等差数列的前n项和，求等比数列的前n项和
等差数列 A1 = 1，A2 = 2， A3 = 3 …… An = n ; 等差数列 每一项都是前一项加一个常数，这里是1
Sn = A1 + A2 + A3 + …… + An
= 1 + 2 + 3 + …… + n
以下是等差数列的前n项和的推导过程
Sn = 1 + 2 + 3 + …… + n
Sn = n + (n - 1) + (n - 2) + …… + 1
Sn + Sn = (1 + n) + (2 + (n - 1)) + (3 + (n - 2)) + …… + (1 + n)
2 * Sn = n * (n + 1)
Sn = n * (n + 1)/2
等比数列 A1 = 2^1，A2 = 2^2， A3 = 2^3 …… An = 2^n ; 等比数列 每一项都是前一项乘以个常数，这里是2
Sn = A1 + A2 + A3 + …… + An
= 2^1 + 2^2 + 2^3 + …… + 2^n
Sn = 2^1 + 2^2 + 2^3 + …… + 2^n
2 * Sn = 2^2 + 2^3 + …… + 2^n + 2^(n + 1)
2 * Sn - Sn = 2^(n + 1) - 2^1
Sn = (2^(n + 1) - 2^1 ) / (2 - 1)