算法：分而治之与时间复杂度 O(nlogn) 有何关系？
algorithms: how do divide-and-conquer and time complexity O(nlogn) relate?
在我的算法和数据结构 class 中引入了第一个 divide-and-conquer algorithm，即 merge sort。
在为作业实施算法时，我想到了几个问题。
使用分而治之范式实现的任何算法的时间复杂度是否为 O(nlogn)？
是不是方法中的递归部分有能力将O(n^2)中的运行s压缩到O(nlogn)的算法？
是什么让这样的算法 运行 成为 O(nlogn) 的首要原因？
对于（3）我假设这与递归树和可能的递归数有关。有人可能会用一个简单的分而治之算法来展示 O(nlogn) 中的 运行s，复杂度实际上是如何计算的？
干杯，
安德鲁
不，分而治之并不能保证 O(nlogn) 的性能。这完全取决于问题在每次递归时如何得到简化。
在归并排序算法中，原来的问题被分成了两半。然后对结果执行 O(n) 操作。这就是 O(n...) 的来源。
这两个子操作中的每一个现在都有自己的 n，大小是原来的一半。每次你递归，你又把问题分成两半。这意味着递归次数将为 log2(n)。这就是 O(...logn) 的来源。
Does any algorithm that is implemented with the use of the divide and conquer paradigm has time complexity of O(nlogn)?
平均而言，Quicksort 和 Mergesort 的时间复杂度为 O(n log(n))，但不一定总是这样。
Big O Cheat Sheet
Is it that the recursion part in the approach has the power to condense an algorithm that runs in like O(n^2) to O(nlogn)?
远不止于此，这还取决于其他因素，例如与每次递归调用的输入相关的操作数。
我强烈推荐这个 video 在这里你可以看到为什么 MergeSort 是 O(n log(n))。
What makes such an algorithm run in O(nlogn) in the first place.
同样，这只是一个算法相对于输入大小消耗多少时间的指标，所以说一个算法的时间复杂度为 O (n log (n)) 并不能说明问题关于算法如何实现的任何信息，它只是说当输入开始增加很多时，使用的时间不会成正比增加，而是需要更多的时间和更多。
我认为您问题的所有答案都可能来自 Master Theorem It kind of tell you what would be your complexity for almost any divide and conquer solution you have, and yes, it has to do everything with recursion trees, by playing with the parameters you will find that some divide and conquer solutions won't have O(nlogn) complexity, in fact there are divide and conquer algorithms that have O(n) complexity。
就问题2而言，并不总是可能的，事实上，有些问题被认为不可能比O(n^2)更快地解决，这取决于问题的性质。
运行 复杂度为 O(nlogn) 并且我认为具有非常简单、清晰且具有教育意义的 运行 时间分析的算法示例是 MergeSort。从下图可以掌握：
所以每个递归步骤输入被分成两部分，然后征服部分花费 O(n)，所以树的每一层花费 O(n)，棘手的部分可能是如何可能递归层数（树高）为 logn。这或多或少是简单的。因此，在每一步中，我们将输入分成 n/2 个元素的 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) 复杂度，您就可以确信您的算法具有 O(nlogn) 复杂度，并且您将问题分成大小为 n/b 的 b 个问题，或者更一般地说，如果这些部分是 n 的线性分数，加起来等于 n。在不同的情况下，很可能你会有不同的运行时间。
回到问题 2，在 QuickSort 的情况下，一个人可能从 O(n^2) 到 \Theta(nlogn) 正是因为平均随机情况实现了一个很好的划分，尽管 运行time分析比这更复杂。
使用分而治之范式实现的算法是否具有 O(nlogn) 的时间复杂度？
不是，分而治之的通用公式是：
2是每次递归调用内部的操作数， is the recursive call for dividing with sub-problems, 是征服的线性操作数
是什么让这样的算法 运行 首先在 O(nlogn) 中？
对数线性时间的一个很好的例子是合并排序算法m:
是不是该方法中的递归部分有能力压缩一个算法 运行s 在 O(n^2) 到 O(nlogn) 之间？
大定理用于确定分治算法的运行宁时间
如果循环就是这种形式
然后
例子
让
a = 2
b = 4
d = 1/2
因为 2 = 4 ^ 1/2 情况 2 适用
在我的算法和数据结构 class 中引入了第一个 divide-and-conquer algorithm，即 merge sort。
在为作业实施算法时，我想到了几个问题。
使用分而治之范式实现的任何算法的时间复杂度是否为 O(nlogn)？
是不是方法中的递归部分有能力将O(n^2)中的运行s压缩到O(nlogn)的算法？
是什么让这样的算法 运行 成为 O(nlogn) 的首要原因？
对于（3）我假设这与递归树和可能的递归数有关。有人可能会用一个简单的分而治之算法来展示 O(nlogn) 中的 运行s，复杂度实际上是如何计算的？
干杯， 安德鲁
不，分而治之并不能保证 O(nlogn) 的性能。这完全取决于问题在每次递归时如何得到简化。
在归并排序算法中，原来的问题被分成了两半。然后对结果执行 O(n) 操作。这就是 O(n...) 的来源。
这两个子操作中的每一个现在都有自己的 n，大小是原来的一半。每次你递归，你又把问题分成两半。这意味着递归次数将为 log2(n)。这就是 O(...logn) 的来源。
Does any algorithm that is implemented with the use of the divide and conquer paradigm has time complexity of O(nlogn)?
平均而言，Quicksort 和 Mergesort 的时间复杂度为 O(n log(n))，但不一定总是这样。 Big O Cheat Sheet
Is it that the recursion part in the approach has the power to condense an algorithm that runs in like O(n^2) to O(nlogn)?
远不止于此，这还取决于其他因素，例如与每次递归调用的输入相关的操作数。
我强烈推荐这个 video 在这里你可以看到为什么 MergeSort 是 O(n log(n))。
What makes such an algorithm run in O(nlogn) in the first place.
同样，这只是一个算法相对于输入大小消耗多少时间的指标，所以说一个算法的时间复杂度为 O (n log (n)) 并不能说明问题关于算法如何实现的任何信息，它只是说当输入开始增加很多时，使用的时间不会成正比增加，而是需要更多的时间和更多。
我认为您问题的所有答案都可能来自 Master Theorem It kind of tell you what would be your complexity for almost any divide and conquer solution you have, and yes, it has to do everything with recursion trees, by playing with the parameters you will find that some divide and conquer solutions won't have O(nlogn) complexity, in fact there are divide and conquer algorithms that have O(n) complexity。
就问题2而言，并不总是可能的，事实上，有些问题被认为不可能比O(n^2)更快地解决，这取决于问题的性质。
运行 复杂度为 O(nlogn) 并且我认为具有非常简单、清晰且具有教育意义的 运行 时间分析的算法示例是 MergeSort。从下图可以掌握：
所以每个递归步骤输入被分成两部分，然后征服部分花费 O(n)，所以树的每一层花费 O(n)，棘手的部分可能是如何可能递归层数（树高）为 logn。这或多或少是简单的。因此，在每一步中，我们将输入分成 n/2 个元素的 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) 复杂度，您就可以确信您的算法具有 O(nlogn) 复杂度，并且您将问题分成大小为 n/b 的 b 个问题，或者更一般地说，如果这些部分是 n 的线性分数，加起来等于 n。在不同的情况下，很可能你会有不同的运行时间。
回到问题 2，在 QuickSort 的情况下，一个人可能从 O(n^2) 到 \Theta(nlogn) 正是因为平均随机情况实现了一个很好的划分，尽管 运行time分析比这更复杂。
使用分而治之范式实现的算法是否具有 O(nlogn) 的时间复杂度？
不是，分而治之的通用公式是：
2是每次递归调用内部的操作数，
是什么让这样的算法 运行 首先在 O(nlogn) 中？
对数线性时间的一个很好的例子是合并排序算法m:
是不是该方法中的递归部分有能力压缩一个算法 运行s 在 O(n^2) 到 O(nlogn) 之间？
大定理用于确定分治算法的运行宁时间
如果循环就是这种形式
然后
例子
让
a = 2
b = 4
d = 1/2
因为 2 = 4 ^ 1/2 情况 2 适用