1

对于 3 路快速排序（双轴快速排序），我将如何找到 Big-O 界限？谁能告诉我如何推导它？

4

2 回答 2

2

嗯，同样的证明实际上成立。

每次迭代将数组拆分为 3 个子列表，这些子列表的大小平均为n/3每个。
因此 - 需要的迭代次数是log_3(n)因为你需要找到你做的次数，(((n/3) /3) /3) ...直到你达到一个。这为您提供了公式：

n/(3^i) = 1

哪个是满意的i = log_3(n)。

每次迭代仍在遍历所有输入（但在不同的子列表中） - 与快速排序相同，它为您提供O(n*log_3(n)).

由于log_3(n) = log(n)/log(3) = log(n) * CONSTANT，您会发现运行时间是O(nlogn)平均的。

请注意，即使您采用更悲观的方法来计算子列表的大小，通过最小化均匀分布 - 它仍然会为您提供大小为 1/4 的第一个子列表、大小为 1/2 的第二个子列表和最后一个子列表大小 1/4（均匀分布的最小值和最大值），这将再次衰减到log_k(n)迭代（具有不同的 k>2） - 这将O(nlogn)再次产生整体。

形式上，证明将类似于： 对于每个，对于某些常量 c_1，N_1，
每次迭代最多需要运行操作。（大 O 表示法的定义，以及每次迭代不包括递归的说法。说服自己为什么这是真的。请注意，在这里 - “迭代”是指算法在某个“级别”中完成的所有迭代，而不是在单个递归调用）。c_1* nn>N_1O(n)

如上所示，您有log_3(n) = log(n)/log(3) 平均情况下的迭代（此处采用乐观版本，可以使用相同的悲观原则）

现在，我们得到算法的运行时间T(n)为：

for each n > N_1:
T(n) <= c_1 * n * log(n)/log(3) 
T(n) <= c_1 * nlogn

根据大 O 符号的定义，它意味着T(n)is in O(nlogn)with M = c_1and N = N_1。
量子点

于 2012-10-24T06:37:22.137 回答
2

找到算法的复杂性和证明它之间存在细微差别。

要找到这个算法的复杂性，你可以按照阿米特在另一个答案中所说的那样做：你知道，平均而言，你将你的大小问题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-Way 快速排序，f(n) = c*n因为您遍历数组，所以检查每个项目的放置位置并最终进行交换。这将我们置于主定理的案例 2中，它指出如果f(n) = O(n^(log_b(a)) log^k(n))对于某些k >= 0（在我们的案例中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)

这就是一个证明。

于 2012-10-24T08:15:28.893 回答