大O合并排序

Question

void mergeSort(int arr[], int l, int r) 
{ 
   if (l < r) 
    { 
        // Same as (l+r)/2, but avoids overflow for 
        // large l and h 
        int m = l+(r-l)/2; 

        // Sort first and second halves 
        mergeSort(arr, l, m); 
        mergeSort(arr, m+1, r); 

        merge(arr, l, m, r); 
    } 
} 

这是合并排序的代码

我不明白为什么它的大o是n log(n)，而合并函数的大o是n，函数合并被调用7次，即n-1。

如果我们有以下数组作为输入{8,7,6,5,4,3,2,1}

那么合并的调用将是

合并(8，7，6，5，4，3，2，1}，0,0,1)

合并({7，8，6，5，4，3，2，1}，2,2,3)

合并(7，8，5，6，4，3，2，1}，0,1,3)

合并({5，6，7，8，4，3，2，1}，4,4,5)

合并({5，6，7，8，3，4，2，1}，6,6,7)

合并({5，6，7，8，3，4，1，2}，4,5,7)

合并({5，6，7，8，1，2，3，4}，0,3,7)

结果是{1,2,3,4,5,6,7,8}

所以计算得有多大，我看到了主方法，我知道了它的公式，并看到了合并排序算法的三个级别。

但我想一步一步地计算

Answer 1

用Mergesort对长度为n的数组排序的时间复杂度是T(n)=2 * T(n/2) + O(n)，其中T是时间复杂度函数，2 * T(n/2)是递归调用，O(n)合并了这两个递归。如果您愿意的话，您现在可以通过归纳法在m = log2(n)上证明m = log2(n)。这里有一个这样的证明：https://www.cs.auckland.ac.nz/compsci220s1c/lectures/2016S1C/CS220-Lecture09.pdf

Answer 2

查看O(nlogn)的一个简单方法是使用递归树，因为T(n) = O(n) + 2T(n/2)可以为T(n)绘制递归树，如下所示：

             n
          /     \
     (n/2)       (n/2)
     /   \       /   \
 (n/4)  (n/4) (n/4) (n/4)
            .
            .
            .

树的每一行和为n (n = n，n/2 + n/2 = n，n/4+n/4=n，.)

并且有log(n)行(因为在每一行n除以2)，所以树中节点的总和是：O(nlogn)