GESP 五级 · GESP 202506 C++ 五级 第 20 题

归并排序的最好、最坏和平均时间复杂度均为 $O(n \log n)$。

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

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

【考点】分治法｜递归树模型｜时间复杂度分析

1. 🎯 考纲定位

GESP 五级_算法基础_分治法（对应五级C++要求掌握"分治策略与递归实现"）。命题人卡的就是考生对"排序算法复杂度家族"的记忆混淆——把快排、归并、堆排混为一谈，或者误以为"最好情况"只发生在已排序数据上。