T(n)=2T(n/2)+n=o(nlogn)

大o记号：大O符号（Big O notation）是用于描述函数渐进行为的数学符号。更确切地说，它是用另一个（通常更简单的）函数来描述一个函数数量级的渐近上界（百度百科）

T(n)=2T(n/2)+n

设n=2^k
T(n/2)=2T(n/2^2)+n/2
T(n/2^2)=2T(n/2^3)+n/2^2
T(n)=2T(n/2)+n=2^2T(n/2^2)+2*n/2+n=2^3T(n/2^3)+2^2*n/2^2+2*n/2+n
    =2^kT(1)+kn=nT(1)+kn=n(logn+T(1))=o(nlogn)
    注：T(1)是常数，可以忽略