Algorithm Design and Analysis - Divide-and-Conquer

Author Avatar
Jiawen Zhang Sep 24, 2018

Main message:

  1. 从最简单的case入手
  2. 看能否分，能否combine
  3. 不求最优，只要次优

一、Remarks

1.对于ClosestPair问题，若暴力破解法将花费多项式时间，分治法通常可被用于节省运行时间：\(O(n^2)\) \(\implies\) \(O(nlogn)\) 2.这个技巧若与随机技巧结合将非常有威力

在使用分治法之前，需要先检验输入（i.e.问题是否可以被分为结构相似，规模更小的子问题）以及输出（i.e.原问题的解是否能够用子问题的解组合而成）

二、Sort Problem

将长度为n的数组排序

INPUT: An array of n integers, say A[0..n-1];
OUTPUT: The items of A in increasing order.

方法1.将其分为n-1长度的数列和一个元素

第一种方法可以从最简单的case入手，从n=2，n=3，到逐步解决原问题

分离出一个元素 
1
2
3
4
5
6
7
8
9
10
InsertionSort( A, n )
	for j = 0 to n - 1 do
		key = A[j];
		i = j - 1;
		while i >= 0 and A[i] > key do
			A[i + 1] = A[i];
			i --;
		end while
		A[i + 1] = key;
	end for

最差的情况：A数组里的元素为逆序

时间复杂度： \(T(n)=T(n-1)+O(n)=O(n^2)\)

最差情况

方法2.将其分为两个独立的子问题(MERGE SORT)

将数组\(A[0..n-1]\)分为两个数组\(A[0..\frac{n}{2}-1]\)以及\(A[\frac{n}{2}-1..n-1]\)

分为子问题 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
MergeSort(A; l; r) //从l到r之间排序
	// To sort part of the array A[l::r]
	if l < r then
		m = (l + r)=2; //m denotes the middle point
		MergeSort(A; l; m );
		MergeSort(A; m + 1; r);
		Merge(A; l; m; r); //Combining the sorted arrays
	end if
Merge (A; l; m; r) //将左端最小与右端最小比较
	//Merge A[l::m] (denoted as L) and A[m + 1::r](denoted as R).
	i = 0; j = 0;
	for k = l to r do
		if L[i] < R[j] then
			A[k] = L[i];
			i + +;
		else
			A[k] = R[j];
			j + +;
		end if
	end for

时间复杂度：O(n)

mergesort

三、迭代的时间复杂度的分析方法：

  1. Unrolling the recurrence 硬展开
  2. Guess and substitution 猜然后验证
  3. Master theorem

technique 1: Unrolling the recurrence

We have \(T(n) = 2T(\frac{n}{2}) + O(n) <= 2T(\frac{n}{2}) + cn\) for a constant c. Let unrolling a few levels to find a pattern, and then sum over all levels.

Unrolling

technique 2: Guess and substitution

Guess and substitution: guess a solution, substitute it into the recurrence relation, and justify that it works.

Guess

technique 3:Master theorem 主定理

Let T(n) be defined by \(T(n)=aT(\frac{n}{b})+O(n^d)\) for a > 1, b > 1 and d > 0, 其中n为问题规模，a为递推的子问题数量,\(\frac{n}{b}\)为每个子问题的规模（假设每个子问题的规模基本一样）， 为递推以外进行的计算工作. then T(n) can be bounded by:

  1. If d < \(\log_b a\), then \(T(n)=O(n^{\log_b a})\);
  2. If d = \(\log_b a\), then \(T(n)=O(n^{\log_b a} \log n)\);
  3. If d > \(\log_b a\), then \(T(n)=O(n^d)\).

四、Counting Inversion Problem 数逆序对

To count inversions in an array of n integers

INPUT: An array $A[0..n]$ with n distinct numbers; 
OUTPUT:the number of inversions. A pair of indices i and j constitutes an inversion if i < j butA[i] > A[j].
CountingInversion

可使用分治法解决数逆序对问题，其中Divide和Conquer部分与之前排序问题相同，即将问题分为两个独立的子问题。Combine部分有两种策略。

策略1：若\(A[0..\frac{n}{2}-1]\)以及\(A[\frac{n}{2}..n-1]\)没有特殊的结构，则我们需要检查所有可能的配对\((i,j)\)去检查逆序。即若左右数都是任意的，就必须写For循环。

