算法：分治法和时间复杂度O（nlogn）有何关系？

15
投票

[我认为您问题的所有答案都可能来自Master Theorem。它告诉您几乎所有分而治之的解决方案的复杂性是什么，是的，它必须使用递归树来完成所有工作，使用这些参数，您会发现一些分而治之的解决方案不会具有O（nlogn）复杂性，实际上是divide and conquer algorithms that have O(n) complexity。

仅就问题2而言，总不可能总是有可能比O（n ^ 2）更快地解决某些问题，这取决于问题的性质。

一个在O（nlogn）中运行的算法示例，我认为它具有非常简单，清晰且具有教育意义的运行时分析是MergeSort。可以从下面的图片中了解它：

因此，每个递归步骤将输入分为两部分，然后征服部分取O（n），因此树的每一级花费O（n），棘手的部分可能是递归数的数量登录级别（树高）。这或多或少简单。因此，在每个步骤中，我们将输入均分为n / 2个元素的2个部分，然后递归重复，直到我们得到一些恒定大小的输入为止。因此，在第一个级别上，我们将n / 2除以下一个n / 4，然后除以n / 8，直到达到恒定大小的输入（它将是树的叶子）和最后的递归步骤为止。

因此，在第i个递归步骤中，我们将n / 2 ^ i除，所以让我们在最后一步找到i的值。我们需要n / 2 ^ i = O（1），这对于2个常数c而言是在2 ^ i = cn时实现的，因此我们从两侧取底数为2的对数，得到i = clogn。因此，最后一个递归步骤将是第clogn步，因此树的高度为clogn。

因此，对于每个克隆递归（树）级别，MergeSort的总成本将为cn，这将带来O（nlogn）复杂性。

[通常，您可以确信，只要递归步骤具有O（n）复杂度，您的算法将具有O（nlogn）复杂度，并且可以分解为b个大小为n / b的问题，或者，如果这些部分是n的线性分数，总计为n。在不同的情况下，您很有可能会有不同的运行时。

返回问题2，在QuickSort的情况下，可能会从O（n ^ 2）到\ Theta（nlogn），这恰恰是因为平均随机情况实现了很好的分区，尽管运行时分析甚至比这复杂得多。

不，分治法不能保证O（nlogn）性能。这完全取决于如何在每次递归中简化问题。

在合并排序算法中，原始问题分为两半。然后对结果执行O（n）运算。这就是O（n ...）的来源。

这两个子操作中的每一个现在都有其自己的n，该大小仅为原始大小的一半。每次递归时，您都会将问题再分为两半。这意味着递归数将为log2（n）。这就是O（... logn）的来源。