Divide-and-conquer Algorithm 分治算法

理解分治算法的思想；
掌握Counting inversions问题的分治算法；
能用Master Theorem求解递归关系式，典型考题：作业1的第1题；

Divide-and-conquer paradigm 分治算法范式

★Divide-and-conquer 分治算法思想

Divide up problem into several subproblems (of the same kind).
将问题分成几个同类子问题。

Solve (conquer) each subproblem recursively.
递归地解决每个子问题。

Combine solutions to subproblems into overall solution.
将子问题的解决方案合并为整体解决方案。

Merging sort 合并排序

Most common usage, e.g., merging sort.
分治算法最常见的用法，例如，合并排序。

• Divide problem of size n into two subproblems of size n / 2.
  将大小为n的问题分成大小为n/2的两个子问题。
• Solve (conquer) two subproblems recursively.
  递归地解决两个子问题。
• Combine two solutions into overall solution.
  将两种解决方案合并为整体解决方案。

Consequence.
时间复杂度结果

• Brute force 暴力: Θ(n²).
• Divide-and-conquer 分治: O(n log n).

求解递归式的时间复杂度1

证明合并排序问题分治算法的时间复杂度是O(n log n)

求解递归式的时间复杂度2

★问题 > Counting inversions 数逆序

Music site tries to match your song preferences with others.
音乐网站想要匹配你和他人的喜好

• You rank n songs.
  您对n首歌曲进行排名
• Music site consults database to find people with similar tastes.
  音乐网站查阅数据库，寻找有相似品味的人。

Similarity metric: number of inversions between two rankings.
相似性度量：两个排名之间的逆序次数

• My rank 我的排名: 1, 2, …, n.
• Your rank 你的排名: a₁, a₂, …, a_n.
• Songs i and j are inverted if i < j, but a_i > a_j.
  如果歌曲i和歌曲j在我的排名中i < j，但是在你的排名中a_i > a_j，那么歌曲i和歌曲j是逆序

Brute force: check all Θ(n²) pairs.
暴力算法：检查所有Θ(n²)对

Applications

• Voting theory. 投票理论
• Collaborative filtering. 协作过滤
• Measuring the “sortedness” of an array. 测量数组的“排序”
• Sensitivity analysis of Google’s ranking function. 谷歌排名功能的敏感性分析
• Rank aggregation for meta-searching on the Web. Web上元搜索的排名聚合
• Nonparametric statistics (e.g., Kendall’s tau distance). 非参数统计（例如Kendall’s tau距离）

Divide-and-conquer 分治算法

• Divide: separate list into two halves A and B.
  分：将列表平分成A和B两部分
• Conquer: recursively count inversions in each list.
  治：递归地求解每个列表的逆序
• Combine: count inversions (a, b) with a ∈ A and b ∈ B.
  合：计算跨越A和B的逆序
• Return sum of three counts.
  返回三部分之和

How to combine two subproblems? 如何合并两个子问题？

Q. How to count inversions (a, b) with a ∈ A and b ∈ B?
问：如何计算跨越A和B的逆序

A. Easy if A and B are sorted!
答：如果A和B都拍好了序就好办了

Warmup algorithm. 预热算法

• Sort A and B.
  对A和B排序
• For each element b ∈ B,
  对于B中的每个元素
  • binary search in A to find how many elements in A are greater than b.
    在A中二分搜索有多少个元素大于B

Count inversions (a, b) with a ∈ A and b ∈ B, assuming A and B are sorted.
假设A和B都拍好了序，计算跨越A和B的逆序：

• Scan A and B from left to right.
  从左到右扫描A和B
• Compare a_i and b_j.
  比较a_i和b_j
• If a_i < b_j, then a_i is not inverted with any element left in B.
  如果a_i < b_j，那么a_i不会与B中剩余的任何元素形成逆序
• If a_i > b_j, then b_j is inverted with every element left in A.
  如果a_i > b_j，那么b_j会与A中剩余的每个元素形成逆序
• Append smaller element to sorted list C.
  将二者中更小的元素加入排好序的列表C

Divide-and-conquer algorithm implementation 分治算法实现

Sort-and-count algorithm 排序和计数算法

