算法笔记（一）：递归与分治法

绝地灬酷狼 2022-12-18 03:55 161阅读 0赞

# 一、基本思想 #

（一）分治法的基本思想是：将规模较大的、不容易解决的大问题，分割为性质相同但规模较小的子问题，若子问题易于求解，则分别求解子问题，然后由子问题的解构造出原问题的解。**适合用分治法求解的问题一般都具有以下基本特征：**  
（1）该问题可以分解为若干个规模较小的子问题；  
（2）该问题的规模缩小到一定的程度后容易求解；  
（3）各个子问题相互独立；  
（4）子问题的解可以合并为原问题的解。  
**分治法求解问题的步骤主要包括三步：**  
（1）分解（Divide）。当问题的规模超过某一阈值时，将问题分解为规模较小但性质与原问题相同且容易解决的子问题；  
（2）递归求解子问题（Conquer）。当子问题的规模不超过阈值，且子问题容易求解出，直接解子问题；否则，将问题分解为子问题，按相同策略递归求解各个子问题。  
（3）合并子问题的解（Merge）。采用合并算法，将各个子问题的解合并为原问题的解。  
（二）分治法的计算时间：  
 T ( n ) = \{ O ( 1 ) , n = 1 a T ( n / b ) + f ( n ) n > 1 T(n)=\\left\\\{ \\begin\{array\}\{lcl\} O(1), & & \{n = 1\}\\\\ aT(n/b)+f(n) & & \{n >1\} \\end\{array\} \\right. T(n)=\{ O(1),aT(n/b)\+f(n)n=1n>1  
其中a表示子问题数量，n/b表示每个子问题的规模，合并子问题所需时间为f(n)。  
用主定理法解此递归函数，得到  
 T ( n ) = \{ O ( n k ) , a < b k O ( n k l o g b n ) , a = b k O ( n ( l o g b a ) ) , a > b k T(n)=\\left\\\{ \\begin\{array\}\{rcl\} O(n^k),&&\{a<b^k\}\\\\ O(n^klog\_bn),&&\{a=b^k\}\\\\ O(n^(log\_ba)),&&a>b^k \\end\{array\}\\right. T(n)=⎩⎨⎧O(nk),O(nklogbn),O(n(logba)),a<bka=bka>bk  
其中k表示f(n)中n的幂。  
下面介绍几种分治策略的经典算法，包括二分搜索技术、合并排序、快速排序。

# 二、经典算法介绍 #

## 二分搜索 ##

假定给定已按升序排好序的n个元素a\[0:n-1\]，现要在这n个元素中找出某个特定元素x，例如，在数组a\[0:6\]=\{2,4,6,8,10,12,14\}中找出是否有元素10。最容易想到的方法是顺序查找，即从第一个元素开始依次比较直到找到或找不到需要的元素，该方法的时间复杂度为O(n)。但这种方法并没有充分利用到元素之间的次序关系，而二分搜索则可以。**以在数组a\[0:6\]=\{2,4,6,8,10,12,14\}中查找是否有10为例说明搜索过程：**  
（1）初始化时，left=0，right=6，如图  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0hvc2hpem9sYQ_size_16_color_FFFFFF_t_70_pic_center]（2）因为left=0，right=6，所以middle=(left+right)/2=3，如图  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0hvc2hpem9sYQ_size_16_color_FFFFFF_t_70_pic_center 1]显然10大于a\[3\]，接下来需要在数组右半部分查找，修改数组左边界，令left=middle+1=4,如图  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0hvc2hpem9sYQ_size_16_color_FFFFFF_t_70_pic_center 2]（3）因为left=4，right=6，所以middle=(left+right)/2=5，如图  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0hvc2hpem9sYQ_size_16_color_FFFFFF_t_70_pic_center 3]显然10小于a\[5\]，接下来需要在数组左半部分寻找元素10，修改数组右边界，令right=middle-1=4，如图  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0hvc2hpem9sYQ_size_16_color_FFFFFF_t_70_pic_center 4]（4）因为left=right=4,所以middle=(left+right)/2=4，此时10=a\[4\]，算法结束。

