NOIP 提高 2013 第一轮 第 17 题：（ ）的平均时间复杂度为 O(n n)，其中 n 是待排序的元素个数。

题目

（   ）的平均时间复杂度为 $O(n \log n)$，其中 $n$ 是待排序的元素个数。

答案

A、D

题解

考点定位

本题考「平均复杂度 O(n log n)（不定项）」,对应大纲 4.1.3 排序（难度【1】）。

解题过程

平均 O(n log n)：快速排序 ✓、归并排序 ✓（插入/冒泡 O(n²)）。

答案：A、D。

易错提醒

① 堆排序也是 O(n log n) 但不在选项；② 「平均」对快排关键（最坏 O(n²)）。