algorithm - 证明 3-Way Quicksort Big-O Bound

Question

对于 3 向快速排序(双轴快速排序)，我将如何找到 Big-O 边界？谁能告诉我如何推导它？

Answer 1

发现算法的复杂性与证明之间存在细微差别。

要找到这个算法的复杂性，您可以按照 amit 在另一个答案中所说的那样做:您知道在平均中，您将问题拆分为n 分成三个大小为 n/3 的小问题，因此您将平均在 è log_3(n)` 步内得到大小为 1 的问题。根据经验，您将开始感受这种方法，并能够仅通过考虑所涉及的子问题来推断算法的复杂性。

要证明此算法在平均情况下以 O(nlogn) 运行，您使用 Master Theorem .要使用它，您必须编写递归公式，给出排序数组所花费的时间。正如我们所说，对大小为 n 的数组进行排序可以分解为对三个大小为 n/3 的数组进行排序加上构建它们所花费的时间。可以这样写:

T(n) = 3T(n/3) + f(n)

其中 T(n) 是一个函数，它为大小为 n 的输入(实际上是所需的基本操作数)提供分辨率“时间”，并且 f(n) 给出将问题拆分为子问题所需的“时间”。

对于 3 向快速排序，f(n) = c*n 因为您遍历数组，检查每个项目的放置位置并最终进行交换。这使我们处于 Case 2 of the Master Theorem ，其中说明如果 f(n) = O(n^(log_b(a)) log^k(n)) 对于某些 k >= 0(在我们的case k = 0) 然后

T(n) = O(n^(log_b(a)) log^(k+1)(n)))

作为a = 3 和b = 3(我们从递归关系中得到这些，T(n) = aT(n/b)), 这简化为

T(n) = O(n log n)

这是一个证明。