如何用Σ符号逐步推导迭代式归并排序O(nlogn)时间复杂度

迭代式归并排序的C语言代码 #

void merge(int arr[], int l, int m, int r); 

int min(int x, int y) { return (x<y)? x :y; } 

void mergeSort(int arr[], int n) 
{ 
   int curr_size;  
   int left_start; 

   for (curr_size=1; curr_size<=n-1; curr_size = 2*curr_size) 
   { 
       for (left_start=0; left_start<n-1; left_start += 2*curr_size) 
       {
           int mid = min(left_start + curr_size - 1, n-1);
           int right_end = min(left_start + 2*curr_size - 1, n-1); 
           merge(arr, left_start, mid, right_end); 
       } 
   } 
} 

void merge(int arr[], int l, int m, int r) 
{ 
    int i, j, k; 
    int n1 = m - l + 1; 
    int n2 =  r - m;
    int L[n1], R[n2]; 
    for (i = 0; i < n1; i++) 
        L[i] = arr[l + i]; 
    for (j = 0; j < n2; j++) 
        R[j] = arr[m + 1+ j]; 

    i = 0; 
    j = 0; 
    k = l; 
    while (i < n1 && j < n2) 
    { 
        if (L[i] <= R[j]) 
        {
            arr[k] = L[i]; 
            i++; 
        } 
        else
        { 
            arr[k] = R[j]; 
            j++; 
        } 
        k++; 
    } 
    while (i < n1) 
    { 
        arr[k] = L[i]; 
        i++; 
        k++;
    } 
    while (j < n2) 
    { 
        arr[k] = R[j]; 
        j++; 
        k++; 
    } 
}

时间复杂度推导（使用Σ符号） #

1. 确定迭代的总层数 #

迭代归并排序的外层循环控制curr_size（当前归并的子数组长度），从1开始每次翻倍，直到curr_size >= n。设总层数为t，则满足：
$$2^t \geq n$$
解得 $t = \lceil \log_2 n \rceil$，近似为 $\log_2 n$ 层（时间复杂度分析中忽略常数和取整操作）。

2. 分析单一层的时间开销 #

对于第k层（k从0开始计数，对应curr_size = 2^k）：

• 每一次merge操作处理的是两个长度为2^k的子数组，合并后的区间长度最多为2*2^k = 2^{k+1}，merge操作的时间复杂度为线性时间，即 $O(2^{k+1})$。
• 该层共有 $\lceil \frac{n}{2^{k+1}} \rceil$ 个这样的merge操作（最后一个区间可能不足2^{k+1}，但不影响复杂度量级）。
• 该层的总时间开销为：
  $$\lceil \frac{n}{2^{k+1}} \rceil \times O(2^{k+1}) = O(n)$$
  原因是所有merge操作处理的元素总数为n，线性时间的总开销只和元素总数相关，与子数组拆分方式无关。

3. 总时间复杂度求和 #

总时间T(n)为所有层的时间开销之和，用Σ符号表示为：
$$T(n) = \sum_{k=0}^{t-1} O(n)$$
代入t = \log_2 n，可得：
$$T(n) = O(n) \times \log_2 n = O(n \log n)$$

内容的提问来源于stack exchange，提问作者Arooj