算法设计与分析笔记0x05 —— 分治法(1)

Divide and Conquer

  • Break up problem into several parts
  • Solve each part recursively
  • Combine solution to sub-problems into over solution

Let’s consider about mergesort.
$$T(n) = T(\lceil n/2 \rceil) + T(\lfloor n/2 \rfloor) + n$$
We solve it and get T(n)=O(nlogn), which could be proved by several methods mentioned in Basic Algorithm Note.

Counting Inversion

Application

  • Collaborative Filtering 协同过滤

Similarity metric: number of inversions between two rankings

  • My rank: 1, 2, …, n.
  • Your rank: a1, a2, …, an.
  • Songs i and j inverted if i < j, but ai > aj.
    • 1,2,3,4,5
    • 1,3,4,2,5
    • in the above ranks, inversions are 3-2, 4-2

  • 每个sublist求inversions并进行mergesort
  • 当inversion出现时,inversion数增加前一个sublist还未merge的元素个数

$$T(n)\leq T(\lceil n/2 \rceil) + T(\lfloor n/2 \rfloor) + O(n) \Rightarrow T(n) = O(nlogn)$$

Closet Pair of Points

  • Goal: 屏幕上有两个点,找到最近的两个点并输出Euclidean distance
  • Assume no points have the same x coordinates.
  • Divide 找出两个parts最近的两个点,得到两个最短距离dis1, dis2
  • Combine 找出两个parts分界线两边的点最短距离,再比较三个最短距离

Question: How to find closet pair with one point in each side?

  • Assume that distance < $\delta$ = min(dis1, dis2)
  • We only need to consider points within $\delta$ of boundary L.
    • Sort them by y coordinate
  • Def. Let $s_i$ be the point in the 2$\delta$-strip, with the $i^{th}$ smallest y-coordinate.
  • Claim. If $|i-j|\geq 12$, then the distance between $s_i$ and $s_j$ is at least $\delta$.

  • Fact We can replace 12 with 8.

Algorithm


$$T(n)\leq 2T(n/2)+O(nlogn)\Rightarrow T(n)=O(nlog^2 n)$$

  • Don’t sort points from scratch each time.
  • Sort all the points twice before recursive call, once by x coordinate and once by y coordinate
  • Reuse the sorted sequences when needed (linear time)

$$T(n)\leq 2T(n/2)+O(n)\Rightarrow T(n)=O(nlogn)$$

Leave a Reply

Your email address will not be published.