### 算法设计策略I:分治法

```Divide and Conquer
Algorithms

• Binary Search and Related Problems
• Recurrence Relation and Master Theory
• 排序相关问题
– 归并排序、逆序对、快速排序、求第k小元素
• 最大连续序列问题
• 最大值最小化
• 最近点对问题
• Karasuba快速乘法
• Strassen矩阵乘法
• 求解线性递推方程
• 非线性方程求根
• 快速幂
• The divide-and-conquer strategy solves a
problem by:
– 1. Breaking it into subproblems that are
themselves smaller instances of the same
type of problem.
– 2. Recursively solving these subproblems
– 3. Appropriately combining their answers
• The real work is done in 3 different places:
– 1. in the partitioning of problems into
subproblems;
– 2. at the very tail end of the recursion, when
the subproblems are so small that they are
solved outright;
– 3. in the gluing together of partial answers.

• Divide. 把问题的实例划分成子问题
• Conquer. 递归解决子问题
• Combine. 合并子问题的解得到原问题的解
Binary Search

• 在一个从小到大排序好的表里搜索关键码x
• 顺序查找：最坏情况下要比较所有元素
• 二分查找：只需要比较log2n个元素

• 每次把范围缩小一半
• 除A[mid]外有两部分
– A[low..mid-1]
– A[mid+1, high]
• 每次元素减半
• 最多log2n次迭代

• Divide: 检查中间元素
• Conquer: 递归在其中一个区间内搜索
• Combine: 平凡的

• 线性查找: O(n)
• O(logn)比O(n)好多少?
• 注意: n很小时

// 查找范围[low, high]
int bsearch(int s[],int low, int high, int key)
{
if ( low > high ) return 1;
int middle = (low + high) / 2;
if (s[middle] == key) return middle;
else if (s[middle] > key)
return bsearch(s,low,middle-1,key);
else
return bsearch(s,middle+1,high,key);
}

//查找范围[low, high]
int bsearch(int* s,int low, int high, int key)
{
int middle;
while ( low <= high )
{
middle = low + (high-low)/2;
if ( s[middle) == key ) return middle;
else if (s[middle]>key) high = middle-1;
else low = middle + 1;
}
return -1;
}

• 比较A[mid]和x以后一定不要让mid仍然在有

• 如果把算法扩展到在实数区间里寻找给定

low和high足够接近(例如|high-low| < 108)
Counting Occurrences
• Problem: count the number of times a given key
k occurs in a given sorted array.
• For example, in array 1 2 2 2 3 3, key 2 occurs 3
times.
• O(lg n + s) Algorithm, where s is the number of
occurrences of the key.
• If the entire array consists of identical keys, this
can be as bad as linear.
Counting Occurrences
• Problem: count the number of times a given key
k occurs in a given sorted array.
• Faster Algorithm: modifying binary search to
search for the boundary of the block containing
Counting Occurrences
//二分查找下界，查找范围[x,y)
int lower_bound(int* s,int x,int y,int v)
{
while ( x < y )
{
int m= x + (y-x)/2;
if ( s[m] >= v ) y = m;
else x = m + 1;
}
return x;
}
Counting Occurrences
// 二分查找上界，查找范围[x,y)
int upper_bound(int* s, int x, int y, int v)
{
int m;
while (x < y)
{
m = x + (y-x) / 2;
if(s[m] <= v) x = m+1;
else y = m;
}
return x;
}
Counting Occurrences

• 题目：给出n个整数xi和m个询问，对于每

• 分析

#include <cstdio>
#include <algorithm>
Using namespace std;
Int v[10000];
Int main()
{
int n, m, a, b;scanf(“%d%d”, &n, &m);
for(int i=0; i<n; i++) scanf(“%d”, &v[i]);
sort(v, v+n);
for(int i=0; i<m; i++) {
scanf(“%d%d”, &a, &b);
printf(“%d\n”, upper_bound(v,v+n,b) – lower_bound(v,v+n,a));
}
}
Recurrence relations and
master theorem
generic pattern:
they tackle a problem of size n by recursively
solving, say, a subproblem of size n/b and then
combining these answers in O(nd) time, for
some a, b, d > 0 (in the binary search algorithm,
a = 1, b = 2, and d = 0).
Their running time can therefore be captured by
the equation T(n) = aT(n/b) + O(nd).
Each problem of size n is divide into a subproblems of size n/b
Master Theorem
• If T(n) = aT(n/b) + O(nd) for some
constants a>0, b>1, and d>=0, then
1. T(n) = O(nd)
if d>logba
2. T(n) = O(ndlogbn) if d=logba
3. T(n) = O(nlogba) if d<logba
Master Theorem
• Proof.
If q is positive real number, then g(n) =
1+q+q2+…+qn is
(a) O(1) if q<1
(b) O(n) if q=1
(c) O(qn) if q>1
The moral: in big-O terms, the sum of a geometric
series is simply the first term if the series is strictly
decreasing, the last term if the series is strictly
increasing, or the number of terms if the series is
unchanging.
Master Theorem
The total work done at level k is
ak × O(n/bk)d = O(nd) × (a/bd)k
As k goes from 0 to logbn (the level), these numbers form a
geometric series with ratio a/bd.
1. The ratio is less than 1. Then the series is decreasing,
and its sum is just given by its first term O(nd).
2. The ration is exactly 1. In this case all O(logn) terms of
the series are equal to O(nd). O(logbn) × O(nd) =
O(ndlogbn)
3. ratio is greater than 1. The series is increasing and its
sum is given by its last term, O(nlogba) :
O(nd) × (a/bd) logbn = O(nd × a logbn / (b logbn)d)
= a logbn = n logba

• 给n个数, 从小到大排序
Mergesort
• Merge sort is an O(n log n) comparison-based
sorting algorithm.
• In most implementations it is stable, meaning
that it preserves the input order of equal
elements in the sorted output.
• It is an example of the divide and conquer
• It was invented by John von Neumann in 1945.
Mergesort

Mergesort

• Divide: 平凡的
• Conquer: 递归排序两个区间
• Combine: 合并两个有序表
Mergesort Routine
void merge_sort(int *A, int x, int y, int* T)
{
if (y-x > 1)
{
int m = x + (y-x) / 2; // divide
int p = x, q = m, i = x;
merge_sort(A, x, m, T); // 递归求解
merge_sort(A, m, y, T); // 递归求解
while (p < m || q < y)
{
if(q >= y || (p < m && A[p] <= A[q]))
T[i++] = A[p++];
else T[i++] = A[q++];
}
for(i=x; i<y; i++) A[i] = T[i];
}
}
Iterative Mergesort
function iterative-mergesort(a[1…n])
Input: elements a[1],a[2],…,a[n] to be sorted
Q = [ ] (empty queue)
for i=1 to n:
Q.enqueue([ a[i] ])
while |Q| > 1:
Q.enqueue(merge(Q.dequeue(), Q.dequeue()))
return Q.dequeue()
Mergesort
• 算法分析
– 时间: T(n) = 2T(n/2) + n  T(n) = O(nlogn)
– 空间: S(n) = 2S(n/2) + n? 空间可重用!
• 最好、最坏、平均是一致的

• 逆序对：对于一个包含N个非负整数的数组
A[1..n]，如果有i < j，且A[ i ]>A[ j ]，则称
( i , j )为数组A中的一个逆序对。
• 例如，数组（3，1，4，5，2）的逆序对有
(3,1),(3,2),(4,2),(5,2)，共4个。
• 枚举：O(n2). n <= 5000适用

• Divide: 把序列等分成两半
• Conquer: 统计i和j都在左边或者均在右边的逆序对

• Combine: 统计i在左边，但j在右边的逆序对个数。
• Q: 如何求出i在左边，而j在右边的逆序对个数呢？
• A: 对于右边的每个j，统计左边比它大的元素个数
f(j)，则所有f(j)之和就是答案。

• 利用归并排序的框架
i,j <= mid或i,j > mid，递归处理
i <= mid < j，合并的时候顺便求！
• 1, 2, 4, 7, 9
• 3, 5, 6, 10, 11
• 取后一半元素时，前一半还剩多少个就是…
• 时间复杂度：O(nlogn)

int inverse_num = 0;
void inverse_number(int *A, int x, int y, int* T)
{
if (y-x > 1)
{
int m = x + (y-x) / 2; // divide
int p = x, q = m, i = x;
merge_sort(A, x, m, T); // 递归求解
merge_sort(A, m, y, T); // 递归求解
while (p < m || q < y)
{
if(q >= y || (p < m && A[p] <= A[q]))
T[i++] = A[p++];
else {T[i++] = A[q++]; reverse_num += m-p;}
}
for(i=x; i<y; i++) A[i] = T[i];
}
}
k-way Merge
• Suppose you have k sorted arrays, each with n
elements, and you want to combine them into a
single sorted array of kn elements.
– (a) Here’s one strategy: merge the first two arrays,
then merge in the third, then merge in the fourth, and
so on. What is the time complexity of this algorithm, in
terms of k and n?
– (b) Give a more efficient solution to this problem,
using divide-and-conquer.

•
•
•
•

1962年由C.A.R.Hoare提出

• Divide. 把数组以轴心x为分界线划分成两部分，左

• Conquer. 递归把两部分排序
• Combine. 平凡的
• 关键：线性时间的划分过程

• 两个指针left和right. left左边的都比x小, right右

• left和right交替移动, 一旦发现不满足要求的元素

• 好处：当相同元素比较多时较快

• 虽然效率还可以优化, 但非常容易理解

• 不管使用哪种划分方法，快速排序的主过程如下：

• 如果每次划分出来的序列都是一边n-1个元素一

• 解决方案：随机划分

• 最好情况：均分成两半，则是O(nlogn)
• 最坏情况：分成长度为1和n-1，则是O(n2)
• 这是不是说明快速排序比归并排序差
– 显然不是，否则就不会叫“快速排序”了嘛…
– 加入随机数, 几乎可以保证是O(nlogn), 系数比归

– 随机数让坏情况从数据转移到了随机运气

• 一些小细节
– n <= 10时用插入排序加速
– pivot x如何选？中间？随机（随机数产生开

– 警告！快速排序不稳定！原因？如何修改？
– 最坏情况:数据随机数
Picking the Pivot for Quicksort
• A wrong way
– Use the first element as pivot. What happens
if the input is presorted or in reverse order?
• A safe maneuver
– Chose the pivot randomly. Downside: random
number generation is somewhat expensive.
• Median-of-Three Partitioning
– The best choice of pivot would be the median
of the array, but this hard to calculate.
– Use the median of the left, right, and center
(in position (left+right)/2) elements as pivot.
Patitioning Strategy
• 1. When using median-of-three partitioning, just
sort a[left], a[right] and a[center] in place, let the
smallest of the three in a[left], the largest in a[right].
• 2. swap pivot (a[center]) with the a[right-1] and
initialize i and j to left+1 and right-2.
• While i is to the left of j, we move i right, skipping
over elements that are smaller than the pivot and
we move j left, skipping over elements that are
larger than the pivot. If i is to the left of j, swap the
elements points to by i and j and repeat the
process until i and j cross.
Small Arrays
• For very small arrays (N<=20), quicksort does not
perform as well as insertion sort. Because
quicksort is recursive, there cases will occur
frequently.
• A common solution is no to use quicksort
recursively for small arrays, but instead use a
sorting algorithm that is efficient for small arrays,
such as insertion sort.
Quicksort Routine
/* Return median of left, center, and right.
* Order these and hide the pivot.*/
template <typename Comparable>
const Comparable & median3( vector<Comparable> & a,
int left, int right )
{
int center = ( left + right ) / 2;
if( a[ center ] < a[ left ] )
swap( a[ left ], a[ center ] );
if( a[ right ] < a[ left ] )
swap( a[ left ], a[ right ] );
if( a[ right ] < a[ center ] )
swap( a[ center ], a[ right ] );
// Place pivot at position right - 1
swap( a[ center ], a[ right - 1 ] );
return a[ right - 1 ];
}
Quicksort Routine
template <typename Comparable>
void quicksort( vector<Comparable> & a, int left, int right )
{
if( left + 10 <= right )
{
Comparable pivot = median3( a, left, right );
int i = left, j = right - 1;
for( ; ; )
{
while( a[ ++i ] < pivot ) { }
while( pivot < a[ --j ] ) { }
if( i < j )
swap( a[ i ], a[ j ] );
else
break;
}
swap( a[ i ], a[ right - 1 ] ); // Restore pivot
quicksort( a, left, i - 1 );
// Sort small elements
quicksort( a, i + 1, right );
// Sort large elements
}
else // Do an insertion sort on the subarray
insertionSort( a, left, right );
}
Quicksort Routine
/**
* Quicksort algorithm (driver).
*/
template <typename Comparable>
void quicksort( vector<Comparable> & a )
{
quicksort( a, 0, a.size( ) - 1 );
}

• 令T(n)为随机快速排序时间复杂度. 注意T(n)是一

• 对于k=0,1,…,n-1,定义指示随机变量(indicator
random variable)
• 每种划分都是等概率的，因此Xk的期望全是1/n

• 根据数学期望的定义，我们有
• 两边取期望，得

• 第一步：期望的线性性质
• 第二步：Xk是独立随机变量
• 第三步：期望的线性性质，Xk的期望为1/n

• 注意：前两项实际是相同的
• 合并前两项后化简第三项，得
• 下面我们证明：存在常数a>0使得E[T(n)]<=anlgn
• 首先证明下面不等式：

• 用第二数学归纳法，则有
• 取a足够大，让an/4比Θ(n)大即可

• 算法一: 先排序O(nlogn)
• 算法二: 借用快速排序的框架
– 只需要根据k的大小只处理一边
– 平均情况：O(n)

• 和快速排序类似, 需要求如下的期望
• 注意到最后一步合并时n/2开始的元素才出现，其

• 仍然使用数学归纳法，需要用到事实

• 和快速排序类似
• 让c大到cn/4比Θ(n)大即可
Quickselect Routine
int median3( vector<Comparable> & a, int left, int
right )
{
int center = ( left + right ) / 2;
if( a[ center ] < a[ left ] )
swap( a[ left ], a[ center ] );
if( a[ right ] < a[ left ] )
swap( a[ left ], a[ right ] );
if( a[ right ] < a[ center ] )
swap( a[ center ], a[ right ] );
return center;
}
Quickselect Routine
template <typename Comparable>
int partion(vector<Comparable> & a, int left, int
right, int pivotIndex)
{
Comparable pivotValue = a[pivotIndex];
swap(a[pivotIndex, a[right]);
int storeIndex = left;
for (int i=left; i<=right; ++i)
{
if (a[i]<pivotValue)
{ swap(a[storeIndex], a[i]); storeIndex++; }
}
swap(a[right],a[storeIndex]);
return storeIndex;
}
Quickselect Routine
template <typename Comparable>
int quickSelect( vector<Comparable> & a, int left, int
right, int k )
{
if (left == right) return a[left];
int pivotIndex = median3( a, left, right );
int pivotNewIndex = partion(a,left,right,pivotIndex);
int pivotDist = pivotNewIndex-left+1;
if ( k == pivotDist ) return a[pivotNewIndex];
else if( k < pivotDist )
return quickSelect(a, left, pivotNewIndex-1, k);
else
return quickSelect( a, pivotNewIndex + 1, right, kpivotDist );
}

•
•
•
•

1973年, 由Blum, Floyd, Pratt, Rivest和
Tarjan提出
• 思想：选取好的pivot，然后执行划分并递

• 一共n/5个组，n/5个“组中位数”(黄色)
• 所有“组中位数”的中位数为x(红色)
• 至少有[[n/5]/2]=[n/10]个“组中位数”比x小, 而每

• 类似地，至少有3*[n/10]个元素比x大
• 当n>=50时，3*[n/10]>=n/4, 即最坏的划分为1/43/4划分。因此步骤4需要的时间为O(3n/4)

• 使用数学归纳法即可，和前面类似

• 有m个有序表, 每个表里有n个元素.
• 所有元素都是小于等于W的正整数.
• 设计算法, 回答这m*n个元素中第k小元素的

• 二分元素大小x
– 计算每个有序表里比x小的元素个数之和k’, 每

– 如果k’=k, 输出x
– 如果k’<k, 把x变大；如果k’>k, 把x变小
• 总时间复杂度O(mlogn*logW)

• 把一个包含n个正整数的序列划分成m个连续的子

• 例如序列1 2 3 2 5 4划分成3个序列的最优方案为
1 2 3 | 2 5 | 4，其中S(1)、S(2)、S(3)分别为6、7、
4，最大值为7；如果划分成1 2 | 3 2 | 5 4，则最

• n<=10^6，所有数之和不超过10^9.

• 考虑新问题：能否将输入序列划分成m个连续的

• 二分求最小值x：随便猜一个x0，如果P(x0)为假，

• 设所有数之和为M，则二分次数为O(logM)，计算
P(x)的时间复杂度为O(n)，因此总时间复杂度为
O(nlogM)

• 给一串整数a[1…n]，求出它和最大的子序

a[i]+a[i+1]+…+a[j]最大
• 例如 5 -6 3 -1 4, 和最大连续子序列为3 -1 4
• 介绍四个算法并分析时间复杂度
–
–
–
–

max := a[1];
for i:=1 to n do
for j:=i to n do begin
sum := 0;
for k:=i to j do
sum := sum + a[k];
if sum > max then max := sum;
end;
• 思想：枚举所有的i和j，计算a[i]+…+a[j]，选择最大的
• 时间复杂度如何分析？
– 三层循环
– 内层操作次数取决于i, j
– 中层操作次数取决于i

•
•
•
•

1
– 先计算里层求和号，得  ( n  i  1)( n  i  2)
2
n
n
i 1
ji
n
i 1
– 再加起来？好复杂…
– 直接算法需要利用公式12+…+n2=O(n3)
– 一般地，有1k+…+nk=O(nk+1). 证明: 数学归纳法

n
n
i 1
ji
• 总次数为：  ( j  i  1)
– 完全的计算太麻烦
– 能不能不动笔就知道渐进时间复杂度呢？
• 何必非要计算出详细的公式再化简呢？
– 里层求和计算出的结果是O((n-i+1)2)
– 12+22+…+n2=O(n3)
– 每步都化简！但是要保留外层需要的变量
• 结论：算法一时间复杂度为O(n3)
• 经验：一般只能支持 n<=200

• 思路
–
–
–
–

s[0] := 0;
for i:=1 to n do
s[i] := s[i–1] + a[i];

• 有了s[i]，怎么快速求a[i]+…+a[j]呢？
a[i]+…+a[j]
= (a[1] + … + a[j]) – (a[1] + … + a[i-1])
=s[j] – s[i-1]

max := a[1];
for i:=1 to n do
for j:=i to n do
if s[j] – s[i-1] > max then
max := s[j] – s[i-1];

• 用一种完全不同的思路
• 最大子序列的位置有三种可能
– 完全处于序列的左半，即j<=n/2
– 完全处于序列的右半，即i>=n/2
– 跨越序列中间，即i<n/2<j
• 用递归的思路解决！
– 设max(i, j)为序列a[i…j]的最大子序列, 那么…

• 用递归的思路解决！
– 设max(i, j)为序列a[i…j]的最大子序列
– 设mid = (i + j)/2，即区间a[i…j]的中点
• 最大的第一种序列为max(i, mid)
• 最大的第二种序列为max(mid+1, j)
• 问题：最大的第三种序列为？？？
– 既然跨越中点，把序列a[i…j]划分为两部分
• a[i…mid]：最大序列用扫描法在n/2时间内找到
– 一共只有mid-1=n/2种可能的序列，一一比较即可
• a[mid+1…j]：同理
• 一共花费时间为j-i+1

//返回数组在区间[x,y)中的最大连续和
int maxsum(int *A, int x, int y)
{
int i, m, v, L, R, max;
if (y-x == 1) return A[x]; //只有一个元素，直接返回
m = x + (y – x) / 2; // 分治第一步：划分成[x,m)和[m,y)
//分治第二步，递归求解
max = max_element(maxsum(A, x, m),maxsum(A, m, y));
//分治第三步：合并(1),求分界点开始向左的最大连续和；
v = 0; L = A[m-1];
for(i=m-1;i>=x;i--) L >?= v += A[i];
//分治第三步：合并[2],求分界点开始向右的最大连续和；
v = 0; R = A[m];
for(i=m;i<y;i++) R >?= v += A[i];
return max >? (L+R);
}

• 如何分析时间复杂度呢？
– 我们没有直接得到具体的T(n)的式子
– 但是容易得到递推关系T(n) = 2T(n/2) + n
• 设时间复杂度的精确式子是T(n)
• 第一、二种序列的计算时间是T(n/2)，因为序列长度

• 第三种序列的计算时间是n
– 由递归式四, 得T(n)=O(nlogn)

• 算法二的实质是求出i<=j,让s[j]-s[i-1]最大，即
s[i-1]尽可能小
– 对于给定的j，能否直接找到在j之前的最小s值呢？
– 从小到大扫描j
• j=1时，只有一个合法的i，即i=1, s[1-1]=0
• 如果s[j]变大，则最小的s值和上次一样
• 如果s[j]再创新低，应该让s[j]作为今后的最优s值
min_s := 0;
For j :=1 to n do begin
if s[j] < min_s then min_s := s[j];
if s[j] – min_s > max then
max := s[j] – min_s;
end;

O(n3)

O(n2)

O(nlogn)

O(n)

• 如何对n长序列里求m次区间询问的最大连

• 《山海经》是以山为纲，以海为线记载古代的河流、植物、

（i，j），使得他感到是最满意的，即（i，j）这条路上所

《山海经》中，第i座山只能到达第i+1座山。

Input
• 输入第一行是两个数n，m，2≤n≤100000，1≤m≤100000，
n表示一共有n座山，m表示老师想查询的数目。
• 第二行是n个整数，代表n座山的喜恶度，绝对值均小于
10000。
• 以下m行每行有两个数，a，b，1≤a≤b≤n，表示第a座山

Output
• 一共有m行，每行有三个数i，j，s，表示从第i座山到第j座

Sample Input
53
5 -6 3 -1 4
13
15
55
Sample Output
115
356
554
Closet Pair
Closet Pair
Closet Pair
•
•
•
•
•
Here's a high-level overview of the algorithm:
Find a value x for which exactly half the points have xi < x, and half
have xi > x. On this basis, split the points into two groups, L and R.
Recursively find the closest pair in L and in R. Say these pairs are
pL, qL and pR, qR, with distances dL and dR respectively. Let d be the
smaller of these two distances.
It remains to be seen whether there is a point in L and a point in R
that are less than distance d apart from each other. To this end,
discard all points with xi < x-d or xi > x+d and sort the remaining
points by y-coordinate.
Now, go through this sorted list, and for each point, compute its
distance to the seven sub-sequent points in the list. Let pM, qM be
the closest pair found in this way.
The answer is one of the three pairs {pL, qL}, {pR, qR}, {pM, qM},
whichever is closest.

• 给定平面上n个点的坐标, 找出其中距离最

• 枚举算法: 需要枚举O(n2)个点对, 每个距离

• 有更好的算法吗?

• 用分治法解决. 先按x坐标排序, 把所有点划分成

• 令d=min{dl, dr}, 则跨越两边的点对中，只有下

• 需要检查竖条里的所有点对吗? 不需要.
• 从上往下看, 对于任何一个p, 另一侧可能与它组

• 最坏情况(同一行的红蓝点几乎重合), 需要检查接

p

Closest-Pair(P, l, r)
if r – l < 3 then return Brute-Force(P, l, r)
q  (l+r)/2
dl  Closest-Pair(P, l, q-1)
dr  Closest-Pair(P, q, r)
d  min(dl, dr)
for i  l to r do
if P[q].x - d  P[i].x  P[q].x + d then
append P[i] to S
Sort S on y-coordinate
for j  1 to size_of(S)-1 do
if any of d(S[j],S[j+1]), ..., d(S[j],S[j+7])
is smaller than d, set d to the smallest
return d

• 由于合并时要把竖条内的点按y坐标排序, 因此合

• 递归方程:
n
T (n)  
 2T ( n / 2)  n log n
• 解得T(n)=O(nlog2n)
• 下面把它优化到O(nlogn)
if n  3
otherw ise

• 实现时把所有点分别按x和y排序放在两个

• Divide. 把点按x值分成两半后, 按顺序遍历
y表, 根据x值拆分成两个y表. 这一步O(n)
• Combine. 合并得到拆分前的y表, 同时把在

• 因此时间复杂度降为O(nlogn)
• 现详细描述对y表的两个操作

•
•
•
•
x表为: (1, 3), (2, 2), (3, 4), (4, 1)
y表为: (4, 1), (2, 2), (1, 3), (3, 4)

– 左边(红色)y表: (2, 2), (1, 3)
– 右边(蓝色)y表: (4, 1), (3, 4)
• 两个表仍分别按y坐标排序

• 递归调用以后可以按照归并排序中合并的

• 合并时检查每个点是否在竖条中. 如果在，

• 按顺序遍历bar, 如果bar[i]和bar[i+1~i+7]中

Karatsuba快速乘法

Divide:
For instance, if x = 101101102 , then xL = 10112, xR =
01102, and x = 10112 × 24 + 01102.
Conquer:

T(n) = 4 T(n/2) + O(n).

Karatsuba快速乘法
The mathematician Carl Friedrich Gauss (17771855) once noticed that although the product of
–
two complex numbers
(a + bi)(c + di) = ac – bd + (bc + ad)i
seems to involve four real-number
multiplications, it can in fact be done with just
three: ac, bd, and (a + b)(c + d), since
bc + ad = (a + b)(c + d) – ac – bd.
Karatsuba快速乘法

T(n) = 4 T(n/2) + O(n).

Karatsuba快速整数乘法
Strassen Matrix Multiplication
Strassen矩阵乘法

Strassen矩阵乘法算法
Strassen矩阵乘法算法
Strassen矩阵算法
• Divide: 把A和B划分成(n/2)*(n/2)个子矩阵
• Conquer: 递归对子矩阵进行7次乘法
• Combine: 对子矩阵进行加法和减法得到C

• 1965年由John Cooley和John Tukey提出
• 应用广泛，尤其在数字信号处理领域
• 被誉为二十世纪十大算法之一

An alternative representation of
polynomials
Fact: A degree-d polynomial is uniquely characterized by
its values at any d+1 distinct points.
Two forms of

Evaluation: 计算单个点的值O(n)，n个点总代价 O(n2).

Evaluation by divide-and-conquer

Evaluation by divide-and-conquer
Running time：
Problem solved?
Evaluation by divide-and-conquer

Interpolation
A matrix reformulation
A = MB, 矩阵M是范德蒙德矩阵，当x0,…,xn-1是互

Interpolation resolved
The columns of M are orthogonal. MM*=nI, M-1=(1/n)M*.
Inversion formula:

FFT algorithm

• Fi = a1Fi-1+a2Fi-2+a3Fi-3…+akFi-k
• 已知F1, F2, …, Fk, 求任意的Fn

• 通项公式
(
Fn 
1
5
) (
n
2
1
5
)
n
2
5
• 由于分子第二项小于1，可以只算第一项，舍入到

• 求幂可以用对数或倍增法
• 问题：精度误差！

• 可以直接写出递归代码
int fib(int n){
if(n < 2) return n;
else return fib(n-1) + fib(n-2);
}

• 记T(n)为计算fib(n)的时间复杂度
T(n)=T(n-1)+T(n-2),
• 设T(1)=T(2)=c, 则T(n)=c*Fn-2. 由于
fn+1
lim
n fn
5 + 1
=
2
= 1.618 ....
• 因此T(n) = O(1.618n), 指数时间算法!

• 依次计算出很多结果, 采用预处理的方式
• 时间复杂度仅为O(n), 但空间复杂度也上升

void precalc_fib(int n){
f[0] = 0; f[1] = 1;
for(int i = 2; i <= n; i++)
f[i] = f[i-1] + f[i-2];
}

• 在执行的过程中计算出了F1, F2, F3, … Fn,

• 如果的确需要得到所有值, 附加空间是必须

• 滚动数组: 把以后再也用不到的值及时扔掉
• 滚动的含义: 在递推的过程中, 数组内元素

• 下面的代码, f[0..2]实际代表Fi-2~Fi
int fib(int n){
f[1] = 0; f[2] = 1;
for(int i = 2; i <= n; i++){
f[0] = f[1]; f[1] = f[2];
f[2] = f[1] + f[0];
}
return f[2];
}

• 一开始f[1]=0, f[2]=1实际上是F0=0, F1=1
• 第i次循环时, 刚开始f[0], f[1], f[2]保存着Fi-3~Fi-1,

• 问题: 如果递推式比较长，每次需要花费比较多的

• 比较好的解决方法是用循环数组, 让f[p]为当前要

int fib(int n){
int p=1;
f[0] = 0; f[1] = 1;
for(int i = 2; i <= n; i++){
p = next(p);
f[p]=f[prev(p)] + f[prev(prev(p))];
}
return f[p];
}

• 注意到
1

1
1   F k 1   F k 1  F k   F k  1 
 
 


Fk
F
0   Fk  
  k 
• 从F0和F1出发, 由结合律得:
1

1
N
1
 F0   F N  1 

    
F
F
0
 1  N 
• 可用倍增法在O(logn)时间内求出幂(忽略高精度)

• 设
• 若
f i  a 1 f i 1  a 2 f i  2    a k f i  k


F0  



f k 1 

f k 2

 

f0 
 a1

1

A 0

 
0

,则
a2
a3

0
0

1
0




ak 

0

0 

 
0 
 f i  k 1 


f
i k 2 
i

Fi  A  F0 
  


 fi 
0

1

• Problem: How to find the root of the function f?
r such that f(l)>0 and f(r)<0. If f is a
continuous function, there must exist a root
between l and r. Depending upon the sign of
f(m), where m=(l+r)/2, we can cut this
window containing the root in half with each test
and stop soon as our estimate becomes
sufficiently accurate.
• sicily 1017 Rate of Return.

• 有一个2k*2k的方格组成的棋盘, 恰有一个方格是

• 需要用三个方格的L型骨牌覆盖所有白色方格. 黑

• 试找一个方案

• 设2k*2k的问题可以用递归过程COVER(k)
COVER(k)可通过递归调用4次COVER(k-1)实现

• 递归方程为T(k) = 4T(k-1) + O(1)
• 递归方程的解为T(k)=O(4k), 而骨牌数目为
(4k-1)/3个, 因此渐进意义下这是最优的
VLSI布线问题
• 把一棵有n个结点的完全二叉树嵌入到网格

H型嵌入

• 有2k个运动员要进行网球循环赛, 需要设计

– 每个选手必须与其他n-1个选手各赛一次
– 每个选手一天只能赛一次
– 循环赛一共进行n-1天
• 按此要求可将比赛日程表设计成有n行和n1列的一个表, 第i行j列为第i个选手第j天遇

• K=3时, 一种方案如下表(第一列为队员编号)
– 蓝色为红色对应元素加4得到
– 把左上角(红)拷贝到右下角, 把左下角(蓝)拷贝到右上角
Questions
Question
• Given a sorted array of distinct integers
A[1, …, n], you want to find out whether
there is an index i for which A[i] = i. Give a
divide-and-conquer algorithm that runs in
time O(log n).
1
2
3
4
5
6
7
-5
-1
3
6
8
13
20
Question: majority element
• An array A[1 … n] is said to have a majority element if
more than half of its entries are the same.
• Given an array, the task is to design an efficient
algorithm to tell whether the array has a majority
element, and, if so, to find that element.
• The elements of the array are not necessarily from some
ordered domain like the integers, and so there can be no
comparisons of the form “
is A[i] > A[j]?
” (Think of the
array elements as GIF files, say.) However you can
answer questions of the form: 
”is A[i] = A[j]?”in constant
time.
Question: majority element
• Find a divide-and-conquer algorithm to solve problem in
O(n log n) time.
• Hint: Split the array A into two arrays A1 and A2 of half
the size. Does knowing the majority elements of A1 and
A2 help you figure out the majority element of A? If so,
you can use a divide-and-conquer approach.
Question: majority element
• Can you give a linear-time algorithm?
• Hint: Here's another divide-and-conquer approach:
– Pair up the elements of A arbitrarily, to get n/2 pairs
– Look at each pair: if the two elements are different,
discard both of them; if they are the same, keep just
one of them
Show that after this procedure there are at most n/2
elements left, and that they have a majority element if
and only if A does.

• 有n个螺丝，它们大小互不相同，能和n个

• 请给出一个算法，将螺丝和螺帽配对，并

• sicily 1017 Rate of Return. 求解方程，二

• sicily 1211 商人的宣传. 求两点间L步到达

• sicily 1137 河床. 求一个最长的连续区间满

• sicily 1441 Pie 二分
```