最坏情况 Quicksort 二叉树

Question

我仔细研究了 Quicksort 算法的最坏情况。我发现二叉树看起来像这样。

有人知道 2 是从哪里来的吗？

谢谢

Answer 1

2来自1 + 1的加法。每个1来自1个元素的O(n)。 在快速排序中，找到枢轴然后根据枢轴对数组进行排序需要 O(n) 时间。 你最小的数组都是1号的，最后都是1号的。