数据结构与算法 · 单选题 · 第 49 题
计算机基础面试八股 · 第 49 题
快速排序的平均时间复杂度和最坏时间复杂度分别是?
- A平均和最坏都是 O(n log n)
- B平均 O(n log n),最坏 O(n²)
- C平均 O(n),最坏 O(n log n)
- D平均和最坏都是 O(n²)
答案
B B. 平均 O(n log n),最坏 O(n²)
解析
每次划分大致把数组一分为二时,递归深度约为 log n,每层总工作量是 O(n)。如果每次都选到最大或最小元素作基准(比如对已排序数组固定选第一个元素),深度退化为 n,复杂度变成 O(n²)。随机选基准或三数取中可以大大降低遇到最坏情况的概率;平均和最坏都是 O(n log n) 的是归并排序和堆排序。