在我的算法和数据结构类(class)中，引入了第一个分而治之算法，即归并排序。
在为作业实现算法时，我想到了几个问题。
使用分而治之范式实现的算法是否具有 O(nlogn) 的时间复杂度？
是否该方法中的递归部分能够将 O(n^2) 中运行的算法压缩到 O(nlogn)？
是什么让这样的算法首先在 O(nlogn) 中运行？
对于 (3)，我假设这与递归树和可能的递归数有关。有人可能会用 O(nlogn) 中运行的简单分而治之算法来展示复杂性的实际计算方式吗？
干杯， 安德鲁
最佳答案
我认为您问题的所有答案都可能来自 Master Theorem它会告诉你几乎所有你拥有的分而治之解决方案的复杂性是多少，是的，它必须用递归树做所有事情，通过使用参数你会发现一些分而治之的解决方案不会有O(nlogn)复杂度，其实有divide and conquer algorithms that have O(n) complexity .
关于问题 2，这并不总是可能的，事实上，有些问题被认为不可能比 O(n^2) 更快地解决，这取决于问题的性质。
在 O(nlogn) 中运行并且我认为具有非常简单、清晰且具有教育意义的运行时分析的算法示例是 MergeSort .从下图可以掌握:
所以每个递归步骤输入被分成两部分，然后征服部分花费 O(n)，所以树的每一层花费 O(n)，棘手的部分可能是递归级别(树高)是 logn。这或多或少是简单的。因此，在每一步中，我们将输入分成两部分，每部分 n/2 个元素，并递归重复，直到我们有一些恒定大小的输入。因此，在第一级我们划分 n/2，在下一个 n/4，然后 n/8，直到我们达到一个恒定大小的输入，这将是树的一个叶子，最后的递归步骤。
所以在第 i 个递归步骤中，我们除以 n/2^i，所以让我们在最后一步中找到 i 的值。我们需要 n/2^i = O(1)，这是在 2^i = cn 时实现的，对于某个常数 c，所以我们从两边取以 2 为底的对数，得到 i = clogn。所以最后的递归步骤将是第 clogn 步，因此树具有 clogn 高度。
因此，对于每个 clogn 递归(树)级别，MergeSort 的总成本将为 cn，这给出了 O(nlogn) 复杂度。
一般来说，只要递归步骤具有 O(n) 复杂度，并且将问题分成大小为 n/b 或更一般的 b 个问题，您就可以确信您的算法具有 O(nlogn) 复杂度，如果这些部分是 n 的线性分数加起来等于 n。在不同的情况下，您很可能会有不同的运行时。
回到问题 2，在 QuickSort 的情况下，一个人可能从 O(n^2) 到\Theta(nlogn) 正是因为平均随机情况实现了一个很好的分区，尽管运行时分析比这更复杂.
关于performance - 算法 : how do divide-and-conquer and time complexity O(nlogn) relate?，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/29927439/