GESP 八级 · GESP 202409 C++ 八级 第 14 题

下面程序的 Merge_Sort 函数时间复杂度为（ ）。

void Merge(int a[], int left, int mid, int right) {
    int temp[right - left + 1];
    int i = left;
    int j = mid + 1;
    int k = 0;
    while (i <= mid && j <= right) {
        if (a[i] < a[j])
            temp[k++] = a[i++];
        else
            temp[k++] = a[j++];
    }
    while (i <= mid)
        temp[k++] = a[i++];
    while (j <= right)
        temp[k++] = a[j++];
    for (int m = left, n = 0; m <= right; m++, n++)
        a[m] = temp[n];
}

void Merge_Sort(int a[], int left, int right) {
    if (left == right)
        return;
    int mid = (left + right) / 2;
    Merge_Sort(a, left, mid);
    Merge_Sort(a, mid + 1, right);
    Merge(a, left, mid, right);
}

分析时间复杂度时关注循环层数和每层迭代次数，递归算法则分析递归树。注意最坏/最好/平均情况的区别。

分析复杂度时注意外层循环和内层循环的关联。例如内外两层都到n的循环不一定是O(n²)，要看内层是否每次都在缩小。

【考点】递归｜排序算法｜时间复杂度分析

1. 🎯 考纲定位

GESP 八级"算法与数据结构"模块，排序算法专题。命题人放这道题，就是卡住那些"背了公式但没理解递归合并过程"的考生——八级以前学生容易把归并排序和冒泡排序混淆，或者只记得 $O(n \log n)$ 却说不清为什么。