跳转至

7 Divide & Conquer

文本统计：约 520 个字

  • Divide the problem into a number of sub-problems

  • Conquer the sub-problems by solving them recursively

  • Combine the solutions to the sub-problems into the solution for the original problem
\[ \text{General recurrence}: T(N) = aT(N/b) + f(N) \]

7.1 Closest Points Problem

Given \(N\) points in a plane. Find the closest pair of points. (If two points have the same position, then that pair is the closest with distance 0.)

  • Sort according to \(x\)-coordinates and divide;

  • Conquer by forming a solution from left, right, and cross.

现在需要考虑的就是合并的时间复杂度

我们取 \(\delta\) 为两部分最小的距离，并以中轴线左右 \(\delta\) 为考虑范围（在这个范围之外的不用考虑），然后最差情况在这个区域内的点共有 \(N\) 个，对于每个点来说考虑对面的点，如果y方向差距超过 \(\delta\) ，那么不需考虑，从而又由于假设对面的点之间的距离不能超过 \(\delta\) ，那么需考虑的点则是常数个，从而合并的复杂度为 \(O(N)\)

\[ T(N)=2T(N/2)+O(N)\Rightarrow T(N)=O(N\log N) \]

7.2 解决递推式

7.2.1 Substitution

代换法(substitution method)的思路非常直白，首先我们通过某些手段（比如大眼观察法👀）来得到一个预设的结果，接下来通过代入、归纳的方法来证明这个结果。

7.2.2 Recursion-tree method

递归树法(recursion-tree method)的思路是，我们通过画出递归树来分析算法的时间复杂度，实际上和直接数学推理的区别不是很大，主要就是通过观察递归过程中数据增长的模式来进行分析。

7.2.3 Master method

【Master Theorem】Let \(a\ge1\) and \(b > 1\) be constants, let \(f(N)\) be a function, and let \(T(N)\) be defined on the nonnegative integers by the recurrence \(T(N) = aT(N/b) + f(N)\). Then:

  1. If \(f(N)=O(N^{\log _ba-\epsilon})\) for some constant \(\epsilon>0\), then \(T(N)=\Theta(N^{\log _b a})\)
  2. If \(f(N)=\Theta(N^{\log _b a})\), then \(T(N)=\Theta(N^{\log _b a}\log N)\)
  3. If \(f(N)=\Omega(N^{\log _b a+\epsilon})\) for some constant \(\epsilon>0\), and if \(af(N/b)<cf(N)\) for some constant \(c < 1\) and all sufficiently large \(N\), then \(T(N)=\Theta(f(N))\)

Case3

Case 3的条件有点重复说明了，后面的条件可以证明前者，但是前者并不能证明后者

【Master Theorem】The recurrence \(T(N) = aT(N/b) + f(N)\) can be solved as follows:

  1. If \(af(N/b) = \kappa f(N)\) for some constant \(\kappa< 1\), then \(T(N)=\Theta(f(N))\)
  2. If \(af(N/b) = K f(N)\) for some constant \(K\) > 1, then \(T(N)=\Theta(N^{\log _b a})\)
  3. If \(af(N/b) = f(N)\), then \(T(N)=\Theta(f(N)\log _bN)\)

主方法的证明可以使用递归树来证明

评论区

对你有帮助的话请给我个赞和 star => GitHub stars
欢迎跟我探讨！！！