我正在专门考虑QuickSort：每个子问题的大小大约是主要问题的一半-是子问题，包括划分主要问题然后重新组合已解决子问题的结果的开销在不到主要问题一半的时间内解决了？
我知道解决子问题是并行的，这也是加快算法速度的一种方式，但是QuickSort的大多数讨论都没有提到并行性。
guoshuzhengsz 回答：分而治之：解决子问题比未解决的问题快得多的效率的一部分吗？
不是。如果您分析QuickSort，您会发现它的效率实际上是枢轴质量的函数，并且在某些情况下，无论运气不好还是故意的恶意行为，都会以O（N ^ 2）的形式运行。
但是，总的来说，D＆C算法的复杂性是由于解决子问题和合并解决方案的成本共同造成的。回到您的问题，如果合并解决方案的成本大约是用朴素算法解决问题的成本，那么您的D＆C算法将永远不会超过朴素算法。
您可以（几乎）始终使用Master定理计算出某些D＆C算法的复杂性：
https://en.wikipedia.org/wiki/Master_theorem_(analysis_of_algorithms)
D＆C只是设计算法的一种元策略，该算法可能会或可能不会更好地解决某个问题。不能保证“成功”，即较低的复杂性，最低的复杂性要少得多。
例如，QuickSort在随机对数线性时间内运行，在标准硬件中对通用数组进行排序时具有可接受的平均性能，但在特定情况下（例如整数数组）或硬件体系结构（例如大规模并行）则被其他算法超越计算机）。
,Quicksort并不是一个很好的分而治之的例子，因为排序数据的主要功能（枢轴）是在划分之前执行的。一旦达到分区大小== 1的基本情况，那么就已对调用链的该部分中的所有元素进行了排序。
典型的自上而下的合并排序是一个更好的示例，因为它除了通过递归调用将索引（或指针）推入堆栈外没有其他操作，并且直到出现两个子数组大小为1的实例时才进行合并。然后完成合并，并遵循向上和向下的调用链。但是，自下而上的合并排序将跳过所有递归索引的生成，并开始将n个元素的数组视为大小为1的n个子数组，然后立即开始合并。自上而下主要用于教育目的，而大多数图书馆使用自下而上合并排序和插入排序的混合方式。