深度快速排序的复杂性
Quicksort complexities in depth
所以我正在考试，这次考试的很大一部分将是快速排序算法。众所周知，该算法的最佳情况和实际平均情况是：O(nlogn)。最坏的情况是 O(n^2).
As for the worst case scenario I know how to explain it: It happens when the selected pivot would be the smallest or the biggest value in the array, then we would have n quicksort calls which may take最多 n 次（我的意思是分区操作）。我说得对吗？
现在是 best/average 案例。我读过 Cormens 的书，多亏了那本书，我了解了很多东西，但是至于快速排序算法，他专注于如何解释 O(nlogn) 复杂性的数学公式。我只是想知道为什么是 O(nlogn)，而不是进行一些数学证明。现在我只看到一些维基百科的解释，如果我们选择一个每次将数组分成 n/2, n/2+1 部分的枢轴，那么我们就会有一个深度为 logn 的调用树，但我不知道不知道那是不是真的，即使是，那又是为什么呢logn。
我知道网上有很多关于快速排序的资料，但它们只涉及实现，或者只是告诉我复杂性，而不是解释它。
Am I right?
是的。
we would have a call tree of depth logn but I don't know if that is true
是。
why is it logn?
因为我们在每一步都将数组分成两半，导致调用图的深度为 logn。从这个 Intro:
查看树及其深度，它是 logn。想象一下，BST 中的搜索成本 logn，或者为什么在排序数组中的二进制搜索中搜索也需要 logn。
PS：数学讲真话，努力理解它们，你会成为更好的计算机科学家！ =)
对于最佳情况，快速排序在每个分区步骤上将当前数组拆分 50% / 50%（一半），时间复杂度为 O(log2(n)) (1/.5 = 2) ，但是常量 2 被忽略了，所以它是 O(n log(n).
如果每个分区步骤产生 20% / 80% 的拆分，那么最坏情况下的时间复杂度将基于 80% 或 O(n log1.25(n)) (1/.8 = 1.25) ，但常量 1.25 被忽略，所以它也是 O(n log(n))，即使它比排序 100 万个元素的 50% / 50% 分区情况慢大约 3 倍。
当分区拆分仅在每个分区步骤中线性减少分区大小时，就会出现 O(n^2) 时间复杂度。最简单和最坏的情况示例是每个分区步骤仅删除 1 个元素。
所以我正在考试，这次考试的很大一部分将是快速排序算法。众所周知，该算法的最佳情况和实际平均情况是：O(nlogn)。最坏的情况是 O(n^2).
As for the worst case scenario I know how to explain it: It happens when the selected pivot would be the smallest or the biggest value in the array, then we would have n quicksort calls which may take最多 n 次（我的意思是分区操作）。我说得对吗？
现在是 best/average 案例。我读过 Cormens 的书，多亏了那本书，我了解了很多东西，但是至于快速排序算法，他专注于如何解释 O(nlogn) 复杂性的数学公式。我只是想知道为什么是 O(nlogn)，而不是进行一些数学证明。现在我只看到一些维基百科的解释，如果我们选择一个每次将数组分成 n/2, n/2+1 部分的枢轴，那么我们就会有一个深度为 logn 的调用树，但我不知道不知道那是不是真的，即使是，那又是为什么呢logn。
我知道网上有很多关于快速排序的资料，但它们只涉及实现，或者只是告诉我复杂性，而不是解释它。
Am I right?
是的。
we would have a call tree of depth
lognbut I don't know if that is true
是。
why is it
logn?
因为我们在每一步都将数组分成两半，导致调用图的深度为 logn。从这个 Intro:
查看树及其深度，它是 logn。想象一下，BST 中的搜索成本 logn，或者为什么在排序数组中的二进制搜索中搜索也需要 logn。
PS：数学讲真话，努力理解它们，你会成为更好的计算机科学家！ =)
对于最佳情况，快速排序在每个分区步骤上将当前数组拆分 50% / 50%（一半），时间复杂度为 O(log2(n)) (1/.5 = 2) ，但是常量 2 被忽略了，所以它是 O(n log(n).
如果每个分区步骤产生 20% / 80% 的拆分，那么最坏情况下的时间复杂度将基于 80% 或 O(n log1.25(n)) (1/.8 = 1.25) ，但常量 1.25 被忽略，所以它也是 O(n log(n))，即使它比排序 100 万个元素的 50% / 50% 分区情况慢大约 3 倍。
当分区拆分仅在每个分区步骤中线性减少分区大小时，就会出现 O(n^2) 时间复杂度。最简单和最坏的情况示例是每个分区步骤仅删除 1 个元素。