algorithm - 为什么 QuickSort 是 n log n 的直观解释？

Question

有没有人能够给出一个“简单的英语”直观但正式的解释是什么让 QuickSort n log n ？根据我的理解，它必须遍历 n 个项目，并且它会记录 n 次……我不知道如何用语言来解释为什么它会记录 n 次。

Answer 1

每个分区操作都需要 O(n) 次操作(对数组进行一次传递)。
平均而言，每个分区将数组分成两部分(总和为 log n 次操作)。我们总共有 O(n * log n) 次操作。

IE。在平均日志 n 分区操作中，每个分区需要 O(n) 操作。