时间复杂度为：\(T(n)=2T(\frac{n}{2})+\frac{n^2}{4}=O(n^2)\)

strategy1

策略2：若每一部分为升序，则相对容易计算逆序

strategy2 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
Sort-and-Count(A)
	Divide A into two sub-sequences L and R;
	(RCL, L) = Sort-and-Count(L);
	(RCR, R) = Sort-and-Count(R);
	(C, A) = Merge-and-Count(L, R);
	return (RC = RCL + RCR + C, A);
Merge-and-Count (L; R)
	RC = 0; i = 0; j = 0;
	for k = 0 to ∥L∥ + ∥R∥ - 1 do
		if L[i] > R[j] then
			A[k] = R[j];
			j + +;
			RC+ = (n/2 - i);
		else
			A[k] = L[i];
			i + +;
		end if
	end for
	return (RC, A);

时间复杂度为：\(T(n)=2T(\frac{n}{2})+O(n)=O(n\log n)\)

五、The general Divide and Conquer paradigm

Basic Idea

Many problems are recursive in structure, i.e., to solve a given problem, they call themselves several times to deal with closely related sub-problems. These sub-problems have the same form to the original problem but a smaller size.

Three Steps

  1. Divide a problem into a number of independent sub-problems;
  2. Conquer the subproblems by solving them recursively;
  3. Combine the solutions to the subproblems into the solution to the original problem.

Quick Sort algorithm

Divide according to a randomly-selected pivot.根据随机选取的轴进行分割。

1
2
3
4
5
6
7
8
9
10
QuickSort(A)
	S_ = {}; S+ = {};
	Choose a pivot A[j] uniformly at random;
	for i = 0 to n - 1 do  //将比A[j]小的放在左边，大的放在右边
		Put A[i] in S_ if A[i] < A[j];
		Put A[i] in S+ if A[i] >= A[j];
	end for
	QuickSort(S+);
	QuickSort(S_);
	Output S_, then A[j], then S+;
  • 随机的操作使得这个算法变得简单而高效
  • 然而，随机增加了分析的难度，我们不能保证取到每个问题的第\(\frac{n}{2}\)个元素

最差的情况：选取到了每个迭代中最大/最小的元素

\[T(n) = T(n - 1) + O(n) = O(n^2)\]

最好的情况：选取到了每个迭代中最中间的元素

\[T(n) = 2T(\frac{n}{2}) + O(n) = O(n\log n)\]

大多数情况：选取到了一个接近中心的轴。这种情况我们认为期望的运行时间仍为：

\[T(n) = O(n\log n)\]

Analysis

Observation 1: 对于任意i,j而言，\(A[i]\)和\(A[j]\)之间最多被比较一次。

Observation 2: 当处理包含\(A[i..j]\)的元素时，当且仅当\(A[i]\)或\(A[j]\)被选为枢轴时比较\(A[i]\)和\(A[j]\)。

Modified Quick Sort

在原算法上寻找一个好的分点（大于\(/frac{n}{4}\)小于\(/frac{3n}{4}\)的点）。它在所有项目都不同时有用，然而耗内存，且在比原算法更慢，因为当它偏离中心点时不运行。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
ModifiedQuickSort(A)
	while TRUE do
		Choose a pivot A[j] uniformly at random;
		S_ = {}; S+ = {};
		for i = 0 to n - 1 do
			Put A[i] in S_ if A[i] < A[j];
			Put A[i] in S+ if A[i] > A[j];
		end for
		if ∥S+∥ >= n/4 and ∥S_∥ >= n/4 then
			break;
		end if
	end while
	ModifiedQuickSort(S+);
	ModifiedQuickSort(S_);
	Output S_, then A[j], and finally S+;
nearcenter

比起中心轴，近中心轴更容易获得。获得一个中心点为轴的概率是\(frac{1}{n}\),而获得一个近中心轴的概率是\(frac{1}{2}\)。因此，找到一个近中心轴的期望时间为2n。此时我们不追求最优的pivot，只选择足够好。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
\\Lomuto’s implementation
\\in-place sort 不花内存。
QuickSort(A; l; h)
	if l < h then
		p =Partition(A; l; h);
		QuickSort(A; l; p - 1);
		QuickSort(A; p + 1; h);
	end if
