Divide and Conquer

分析图

image-20220427094855469

简介

image-20220427094923965

适用条件

image-20220427094937897

image-20220427094957403

算法实现

image-20220427095330544

算法分析

image-20220427095444695

image-20220427095601706

大整数相乘

image-20220427095829017

  • 利用（AD+BC）=（A+B）*（C+D）-AC-BD替换，将4次乘法运算降低到3次

image-20220427095843738

分治策略举例

  • 二分查找

  • 二叉查找树，平衡二叉树，B树和B+树

  • 排序问题

    • 归并排序（Merge Sort）
    • 快速排序

二分查找

image-20220427100822850

image-20220427101006001

image-20220427101015852

归并排序

Merge Sort

image-20220427103603103

image-20220427103721937

image-20220427103727652

快速排序

image-20220427214307114

image-20220427214321845

1
2
3
4
5
6
7
8
9
10
11
12
13
void quicksort(int arr[], int low, int high) {
	if (low >= high) return;//没有数返回
	int l = low, h = high;
	int x = arr[low];
	while (low < high) {
		while ((low < high) && (arr[high] >= x)) high--;
		swap(arr[low], arr[high]);
		while ((low < high) && (arr[low] <=x))low++;
		swap(arr[low], arr[high]);
	}
	quicksort(arr, l, high - 1);
	quicksort(arr, high +1 ,h);
}

棋盘覆盖问题

image-20220427104204004

image-20220427104337675

image-20220427110157988

image-20220427110213180

image-20220427110223580

循环赛日程表

image-20220427110248747

1
2
3
4
5
6
7
8
9
10
11
12
Void Dimidiate（int i, int j, int n)
           //起始行i，终止行j，规模n
{  if(n==2)
      { a[i][n]=j; a[j][n]=i; a[i][n-1]=i; a[j][n-1]=j;}
   else {
        dimidiate(i,i+n/2-1,n/2); )    //处理左上角
        dimidiate(i+n/2,j,n/2);     //处理左下角
        左上角复制到右下角；
        左下角复制到右上角；
       }
    输出a；
}

总结

image-20220427110332769

配套作业

配套作业——分治策略

https://gallifrey.asia/posts/f5ccd0a9e3db/