algorithm - 归并排序的大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) 而 merge 函数的大 o 是 n 并且函数 merge 调用了 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}

所以计算了多大，我看到了 master 方法，我知道它的公式，看到了合并排序算法的 3 个级别

但我想一步步计算

Answer 1

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