Partition(A; l; h)
	pivot = A[h]; i = l - 1;
	for j = l to h - 1 do
			if A[j] < pivot then
			i + +;
			Swap A[i] with A[j];
		end if
	end for
	if A[h] < A[i + 1] then
		Swap A[i + 1] with A[h];
	end if
	return i + 1;
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
\\Hoare’s implementation
QuickSort(A; l; h)
	if l < h then
		p =Partition(A; l; h);
		QuickSort(A; l; p); //Reason: A[p] might not be at its correct position
		QuickSort(A; p + 1; h);
	end if
Partition(A; l; h)
	i = l - 1; j = h + 1; pivot = A[l];
	while TRUE do
		repeat
			j = j - 1;
		until A[j] <= pivot or j == l;
		repeat
			i = i + 1;
		until A[i] >= pivot or i == h;
		if i >= j then
			return j;
		end if
		Swap A[i] with A[j];
	end while

快速排序只在无重复元素时性能好，若有重复的元素，可用PARTITION算法来解决这个问题，即将数列分为三部分：比pivot大，与pivot相等，比pivot小。仅需对不等于pivot的partitions进行迭代排序。

Selection problem

找到数组中第K小的item

INPUT:An array A = [A0, A1,.., An_1], and a number k < n;
OUTPUT:The k-th smallest item in general case (or the median of A as a specical case).

若先将A排序再寻找第k个值，时间复杂度为\(O(nlog n)\)。相反地，若使用分治法，则有可能开发出更快的算法（e.g.deterministic linear algorithm by Blum et al.）。时间复杂度为\(O(n)\)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
Select(A; k)
	Choose an element Ai from A as a pivot;
	S+ = {};
	S_ = {};
	for j = 1 to n do
		if Aj > Ai then
			S+ = S+ U {Aj};
		else
			S_ = S_ U {Aj};
		end if
	end for
	if |S_| = k - 1 then
		return Ai;
	else if |S_| > k - 1 then
		return Select(S_; k);  \\S的size越小越好
	else
		return Select(S+; k - |S_| + 1);
	end if

How to choose a pivot?

对于pivot（中心元），我们有三种选择方式：

最差的选择：选取到了每个迭代中最小的元素(线性下降)

\[T(n) = T(n - 1) + O(n) = O(n^2)\]

最好的选择：选取到了每个迭代中最中间的元素（指数级下降）

\[T(n) = T(\frac{n}{2}) + O(n) = O(n)\]

好的选择：选取到了一个接近中心的pivot。（子问题最坏的情况也是指数级下降）

\[T(n) ≤ T((1 − ϵ)n) + O(n) ≤ cn + c(1 − ϵ)n + c(1 − ϵ)^2 + .... = O(n)\]

How to select a nearly-central pivot?

我们可以通过以下几种方式尝试获得一个完整集合的中间值：

  • Selecting a central pivot via examining medians of groups
  • Selecting a central pivot via randomly selecting an element
  • Selecting a central pivot via examining a random sample

Strategy 1:BFPRT algorithm uses median of medians as pivot

BFPRT

SelectMedian(A) Line up elements in groups of 5 elements; 2. Find the median of each group; //cost \(\frac{6n}{5}\) time 3. Find the median of medians (denoted as M)through recursively running Select over the group medians; // \(T(\frac{n}{5})\) time 4. Use M as pivot to partition A into S_ and S+; //\(O(n)\) time 5. if |S_| = k - 1 then 6. return M; 7. else if |S_| > k - 1 then 8. return Select(S_; k); //at most \(T(\frac{7n}{10})\) time 9. else 10. return Select(S+; k - |S_| - 1); //at most \(T(\frac{7n}{10})\) time 11. end if

这种方法较耗内存，我们也可以使用原位替换的算法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
Select(A; l; r; k)
	while TRUE do
		if l == r then
			return l;
		end if
		p =Pivot(A; l; r); //Use median of medians A[p] as pivot ;
		pos =Partition(A; l; r; p); //pos represents the final position of the pivot, A[l..pos - 1] deposit S_ and A[pos + 1..r] deposit S+;
		if (k - 1) == pos then
			return k - 1;
		else if (k - 1) < pos then
			r = pos - 1;
		else
			l = pos + 1;
		end if
	end while