Input. List L.
输入：列表L

Output. Number of inversions in L and L in sorted order.
输出：L的逆序数和排好序的列表L

时间复杂度分析

Proposition. The sort-and-count algorithm counts the number of inversions in a permutation of size n in O(n log n) time.
命题：对于大小为n的排列，排序和计数算法在O(n log n)时间内计算出逆序的个数

Pf. The worst-case running time T(n) satisfies the recurrence:
证明：最坏情况下的运行时间T(n)满足以下条件：

问题 > Maximum Subarray Problem 最大连续子数组问题

Goal. Given an array x of n integer (positive or negative), find a contiguous subarray whose sum is maximum.
目标：给定n个整数（正或负）的数组x，找到一个和最大的连续子数组。

分治解法：……

★Master theorem 主定理

Master theorem 主定理

完整版主定理

设$a\ge 1$和$b>1$为常数，设$f(n)$为一函数，$T(n)$由以下递归式给出：

$$T(n)=aT(n/b)+f(n)$$

对于非负整数定义，其中$n/b$指$\lfloor n/b\rfloor$或$⌈n/b⌉ $。则$T(n)$可能有如下的渐近界：

• 1）若对于某常数$\epsilon >0$，有$f(n)=O(n^{{\log }_{b}a-\epsilon })$，则$T(n)=\Theta (n^{{\log }_{b}a})$
• 2）若$f(n)=O(n^{{\log }_{b}a-\epsilon })$，则$T(n)=\Theta (n^{{\log }_{b}a}\log n)$
• 3）若对于某常数$\epsilon >0$，有$f(n)=\Omega (n^{{\log }_{b}a+\epsilon })$，且存在常数$c<1$使得对所有足够大的$n$，有$af(n/b)\le cf(n)$，则$T(n)=\Theta (f(n))$

理解主定理

Gaps in master theorem 主定理的空白

• Number of subproblems is not a constant.
  子问题个数不是常数
• Number of subproblems is less than 1.
  子问题个数小于1
• Work to divide and combine subproblems is not Θ(n^c).
  分开合并子问题的操作不是Θ(n^c)复杂度的

不能使用主定理的情况

问题 > Integer multiplication 整数乘法

Integer addition and subtraction 整数加减法

加法a+b的输入规模为a和b的位数n，而不是a或b

Integer multiplication 整数乘法

Divide-and-conquer multiplication 分治乘法

Karatsuba trick (Karatsuba技巧)

Karatsuba multiplication (Karatsuba乘法算法)

Karatsuba analysis 分析Karatsuba算法

问题 > Matrix multiplication 矩阵乘法

Dot product 点乘

Matrix multiplication 矩阵乘法

Block matrix multiplication 分块矩阵乘法

Warmup 准备

分成四等分

Strassen’s trick (Strassen的技巧)

Strassen’s algorithm (Strassen的算法)

Analysis of Strassen’s algorithm 分析Strassen的算法

Theorem. Strassen’s algorithm requires O(n2.81) arithmetic operations to multiply two n-by-n matrices.

问题 > Closest pair of points 最近点对

Closest pair of points 最近点对问题

Closest pair problem. Given n points in the plane, find a pair of points with the smallest Euclidean distance between them.

First attempt 初次尝试

Sorting solution. 排序

• Sort by x-coordinate and consider nearby points.
• Sort by y-coordinate and consider nearby points.

无法解决这种问题：

Second attempt 二次尝试

Divide. Subdivide region into 4 quadrants.
分成4部分

Obstacle. Impossible to ensure n / 4 points in each piece.
无法保证平分

Divide-and-conquer algorithm 分治算法思想

分成两部分

How to find closest pair with one point in each side? 如何找到分布两边的最近点对

Find closest pair with one point in each side, assuming that distance < δ.

• Observation: suffices to consider only those points within δ of line L.
• Sort points in 2 δ-strip by their y-coordinate.
• Check distances of only those points within 7 positions in sorted list!

Divide-and-conquer algorithm 分治算法

时间复杂度：

Refined version of closest-pair algorithm 最近点对算法的改良版

问题 > 棋盘覆盖

问题描述

分治算法