二分搜索将规模为n的问题简化成规模为n/2的子问题，用递归方程分析该算法的效率：  
 T ( n ) = \{ O ( 1 ) , n = 1 a T ( n / b ) + f ( n ) n > 1 T(n)=\\left\\\{ \\begin\{array\}\{lcl\} O(1), & & \{n = 1\}\\\\ aT(n/b)+f(n) & & \{n >1\} \\end\{array\} \\right. T(n)=\{ O(1),aT(n/b)\+f(n)n=1n>1

T(n)=T(n/2)+O(1)，a=1，b=2，k=0，则a=bk，T(n)=O(logn)。  
**Java代码实现如下**

public class BinarySearch { 
    
    	public static void main(String[] args) { 
    	    int[] arr = { 1, 8, 12, 15, 16, 21, 30, 35, 39};
    		int a = binarySearch(arr, 30, arr.length);
    		System.out.println("30的下标为：" + a);
    	}
    	public static int binarySearch(int[] arr, int i, int len) { 
    		int left = 0;
    		int right = len - 1;
    		while(left < right) { 
    			int middle = (left + right) / 2;
    			if (i == arr[middle])
    				return middle;
    			if (i > arr[middle])
    				left = middle + 1;
    			else
    				right = middle - 1;
    		}
    		return -1;
    	}
    }

### 合并排序 ###

给定一个包含n个元素的一维线性序列，例如a\[0:7\]=\{8,4,5,6,2,1,7,3\}，将这n个元素按照非递减顺序排序。合并排序基本思想：首先将n个待排序元素分成两个规模大致相同的子数组。如果子数组规模依然较大，那么继续分割子数组，当子数组只包含单个元素时，认为单元素数组已经排好序，这时将相邻的两个有序子数组两两合并成所要求的有序序列。**如图所示为合并排序算法的完整运算过程：**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0hvc2hpem9sYQ_size_16_color_FFFFFF_t_70_pic_center 5]合并排序算法将规模为n的问题分解为两个规模为n/2的子问题，用递归方程分析合并排序算法的计算效率：  
 T ( n ) = \{ O ( 1 ) , n = 1 a T ( n / b ) + f ( n ) n > 1 T(n)=\\left\\\{ \\begin\{array\}\{lcl\} O(1), & & \{n = 1\}\\\\ aT(n/b)+f(n) & & \{n >1\} \\end\{array\} \\right. T(n)=\{ O(1),aT(n/b)\+f(n)n=1n>1

T(n)=2T(n/2)+O(n)，a=2，b=2，k=1，则a=bk，T(n)=O(nlogn)。

**Java代码实现如下**

public class MergeSort { 
    	
    	static int[] arr = { 23, 5, 9, 16, 30, 25, 17, 18};
    	public static void main(String[] args) { 
    		mergeSort(arr, 0, arr.length-1);
    		for(int i = 0; i < arr.length; i++) { 
    			System.out.print(arr[i]+" ");
    		}
    		
    	}
    	static int[] copy_arr = new int[arr.length];//保存有序序列的数组
    	public static void mergeSort(int[] arr, int left, int right) { 
    		if(left < right) { 
    			int i = (left + right) / 2;
    			mergeSort(arr, left, i);
    			mergeSort(arr, i + 1, right);
    			merge(left, i, right);
    			copy(left, right);
    		}
    	}
    	
    	public static void merge(int left, int middle, int right) { 
    		int l = left;//左子数组下标游标
    		int j = middle + 1;//右子数组下标游标
    		int k = l;//copy_arr数组下标游标
    		while(l <= middle && j <= right) { 
    			if(arr[l] < arr[j]) { 
    				copy_arr[k++] = arr[l++];
    			}else { 
    				copy_arr[k++] = arr[j++];
    			}
    			if(l > middle) { //左数组已经排完
    				while(j <= right) { 
    					copy_arr[k++] = arr[j++];
    				}
    			}
    			if(j > right) { //右数组已经排完
    				while(l <= middle) { 
    					copy_arr[k++] = arr[l++];
    				}
    			}
    		}
    	}
    
    	public static void copy(int left, int right) { 
    		for(int i = left; i <= right; i++) { 
    			arr[i] = copy_arr[i];
    		}
    	}
    }

### 快速排序 ###

（一）给定一个包含n个元素的一维线性序列a\[p:r\]，例如a\[0:7\]=\{5,3,1,9,8,2,4,7\}，将这n个元素按照非递减顺序排序。快速排序利用分治策略排序的步骤如下：  
1、**分解**。首先选择一个元素作为划分的基准，默认选择第一个元素，从第二个元素开始，将数组中的元素与基准一一比较，将比基准小的元素放在基准元素的左边，比基准大的元素放在右边。扫描结束时，数组被分为三段，基准位于中间位置，所在的位置为q，即中间子数组为a\[q\]，比基准元素小的元素构成左子数组a\[p:q-1\]，比基准元素大的元素构成右子数组a\[q+1:r\]。  
2、**递归求解**。左右两个子数组是与原问题相同的两个子问题。若子数组长度为1，则为有序的；否则采用相同的策略递归求解左、右子问题。  
3、**合并**。对于每个基准元素而言每次分解都完成了对这个元素的排序，因此快排无需合并这个步骤。  
（二）**以a\[0:7\]=\{5,3,1,9,8,2,4,7\}为例说明快排的计算过程：**  
**1**、初始化时，p=0，r=7,设基准元素x=a\[p\]=a\[0\]=5，设置两个游标，令i=p，j=r+1。从第2个元素开始由左向右找比5大的元素，找到a\[3\]=9，i=3；接着从最后一个元素开始由右向左找比5小的元素，找到a\[6\]=4，j=6；交换a\[3\]和a\[6\]；继续从a\[3\]开始由左向右找比5大的元素，找到a\[4\]=8，i=4；继续从a\[6\]开始由右向左找比5小的元素，找到a\[5\]=2，j=5；交换a\[4\]和a\[5\]；继续从a\[4\]开始从左向右找比5大的元素，找到a\[5\]=8，i=5；继续从a\[5\]开始从右向左找比5小的元素，找到a\[4\]=2，j=4；这时i>j，停止比较，将a\[0\]与a\[4\]交换；将j的值返回，赋给变量q，q=4；至此，基准元素5左边的元素比它小，右边的元素比它大，基准元素5确定了其在有序数组中的最终位置。如图：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0hvc2hpem9sYQ_size_16_color_FFFFFF_t_70_pic_center 6]**2**、数组a\[0:7\]被划分为3段：a\[0:3\]、a\[4\]、a\[5:7\]。接下来按照同样的策略，通过递归调用快速排序算法分别对a\[0:3\]与a\[5:7\]进行排序，最终所有数据被排成有序序列。如图：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0hvc2hpem9sYQ_size_16_color_FFFFFF_t_70_pic_center 7]**Java代码实现如下**

public class QuickSort { 
    	
    	static int[] arr = { 8, 4, 3, 7, 1, 5, 6, 2};
    	public static void main(String[] args) { 
    		quickSort(0, arr.length-1);
    		System.out.println("排序后：");
    		for(int i = 0; i < arr.length; i++) { 
    			System.out.print(arr[i] + " ");
    		}
    	}
    
    	public static void quickSort(int p, int r) { 
    		if(p < r) { 
    			int q = partition(p, r);
    			quickSort(p, q - 1);
    			quickSort(q + 1, r);
    		}
    	}
    
    	public static int partition(int p, int r) { 
    		int k = arr[p];
    		int i = p;
    		int j = r+1;
    		while(true) { 
    			while(arr[++i] < k && i < r) { }
    			while(arr[--j] > k && j > p) { }
    			if(j <= i)
    				break;
    			swap(i, j);
    		}
    		arr[p] = arr[j];
    		arr[j] = k;
    		return j;
    	}
    
    	public static void swap(int i, int j) { 
    		int temp = arr[i];
    		arr[i] = arr[j];
    		arr[j] = temp;
    	}
    }

3、时间复杂度分析  
（1）最好情况。快排在最好情况下将规模为n的问题分解为两个规模为n/2的子问题。计算效率为如下：  
 T ( n ) = \{ O ( 1 ) , n = 1 a T ( n / b ) + f ( n ) n > 1 T(n)=\\left\\\{ \\begin\{array\}\{lcl\} O(1), & & \{n = 1\}\\\\ aT(n/b)+f(n) & & \{n >1\} \\end\{array\} \\right. T(n)=\{ O(1),aT(n/b)\+f(n)n=1n>1

T(n)=2T(n/2)+O(n)，a=2，b=2，k=1，则a=bk，T(n)=O(nlogn)。  
（2）最坏情况。快排算法的执行效率取决于基准元素的选择。然而，如果给定的数组本身是有序的，那么每次选择第一个元素作为基准元素时，就会出现划分不平衡的情况，最坏时间复杂度为O(n2)：  
 T ( n ) = \{ O ( 1 ) , T ( n − 1 ) + O ( n ) T(n)=\\left\\\{ \\begin\{array\}\{lcl\} O(1), \\\\ T(n-1)+O(n) \\end\{array\} \\right. T(n)=\{ O(1),T(n−1)\+O(n)  
（3）为了解决最坏情况下时间复杂度为O(n2)的问题，常用的方法有平衡快速排序法和基于随机支点选择的快速排序法。**平衡快速排序法**取数组开头、中间和结尾的元素，在三个元素中取中值，将中值元素作为基准元素。基于随机支点选择的快速排序法则是在数组中随机选择一个元素作为基准元素。然而，基于随机支点选择的快排在最坏情况下的时间复杂度依然是O(n2)，但是理论上出现的概率仅为1/2n，发生概率极低，因此不讨论最坏时间复杂度。基于随机支点选择的快排的平均时间复杂度为  
 T ( n ) = \{ O ( 1 ) , 2 T ( n / 2 ) + O ( n ) T(n)=\\left\\\{ \\begin\{array\}\{lcl\} O(1), \\\\ 2T(n/2)+O(n) \\end\{array\} \\right. T(n)=\{ O(1),2T(n/2)\+O(n)  
T(n)=O(nlogn)。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0hvc2hpem9sYQ_size_16_color_FFFFFF_t_70_pic_center]: /images/20221122/7218e84d6c6546e28c479cd84ab1e8cb.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0hvc2hpem9sYQ_size_16_color_FFFFFF_t_70_pic_center 1]: https://img-blog.csdnimg.cn/20201025131854346.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0hvc2hpem9sYQ==,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0hvc2hpem9sYQ_size_16_color_FFFFFF_t_70_pic_center 2]: /images/20221122/fee61e35b40143c19cf6939e1989c57b.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0hvc2hpem9sYQ_size_16_color_FFFFFF_t_70_pic_center 3]: https://img-blog.csdnimg.cn/20201025132528893.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0hvc2hpem9sYQ==,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0hvc2hpem9sYQ_size_16_color_FFFFFF_t_70_pic_center 4]: https://img-blog.csdnimg.cn/20201025132832970.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0hvc2hpem9sYQ==,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0hvc2hpem9sYQ_size_16_color_FFFFFF_t_70_pic_center 5]: /images/20221122/b868ba7c962b48bdadccbf322b741b8c.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0hvc2hpem9sYQ_size_16_color_FFFFFF_t_70_pic_center 6]: https://img-blog.csdnimg.cn/20201025170327291.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0hvc2hpem9sYQ==,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0hvc2hpem9sYQ_size_16_color_FFFFFF_t_70_pic_center 7]: /images/20221122/9f25c65d7bfc48be86a47ab5fd71d9e3.png