因为问题小到一定规模可以更好解决，将一个问题分解若干个相同问题，再利用分解出若干子问题的解可以合并为该问题的解：
该问题所分解出的各个子问题都是相互独立。
1.因计算复杂性，伴随问题规模的增加而增加。通过分治法将分成若干子问题，使绝大多数问题都可以满足。
2.当绝大多数问题得以解决，这也体现递归思想。
3.如果不具备前2条特征，可以通过贪心法或动态规划法。
4.如果各个子问题是不独立则分治要做许多其他工作，重复地解决公共子问题，此时虽然可以分治，但一般用动态规范比较稳妥。
列表快排,时间复杂度O(nlogn)
def partition(lst):
# 挑选节点
pivot = lst[0]
# 所有小于pivot
low = [x for x in lst[1:] if x < pivot]
# 所有大于等于pivot
hight = [x for x in lst[1:] if x >= pivot]
return low,pivot,hight
def quick_sort(lst):
if len(lst) <= 1:
# 出口
return lst
# 分解
low, pivot, hight = partition(lst)
# 递归: 分治，再合并
return quick_sort(low) + [pivot,] + quick_sort(hight)
lst = [5,6,3,1,9,4,0,8,7,2]
result = quick_sort(lst)
print(result)
# [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
对数组进行归并排序，时间复杂度O(logn)
def merge(lst):
mid = len(lst) // 2
# 取mid 左右两个数组
left,right = lst[:mid], lst[mid:]
# 递归分治
if len(left) > 1:
left = merge(left)
if len(right) > 1:
right = merge(right)
# 合并操作
result = []
# 这里判断两个列表都不为空
print(left, right)
while left and right:
if left[-1] >= right[-1]:
result.append(left.pop())
else:
result.append(right.pop())
print("---->", result)
result.reverse()
# 添加left或right不为空的列表
return (left or right) + result
lst = [5,6,3,1,9,4,0,8,7,2]
print(merge(lst))
"""
[5] [6]
----> [6]
[1] [9]
----> [9]
[3] [1, 9]
----> [9]
----> [9, 3]
[5, 6] [1, 3, 9]
----> [9]
----> [9, 6]
----> [9, 6, 5]
[4] [0]
----> [4]
[7] [2]
----> [7]
[8] [2, 7]
----> [8]
[0, 4] [2, 7, 8]
----> [8]
----> [8, 7]
----> [8, 7, 4]
----> [8, 7, 4, 2]
[1, 3, 5, 6, 9] [0, 2, 4, 7, 8]
----> [9]
----> [9, 8]
----> [9, 8, 7]
----> [9, 8, 7, 6]
----> [9, 8, 7, 6, 5]
----> [9, 8, 7, 6, 5, 4]
----> [9, 8, 7, 6, 5, 4, 3]
----> [9, 8, 7, 6, 5, 4, 3, 2]
----> [9, 8, 7, 6, 5, 4, 3, 2, 1]
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
"""
利用分治法。给定一个顺序列表，求出最大值。时间负责度O(nlogn),这里分治用于用于比较数组长度小于等于2的情况。
def max_num(lst):
return max(lst)
def solve(lst):
n = len(lst)
# 分治
# 长度小于等于2，取最大
if n <= 2:
return max_num(lst)
# 分解
left, right = lst[:n//2], lst[n//2:]
# 递归 分治
left_max,right_max = solve(left),solve(right)
return max_num([left_max,right_max])
lst = [5,6,3,1,9,4,0,8,7,2]
print(solve(lst))
# 9
给定一个列表，判断某个元素是否在其中，时间复杂度O(nlogn)
def in_lst(lst,key):
if lst[0] == key:
return True
else:
return False
def solve(lst, key):
n = len(lst)
# 当列表长度为1情况
if n == 1:
return in_lst(lst,key)
# 分解
left, right = lst[:n//2], lst[n//2:]
result = solve(left,key) or solve(right,key)
if result:
return "OK"
return None
lst = [5,6,3,1,9,4,0,8,7,2]
key = 10
print(solve(lst,key))
得到一组列表中第4小的元素，要求线性时间，时间复杂度O(nlogn)
def partition(lst):
# 挑选节点
pivot = lst[0]
# 所有小于pivot
low = [x for x in lst[1:] if x < pivot]
# 所有大于等于pivot
hight = [x for x in lst[1:] if x >= pivot]
return low,pivot,hight
def solve(lst,key):
# 分解
low, pivot, hight = partition(lst)
n = len(low)
# 解决
if n == key:
return pivot
# 递归分治
elif n < key:
# 在hight那一部分
return solve(hight,key-n-1)
# 递归分治
else:
# 在low那一部分
return solve(low, key)
lst = [5,6,3,1,9,4,0,8,7,2]
key = 4
result = solve(lst, key)
print(result)
# 4
原文：https://www.cnblogs.com/xujunkai/p/12555513.html