algorithm - 分而治之：解决子问题明显快于未分问题是效率的一部分吗？

Question

我正在专门考虑快速排序：每个子问题的大小大约是主要问题的一半——是否子问题，包括划分主要问题然后重新组合已解决子问题的结果的开销，往往会在更少的时间内解决？主要问题的一半以上？

我知道并行解决子问题也是加快算法速度的一种方式，但大多数关于 QuickSort 的讨论都没有提到并行性。

标签： algorithmquicksortdivide-and-conquer

Answer 1

并不真地。如果您分析 QuickSort，您会发现它的效率实际上是枢轴质量的函数，并且总是存在运气不好或故意恶意将运行为 O(N^2) 的情况。

但总的来说，D&C 算法的复杂性是由于解决子问题和合并解决方案的成本的组合。回到您的问题，如果合并解决方案的成本是用朴素算法解决问题的顺序，那么您的 D&C 算法将永远不会胜过朴素算法。

您可以（几乎）始终使用主定理计算某些 D&C 算法的复杂性：

https://en.wikipedia.org/wiki/Master_theorem_(analysis_of_algorithms)

D&C 只是一种设计算法的元策略，这些算法可能会或可能不会更好地解决某个问题；没有“成功”的保证，即较低的复杂性，更不用说最低的复杂性了。

例如，QuickSort 在随机对数线性时间内运行，并且在标准硬件中对通用数组进行排序具有可接受的平均性能，但在特定情况下（例如整数数组）或硬件架构（例如大规模并行计算机）中被其他算法超越。