为什么我们通常在分而治之的算法中分为两部分？

Question

在合并排序中,我们在解决时分为两部分.为什么我们没有把它分成3个或更多部分？同样在我看到的许多分而治之的问题中,人们往往分为两部分.为什么不是3个或更多部分？它对解决方案/复杂性有什么影响？

Answer 1

你可以。但这并不重要。除法产生的复杂性为log（让我们非常笼统地讨论一下）。

准确地说，你得到了它log_2，但它被概括为log，因为常数因素在复杂性分析中并不重要（ Big-O-Notation，维基百科）。并且您始终可以仅使用常数因子log_a将 a 转换为 a ：log_b

log_a(x) = log_b(x) * (1 / log_b(a))

在更具体的层面上，当分成两半时，您会得到某个常数因子。2如果你现在分裂成4你会替换它，2但无论如何，这实际上只是一个恒定的因素变化。

实际上，在使用并行或分布式编程时，通常会分成两个以上的部分。

但除了分而治之之外，这只是一种使问题更容易被人类理解的技术。你把一个更难的问题转化为更简单的小问题。

大多数时候，分而治之的唯一好处是它更容易理解。