设计思想之分治

发表于 更新于
分治法的思想是分而治之，这个技巧是很多高效算法的基础。

什么是分治

分治法的思想是分而治之，就是把一个复杂问题分成两个或更多相同或相似的子问题，再把子问题分成更小的子问题……直到最后子问题可以简单的直接求解，将最后子问题的解合并得到原问题的解。因为问题小到一定规模可以更好解决，将一个问题分解若干个相同问题，再利用分解出若干子问题的解可以合并为该问题的解。这个技巧是很多高效算法的基础。

应用分治的示例

找出列表中最大值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
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))

给定一个列表，判断某个元素是否在其中

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
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))