Joh*_*ing 5 algorithm complexity-theory big-o divide-and-conquer
我知道像归并排序和快速排序这样的算法使用分而治之的范式，但我想知道为什么它可以降低时间复杂度......
为什么“分而治之”算法通常比非分而治之算法效果更好？
分而治之的算法工作得更快，因为它们最终完成的工作更少。
考虑二分搜索的经典分而治之算法：二分搜索最终只检查它们N，而不是查看项目来找到答案。Log2N当然，当你做的工作越少，你就能更快地完成；这正是分而治之算法所发生的事情。
当然，结果在很大程度上取决于您的策略在划分工作方面的表现：如果每个步骤的划分或多或少公平（即将工作分成两半），您就会获得完美的速度Log2N。但是，如果划分不完美（例如，快速排序的最坏情况，当它花费对O(n^2)数组进行排序时，因为它在每次迭代时仅消除单个元素），那么分治策略就没有帮助，因为您的算法没有帮助减少工作量。
分而治之是有效的，因为数学支持它！
考虑一些分而治之的算法：
1）二分查找：该算法每次将输入空间减少一半。直观上很明显，这比线性搜索更好，因为我们可以避免查看很多元素。
但好多少呢？我们得到递推式（注意：这是最坏情况分析的递推式）：
T(n) = T(n/2) + O(1)
数学意味着T(n) = Theta(log n). 因此，这比线性搜索要好得多。
2）归并排序：这里我们分成（几乎）相等的两半，对两半进行排序，然后将它们合并。为什么这比二次方程更好？这是复发：
T(n) = 2T(n/2) + O(n)
可以用数学方式证明（例如使用马斯特定理）T(n) = Theta(n log n)。因此 T(n) 渐近优于二次。
观察到朴素的快速排序最终给我们带来了最坏情况的重现：
T(n) = T(n-1) + O(n)
从数学上讲，它是二次的，并且在最坏的情况下，并不比冒泡排序更好（渐近地讲）。但是，我们可以证明，在平均情况下，快速排序的时间复杂度为 O(n log n)。
3 选择算法：这是一种分治算法，用于找到第 k^ 个最大元素。该算法是否比排序更好（甚至不是二次算法）根本不明显。
但从数学上来说，它的重现（又是最坏的情况）是
T(n) = T(n/5) + T(7n/10 + 6) + O(n)
可以从数学上证明这一点T(n) = O(n)，因此它比排序更好。
也许用一种常见的方式来看待它们：
您可以将算法视为树，其中每个子问题都成为当前的子树，并且可以用已完成的工作量来标记节点，然后可以将每个节点的总工作量相加。
对于二分查找来说，工作量是O(1)（只是比较），而其中一棵子树，工作量是0，所以总的工作量是O(log n)（本质上是一条路径，就像我们在二叉搜索树中执行）。
对于合并排序，对于具有 k 个子节点的节点，工作时间为 O(k)（合并步骤）。每个级别完成的工作是 O(n) （n、n/2 + n/2、n/4 + n/4 + n/4 + n/4 等），并且有 O(log n) 个级别，并且所以归并排序的复杂度是O(n log n)。
对于快速排序，在最坏的情况下，二叉树实际上是一个链表，因此完成的工作是 n+n-1 + ... + 1 = Omega(n^2)。
对于选择排序，我不知道如何将其可视化，但我相信将其视为具有 3 个子级（n/5、7n/10 和其余）的树可能仍然有帮助。