algorithm - 最坏情况快速排序二叉树

Question

我正在仔细研究快速排序算法的最坏情况。我发现二叉树看起来像这样。

有人知道 2 来自哪里吗？

谢谢

Answer 1

2 来自 1 + 1 相加。每个 1 来自 O(n) 的 1 个元素。 在快速排序中，找到主元后，然后相对于主元对数组进行排序需要 O(n) 时间。 最小的数组每个大小都是 1，最后每个数组的大小都是 1。