在我的算法和数据结构中，首先引入了类divide-and-conquer algorithm即merge sort。
在为一个作业实现一个算法时，我想到了几个问题。
使用分治范式实现的任何算法都有O（nLogn）的时间复杂度吗？
是不是该方法中的递归部分有能力将运行在o（n^2）到o（nlogn）中的算法压缩成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 th步骤，因此树具有clogn height。
因此，对于每个CLogn递归（树）级，合并的总成本将是CN，这给出了O（nLogn）的复杂性。
一般来说，只要递归步骤具有O（n）复杂度，你就可以确信你的算法具有O（nLogn）复杂度，并且YO被划分成大小为N/B的B问题，或者更一般，如果部分是N的线性部分，加起来为N。在不同的情况下，很可能你将有不同的运行时间。
回到问题2，在快速排序的情况下，可能会从o（n^2）到θ（nlogn），这正是因为平均随机情况可以实现一个很好的分区，尽管运行时分析比这更复杂。