# 算法设计与分析笔记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)$$