我知道像归并排序和快速排序这样的算法使用分而治之的范式，但我想知道为什么它可以降低时间复杂度......
为什么“分而治之”算法通常比非分而治之算法效果更好？
分而治之的算法工作得更快，因为它们最终完成的工作更少。
考虑二分搜索的经典分而治之算法：而不是看N寻找答案的项目，二分搜索最终仅检查Log2N其中。当然，当你做的工作越少，你就能更快地完成；这正是分而治之算法所发生的事情。
当然，结果在很大程度上取决于您的策略在划分工作方面的表现：如果每个步骤的划分或多或少公平（即将工作分成两半），您就会得到完美的结果Log2N速度。然而，如果划分不完美（例如，快速排序的最坏情况，当它花费O(n^2)对数组进行排序，因为它在每次迭代时仅消除一个元素），那么分治策略就没有帮助，因为您的算法不会减少工作量。
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
