algorithm - 在最近对算法的时间复杂度中，O(n) 来自哪里？

Question

最近对问题的时间复杂度为 T(n) = 2T(n/2) + O(n)。我知道 2T(n/2) 来自这样一个事实，即该算法应用于 2 组原始大小的一半，但为什么其余的结果为 O(n)？谢谢。

Answer 1

查看http://en.wikipedia.org/wiki/Closest_pair_of_points_problem，它清楚地提到了 O(n) 的来源（平面案例）。

Answer 2

任何分而治之的算法都将包含一个递归的“除法”组件和一个将递归结果放在一起的“合并”组件。壁橱对中的线性 O(n) 分量来自将“除”步骤的结果合并为合并的答案。