为什么合并排序算法时间复杂性T(n)=2T(n/2)+O(n)就会得出T(n)=nlogn怎么通过T(n)=2T(n/2)+O(n)得出nlogn的呢,不懂nlogn是怎么来的

为什么合并排序算法时间复杂性T(n)=2T(n/2)+O(n)就会得出T(n)=nlogn怎么通过T(n)=2T(n/2)+O(n)得出nlogn的呢,不懂nlogn是怎么来的
为什么合并排序算法时间复杂性T(n)=2T(n/2)+O(n)就会得出T(n)=nlogn
怎么通过T(n)=2T(n/2)+O(n)得出nlogn的呢,不懂nlogn是怎么来的

为什么合并排序算法时间复杂性T(n)=2T(n/2)+O(n)就会得出T(n)=nlogn怎么通过T(n)=2T(n/2)+O(n)得出nlogn的呢,不懂nlogn是怎么来的
画个图：
n
/ \
n/2 n/2
/ \ / \
n/4 n/4 n/4 n/4
/ \ / \ / \ / \
n/8 n/8 n/8 n/8 n/8 n/8 n/8 n/8
树高logn,每层加起来都是n,一共是logn×n
上面是n为2的幂时的特殊情况.对于一般情况,同样可证.