标签: 概率分析 - 文档

概率分析共 2 篇文章

为什么快速排序最坏情况O(n²)但平均O(n log n)：概率分析

2026-07-25 02:37:02

为什么快速排序最坏情况$On^2$但平均$On \log n$：概率分析快速排序是实践中使用最广泛的排序算法之一。它的平均时间复杂度是 $On \log n$，但最坏情况下会退化为 $On^2$。这个性能差异让许多人感到困惑：为什么同一个算法会有如此大的表现波动？答案隐藏在主元选择的随机性中。 1

快速排序时间复杂度最坏情况

35 0

快速排序的平均时间复杂度O(n log n)的期望分析

2026-07-14 20:40:15

快速排序的平均时间复杂度On log n的期望分析快速排序的平均时间复杂度 On log n 并非偶然，而是算法设计与概率分析共同作用的结果。本指南将手把手拆解这一期望分析的核心步骤，揭示其高效的根本原因。 1. 理解快速排序的核心机制快速排序的核心是分治法，其性能完全取决于划分步骤的效果

快速排序平均时间复杂度期望分析

39 0

概率分析 共 2 篇文章