快速排序（Quicksort）Ω(n logn)与O(n²)的理解是否正确？

你的理解完全正确！咱们把这几个复杂度记号的逻辑掰扯清楚，就一目了然了：

• 大Ω（Big-Omega）记号：它定义的是算法运行时间的下界——换句话说，无论输入是什么样的，算法的运行时间都不会比这个下界更短。快速排序在最优场景下（比如每次划分都能把数组切成两个规模相近的子数组，比如选中位数当基准），时间复杂度是n log(n)，这是它能达到的最快效率，所以用Ω(n log(n))来描述是完全准确的，这代表快速排序不可能比n log(n)更快。

• 大O（Big-O）记号：它定义的是算法运行时间的上界——也就是算法在最坏场景下的运行时间上限。快速排序在极端输入（比如数组已经完全有序，还每次选第一个元素当基准）时，会退化成O(n²)的时间复杂度，所以O(n²)这个上界描述也是正确的。

• 为什么平时大家常说快速排序是O(n log(n))？
  这是因为在平均情况下，快速排序的时间复杂度是Θ(n log(n))（Θ记号同时约束了上界和下界）。实际开发中，我们遇到的输入大多是随机分布的，再加上一些优化手段（比如随机选基准、三数取中选基准），几乎不会碰到O(n²)的最坏情况，所以大家习惯用平均情况的复杂度来指代它。

内容的提问来源于stack exchange，提问作者user7826451