//
Pivot(A, l, r)
	if (r - l) < 5 then
		return Partition5(A, l, r); //Get median for 5 or less elements;
	end if
	for i = l to r by 5 do
		right = i + 4;
		if right > r then
			right = r;
		end if
		m =Partition5(A, i, right); //Get median of a group;
		Swap A[m] and A[l + [(i-1)/5]];
	end for
	return Select(A, l, l + [(r-l)/5],(r-l)/10 + 1);
//
Partition(A, l, r, p)
	pivot = A[p];
	Swap A[p] and A[r]; //Move pivot to the right end;
	i = l;
	for j = l to r - 1 do
		if A[j] < pivot then
			Swap A[i] and A[j];
			i + +;
		end if
	end for
	Swap A[r] and A[i];
	return i;

图解：

part1
part2
part3

Strategy 2: QuickSelect algorithm randomly select an element as pivot

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
QuickSelect(A, k)
	Choose an element Ai from A uniformly at random;
	S+ = {};
	S_ = {};
	for all element Aj in A do
		if Aj > Ai then
			S+ = S+ U {Aj};
		else
			S_ = S_ U {Aj};
		end if
	end for
	if |S_| = k - 1 then
		return Ai;
	else if |S_| > k - 1 then
		return QuickSelect(S_; k);
	else
		return QuickSelect(S+; k - |S_| - 1);
	end if

Basic idea: when selecting an element uniformly at random, it is highly likely to get a good pivot since a fairly large fraction of the elements are nearly-central.

atRandom

The expected running time of QuickSelect: T(n) = O(n);

Strategy 3: Floyd-Rivest algorithm selects a pivot based on random samples

Floyd-Rivest 
1
2
3
4
5
6
Floyd-Rivest-Select(A; k)
	Select a small random sample S (with replacement) from A.
	Select two pivots, denoted as u and v, from S through recursively calling Floyd-Rivest-Select. The interval [u, v], although small, is expected to cover the k-th smallest element of A.
	Divide A into three dis-joint subsets: L contains the elements less than u, M contains elements in [u; v], and H contains the elements greater than v.
	Partition A into these three sets through comparing each element Ai with u and v: if k <= n2, Ai is compared with v first and then to u only if Ai <= v. The order is reversed if k > n2.
	The k-th smallest element of A is selected through recursively running over an appropriate subset.

六、例题

note:一般来说，对于1维问题而言，我们可以将其分为两部分来解决问题。对于二维问题而言，我们可以将其分为横纵四个子问题来解决。但这并不是对所有情况都适用。

1. ClosestPair problem

Given a set of points in a plane, to find the closest pair.

INPUT: n points in a plane;
OUTPUT: The pair with the least Euclidean distance.

暴力做法的时间复杂度为\[T(n^2)\],存在很多的冗余。 由于将平面分为四个部分会使点的分布不均，我们将平面分割为内含均匀数量的点的两个平面，分别计算两个平面内的最小对点距离，再计算跨越两个平面的最小距离。 我们可以观察到，我们仅需检查中线周围以两个平面中较小的最小距离为宽度的区域就足够。

ClosestPair1

并且，我们不需要检查条形区域内的所有点。检查它周围的11个点已足够。 我们将两倍宽度的长条分解成格子，每个格子中最多包含一个点，否则表明之前计算出的最小距离有误。 我们对y轴进行排序，然后仅需将每个点与其周围11个点进行比对。

ClosestPair2 
1
2
3
4
5
6
7
8
9
10
11
ClosestPair(pl; :::; pr)
	//To find the closest points within (pl; :::; pr). Here we assume that pl,...,pr have already been sorted according to x-coordinate;
	if r - l == 1 then
		return d(pl; pr);
	end if
	Use the x-coordinate of p((l+r)/2) to divide pl,...,pr into two halves;
	d1 = ClosestPair(LeftHalf); //T(n2)
	d2 = ClosestPair(RightHalf); //T(n2)
	d = min(d1; d2);
	Sort points within the 2d wide strip by y-coordinate; //O(n log n)
	Scan points in y-order and calculate distance between each point with its next 11 neighbors. Update d if finding a distance less than d;  //O(n)

Time-complexity: \[T(n) = 2T(\frac{n}{2}) + O(n log n) = O(n log^2 n)\].

为了是复杂度降到O(n),我们可以引入structure，使用merge将每一个子问题先排序。

实例：

ClosestPair3