我认为你的问题的所有答案可能都来自于主定理它告诉你几乎所有分治解决方案的复杂性，是的，它必须用递归树做所有事情，通过使用参数你会发现一些分治解决方案不会有o（nlogn）复杂性，事实上，有一些分治算法具有o（n）复杂度。
就问题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高度。
因此，对于每个clogn递归（tree）级别，mergesort的总开销将是cn，这就给出了o（nlogn）复杂性。
一般来说，只要递归步骤有o（n）复杂度，您就可以确信您的算法将有o（nlogn）复杂度；如果部分是n的线性分数，加起来等于n，那么您可以将其划分为大小为n/b的b个问题，甚至更一般。在不同的情况下，很可能会有不同的运行时。
回到问题2，在快速排序的情况下，可以从o（n^2）到θ（nlogn），这正是因为平均的随机情况实现了一个很好的分区，尽管运行时分析比这更复杂。

使用分治范式实现的算法的时间复杂度是否为o（nlogn）？
不，分而治之的一般公式是：

2是每个递归调用中的操作数，

是用子问题进行除法的递归调用，

是征服的运算的线性数
是什么让这样的算法首先在o（nlogn）中运行？
对数线性时间的一个很好的例子是合并排序算法：

是不是该方法中的递归部分有能力将一个类似o（n^2）的算法压缩为o（nlogn）？
利用主定理确定分治算法的运行时间
如果是这种形式

然后

例子
让

a = 2
b = 4
d = 1/2

因为2=4^1/2情况2适用

使用分治范式实现的算法的时间复杂度是否为o（nlogn）？
平均而言，快速排序和合并排序的时间复杂度为o（nlog（n）），但并不总是这样。大o备忘单
是不是该方法中的递归部分有能力将一个类似o（n^2）的算法压缩为o（nlogn）？
有比眼睛看到的更多的东西，它将取决于其他事情，比如操作的数量与每个递归调用的输入有关。
我强烈推荐这个视频，你可以看到为什么mergesort是o（nlog（n））。
是什么让这样的算法首先在o（nlogn）中运行。
同样，这只是一个算法消耗的时间与输入大小的关系的指标，所以说一个算法的时间复杂度为o（nlog（n））并没有给出算法是如何实现的任何信息，它只是说当输入开始大量增加时，所用的时间不会成正比地增加，而是需要越来越多的时间。

不，分而治之不能保证o（nlogn）性能。这完全取决于问题如何在每次递归中得到简化。
在合并排序算法中，原问题被分成两半。然后对结果执行o（n）运算。这就是o（n…）的来源。
两个子操作中的每一个子操作现在都有自己的 n 那是原作的一半大。每次你递归，你又把问题一分为二。这意味着递归的数量将是log2（n）。这就是o（…logn）的来源。