分治算法(D&C)

• 概述
• • 例题1
  • 例题2
  • 例题3
• 快速排序

分治算法(Divide and Conquer, D&C)，是一种经典的递归式解决问题的方法，分而治之，是其主要思想。
适用场景：
1）找到终止条件（基线条件），停止递归，条件越简单越好；
2）能将问题分解，不断地缩小问题规模，直至满足终止条件。
快速排序是采用分治思想的经典排序算法。
Talk is cheap, show me code.
将通过几个简单的小例子帮助理解，均使用python实现。

求数组之和，例如x = [1, 3, 2, 6, 5,7, 7, 9, 0, 0, 8], sum(x)=48 

首先，考虑能不能缩小问题规模，数组x包含多个元素，求和操作是一个累加操作，始终是两个元素进行相加，那么整个数组可以分解成多次的两个元素相加，此时问题的最小规模即为两个元素相加；
然后，考虑终止条件，数组x除了包含多个元素外，可能是空数组，也可能包含一个元素，如果是空数组，和为0，包含一个元素的数组，和为x[0]。

def dc_sum(num_list):
	if len(num_list) == 0:  # 终止条件
	    return 0
	elif len(num_list) == 1: # 终止条件
	    return num_list[0]
	else:
	    return num_list[0] + dc_sum(num_list[1:]) # 缩小问题规模

求数组最大值，例如x = [1, 3, 2, 6, 5,7, 7, 9, 0, 0, 8], max(x)=9

和求和类似，求最大值可以分解成始终是两个元素之间的比较，终止条件一样。

def dc_max(num_list):
	if len(num_list) == 0:  # 终止条件
	    return 0
	elif len(num_list) == 1: # 终止条件
	    return num_list[0]
	else:
		# 缩小问题规模
		tmp1 = num_list[0]
		tmp2 = dc_max(num_list[1:])
		if tmp1 > tmp2
			return tmp1
		else:
			return tmp2

有一块土地需要均匀的划分成方块，要求划分的方块要尽可能的大，求最大的方块边长，土地如下所示：

题目要求是方块，且尽可能的大，所以下图所示划分是不合理的：

设想一块土地是25x25的，那么符合条件的就是25x25的这样一个划分，如果是50x25呢，符合条件的就是划分出两个25x25的区域，也就是说，尽可能找到一个长宽能够整除的方块，这样才能保证划分的方块尽可能的最大。
但题目给的土地宽高并不能整除，怎么办呢？
可以先从土地中划分出两个640x640的区域，同时余下一块土地，对余下的这块土地采用相同的方式，划分出以最短边为方块的土地，然后再次余下一块土地，循环此操作，直到找到一个长宽能够整除的土地。

def dc_land_split(height, width):
	max_len = max(height, width)
	min_len = min(height, width)
	if max_len%min_len == 0: # 终止条件
		return min_len
	else:
		# 缩小问题规模
	    return dc_land_split(max_len%min_len, min_len) 

快速排序算法是经典的排序算法之一，其平均运行时间为 O ( n l o g n ) O(nlogn) O(nlogn)，最坏情况为 O ( n 2 ) O(n^2) O(n2)。
步骤：
1）选择一个基准值（pivot）;
2) 将数组中其余的元素分成两个数组，小于pivot的放在一个数组，大于pivot的放在另一个数组，与pivot相等的放在其中任意一个数组，这样pivot就处于原始数组的中间位置。
3）重复2）操作，将两个数组分别进行排序。

上述步骤2）其实就是一个缩小规模的过程，逐渐的将原始数组进行不断分解成多个小数组，在分解的过程中实现了排序。
其终止条件即为数组中元素个数小于2个。

def quick_sort(num_list):
	if len(num_list) < 2:
		return num_list
	
	# pivot = num_list[0]
	pivot = num_list[len(num_list)//2]
	num_list.pop(len(num_list)//2)
	less = []
	greater = []
	for i in num_list:
		if i < pivot:
			less.append(i)
		else:
			greater.append(i)
	less = quick_sort(less)
	greater = quick_sort(greater)
	return less + [pivot] + greater

在取pivot时，如果去首元素作为基准值，那么最糟的情况即为对已经排序后的数组进行快排操作，那么始终有一子数组为空数组，此时其调用栈为 O ( n ) O(n) O(n)，运行时间为 O ( n 2 ) O(n^2) O(n2)，若取数组中间元素，其调用栈为 O ( l o g n ) O(logn) O(logn)，运行时间 O ( n l o g n ) O(nlogn) O(nlogn)。