我正在寻找快速排序算法的递归深度或最佳情况的级别。
参考书、Google 和所有其他资源都给了我答案：快速排序算法的最佳情况的递归深度是 log n。然而，画出递归树时，从顶部到基本情况的递归深度应该是log n + 1。那么，为什么 log n 是。
让我们看看霍尔的分区方案，在最好的情况下将偶数大小的数组分区为相等大小的分区。
当数组只有 1 个元素时，不会发生分区。递归树仅存在一个根节点。该树的高度为 0，即 log21.
当你有一个有 2 个元素的数组时，它被划分为两个 1 的数组，这是一个有一个根和两个叶子的递归树。它的高度是1，即log22.
通过归纳我们可以看到，当数组的大小𝑛是2的幂时，递归树的高度是log2𝑛。
也许您使用了深度的替代定义，但维基百科将其定义为：
节点的深度是到其根的路径（即它的根路径）的长度。因此根节点的深度为零...