分治法及其python实现例子

在前面的排序算法学习中,归并排序和快速排序就是用的分治法,分治法作为三大算法之一的,有非常多的应用例子。

分治法概念

  1. 将一个复杂的问题分成两个或更多的相同或相似的子问题,再把子问题分成更小的子问题----“分”
  2. 将最后子问题可以简单的直接求解----“治”
  3. 将所有子问题的解合并起来就是原问题打得解----“合”

分治法特征

  1. 该问题的规模缩小到一定的程度就可以容易地解决
  2. 该问题可以分解为若干个规模较小的相同问题,即该问题具有最优子结构性质。
  3. 利用该问题分解出的子问题的解可以合并为该问题的解;
  4. 该问题所分解出的各个子问题是相互独立的,即子问题之间不包含公共的子子问题。

第一条特征是绝大多数问题都可以满足的,因为问题的计算复杂性一般是随着问题规模的增加而增加;

第二条特征是应用分治法的前提它也是大多数问题可以满足的,此特征反映了递归思想的应用;、

第三条特征是关键,能否利用分治法完全取决于问题是否具有第三条特征,如果具备了第一条和第二条特征,而不具备第三条特征,则可以考虑用贪心法或动态规划法。

第四条特征涉及到分治法的效率,如果各子问题是不独立的则分治法要做许多不必要的工作,重复地解公共的子问题,此时虽然可用分治法,但一般用动态规划法较好。

分治法例子:

一、对数组进行快速排序

'''
时间复杂度O(nlogn)
pivot枢纽,low和high为起点终点
'''
#划分分区(非就地划分)
def partition(nums=list):
pivot = nums[0] #挑选枢纽
lo = [x for x in nums[1:] if x < pivot] #所有小于pivot的元素
hi = [x for x in nums[1:] if x >= pivot] #所有大于pivot的元素
return lo,pivot,hi #快速排序
def quick_sort(nums=list):
#被分解的Nums小于1则解决了
if len(nums) <= 1:
return nums #分解
lo,pivot,hi = partition(nums) # 递归(树),分治,合并
return quick_sort(lo) + [pivot] + quick_sort(hi) lis = [7, 5, 0, 6, 3, 4, 1, 9, 8, 2]
print(quick_sort(lis)) #[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

二、对数组进行归并排序

'''
名字很多:归并排序/合并排序/二分排序
时间复杂度 O(logn)
递归
两个步骤:1.拆分 2.合并
'''
def merge_sort(nums=list):
#取mid以及左右两个数组
mid = len(nums)//2
left_nums,right_nums = nums[:mid],nums[mid:] #递归分治
if len(left_nums) > 1:
left_nums = merge_sort(left_nums)
if len(right_nums) > 1:
right_nums = merge_sort(right_nums) #合并
res = []
while left_nums and right_nums: #两个都不为空的时候
if left_nums[-1] >= right_nums[-1]: #尾部较大者
res.append(left_nums.pop())
else:
res.append(right_nums.pop())
res.reverse() #倒序
return (left_nums or right_nums) + res #前面加上剩下的非空nums lis = [7, 5, 0, 6, 3, 4, 1, 9, 8, 2]
print(merge_sort(lis)) #[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

三、给定一个顺序表,编写一个求出其最大值的分治算法

#O(nlogn)
#基本子算法(内置算法)
#虽然也可以处理大数组,这里用于解决分治问题规模小于2时候
def get_max(nums=list):
return max(nums) #分治法
def solve(nums):
n = len(nums)
if n <= 2: #分治问题规模小于2时解决
return get_max(nums) # 分解(子问题规模为 n/2)
left_list, right_list = nums[:n//2], nums[n//2:] # 递归(树),分治
left_max, right_max = solve(left_list), solve(right_list) # 合并
return get_max([left_max, right_max]) if __name__ == "__main__":
# 测试数据
alist = [12,2,23,45,67,3,2,4,45,63,24,23]
# 求最大值
print(solve(alist)) #

四、给定一个顺序表,判断某个元素是否在其中

#O(nlogn)
#子问题算法(子问题规模为1)
def is_in_list(nums,key):
if nums[0] == key:
print('Yes! %d in the nums' % key)
else:
print('Not found')
#分治法
def solve(nums,key):
n = len(nums)
#N==1时解决问题
if n == 1:
return is_in_list(nums,key)
#分解
left_list,right_list = nums[:n//2],nums[n//2:]
#递归(树),分治,合并
res = solve(left_list,key) or solve(right_list,key) return res if __name__ == '__main__':
#测试
lis = [12,2,23,45,67,3,2,4,45,63,24,23]
#查找
print(solve(lis,45)) #YES~
print(solve(lis,5)) #NOT~

五、找出一组序列中的第 k 小的元素,要求线性时间

'''
O(nlogn)
用快排的方法,选定pivot然后通过左右两个分组递归得出结果
'''
# 划分
def partition(nums=list):
pi = nums[0]
lo = [x for x in nums[1:] if x < pi]
hi = [x for x in nums[1:] if x >= pi]
return lo,pi,hi # 查找第 k 小的元素
def solve(nums,key):
#分解
lo,pi,hi = partition(nums) n = len(lo)
#解决
if n == key:
return pi
#递归分治
elif n < key:
return solve(hi,key-n-1)
#递归分治
else:
return solve(lo,key) if __name__ == '__main__':
lis = [3, 4, 1, 6, 3, 7, 9, 13, 93, 0, 100, 1, 2, 2, 3, 3, 2]
print(solve(lis,3))#
print(solve(lis,10))#

学习资源来自:分治法的个人理解分治算法分析python实现分治法的几个例子

上一篇:下拉列表控件实例 ComboBoxControl


下一篇:iOS 10 SceneKit 新特性 – SceneKit 制作 3D 场景框架