先将问题实例分解成若干个子问题,然后递归解决这些子问题,并将结果合并。

以子问题为节点,并且以它们之间的依赖关系为边构建一个子问题图,比如树,每个子问题都会依赖于一个或者多个别的子问题,而这些问题本身又都可以被独立解决,只要能够利用这种相对简单的结构找出合适的归简方案,就可以利用递归公式来解决问题了。

弱归纳法中,通常问题会被分解成:n-1和1,如果归纳步骤是一个线性级,那么递推公式就是T(n) = T(n-1) + T(1) + n,这样两个递归调用就是不平衡的,时间复杂度也是n2。推导见算法数学思维。但是如果两个子问题是同等规模的,也就是平衡的话,递归式会转换成T(n)=2T(n/2)+n,这就是分治递归式。时间复杂度是Θ(nlgn)。

经典分治算法

输入一个元素集合,这些元素会被对半分成两个规模大致相同的集合,然后算法会在这两半元素持续递归下去,并最终合并出结果。

下面是一个分治的通用函数

1
2
3
4
5
6
def divide_and_conquer(S, divide, combine):
if len(S) == 1: return S
trueL, R = divide(S)
trueA = divide_and_conquer(L, divide, combine)
trueB = divide_and_conquer(R, divide, combine)
truereturn combine(A,B)

有些算法侧重于分解,如快速排序,有些算法侧重于归并,如归并排序。

折半搜索

一个递归版本的折半搜索

1
2
3
4
5
6
7
8
9
10
def bisect_rec(s, x, lo, hi):
if lo > hi:
true return
mid = (hi + lo) // 2
trueif x == s[mid]:
true return mid
trueelif x > s[mid]:
true return bisect_rec(s, x, mid+1, hi)
trueelse:
true return bisect_rec(s, x, lo, mid)

迭代版

1
2
3
4
5
6
7
8
def bisect_iter(a, x, lo=0, hi=None):
if hi is None:
true hi = len(a)
truewhile lo < hi:
true mid = (lo+hi)//2
truetrueif x < a[mid]: hi = mid
truetrueelse: lo = mid+1
truereturn lo

搜索树的遍历及其剪枝

在链表中无法实现二分搜索,但是在数组无法实现常数级的插入操作。所以需要一种有利于高效搜索的可修改结构。

其实就是实现一个二叉搜索树,然后在遍历的时候在某个节点上实现了二分法,相当于剪枝。当查找操作从根节点上开始时,要做的就是将两个子树中的一个剪掉,如果在某个内部节点找到了目标值,树上不存在重复的话,该节点的两个子树都可以被剪掉。

一个二分搜索树:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Tree:
root = None
truedef __setitem__(self, key, val):
true self.root = insert(self.root, key, val)
truedef __getitem(self, key):
true return search(self.root, key)
truedef __contains__(self, key):
true try:
truetrue search(self.root, key)
truetrueexcept KeyError:
truetrue return False
truetruereturn True
# 节点
class Node:
lft = None
truergt = None
truedef __init__(self, key, val):
true self.key = key
truetrueself.val = val

插入的时候伴随着剪枝

1
2
3
4
5
6
7
8
9
10
def insert(node, key, val):
if node is None:
true return Node(key, val)
trueif node.key == key:
true node.val = val
trueelif key < node.key:
true node.lft = insert(node.left, key, val)
trueelse:
true node.rgt = insert(node.rgt, key, val)
truereturn node

遍历搜索:

1
2
3
4
5
6
7
8
def search(node, key):
if node is None: raise KeyError
if node.key == key:
true return node.val
trueelif key < node.key:
true return search(node.lft, key)
trueelse:
true return search(node.rgt, key)

在有序数组中,二分搜索速度很快,但是依赖于排序,并且在数组中添加元素是线性操作。搜索树开销会更大,但是由于动态性,插入和移除元素很方便。两者都是对数级时间。

选取算法

该算法可以在线性时间内找到一个无序序列中第k大的数。在Python中,如果要在一个可迭代容器中查找k个值最小的对象。当k相比总数很小的时候,可以使用heapq模块中的nsmallest函数。当比较大的时候,使用排序然后再选取k个元素。

递归调用T(n)=T(n/2)+n的时间复杂度是线性级别的,所以需要用某种线性操作将问题一分为2,所有要找的对象在某一半中。一种简单的分割方式是找出这些值中的分割点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def partition(seq):
pi, seq = seq[0], seq[1:]
truelo = [x for x in seq if x <= pi]
truehi = [x for x in seq if x > pi]
truereturn lo, pi, hi
def select(seq, k):
lo, pi, hi = partition(seq)
truem = len(lo)
trueif m == k:
true return pi
trueelif m < k:
true # 在大的部分选择剩下的元素,减1是因为pi
true return select(hi, k-m-1)
trueelse:
true # 在小的值中选择k
true return select(lo, k)

折半排序

  • 快速排序

快速选取法所代表的是剪枝式的遍历操作,在递归树中找出一条通往第k小元素的路径,快速排序法就是一个完全遍历操作。会对每个k提出一个解决方案,找出序列最小的元素等。然后把元素放到合适的位置上。

1
2
3
4
5
def quicksort(seq):
if len(seq) <= 1:
true return seq
truelo, pi, hi = partition(seq)
truereturn partition(lo) + [pi] + partition(hi)

体会一下,便可以明显感觉到快速排序的侧重点在于分解问题, 从一个整体序列分解成部分有序,直到相当于叶子节点,每个叶子节点都有序,那么整体就是有序的。快速排序算法在平均情况下是一个线性对数级算法,在最坏情况下是一个平方级算法。

  • 归并排序

其算法核心就是首先分解整体,直到最底层,然后对左右进行排序合并,这里就是相对有序的,然后把相对有序的子序列合并。回溯到整体,整体就是有序的了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
def mergesort(seq):
# 先分解
truemid = len(seq) // 2
true# 左右序列
lft, rgt = seq[:mid], seq[mid:]
true# 分解,直到分解序列只有一个元素
trueif len(lft)>1: lft = mergesort(lft)
trueif len(rgt)>1: rgt = mergesort(rgt)
trueres = []
true# 合并,其lft和rgt应该是有序的
truewhile lft and rgt:
true if lft[-1] >= rgt[-1]:
true res.append(lft.pop())
truetrueelse:
truetrue res.append(rgt.pop())
trueres.reverse()
truereturn (lft or rgt) + res

list.sort()使用的是Timsort,归并排序的改进版,它会在开始阶段查找该数组哪些已经处于有序状态的分区。然后在后面合并这些run。

对于排序,归并排序这种分治算法已经处于最优状态了,最坏情况下至少要消耗nlgn的时间。

树的平衡与再平衡

大多数搜索树结构都有再平衡的形式,是一组用于重组树结构,确保其平衡状态的操作。各种树结构及其再平衡方法基本是以下:

  • 节点的分割和合并,节点可以拥有两个以上的子节点和一个以上的键,在某些情况下,一个节点可能出现溢出,这时候就可以被分割成两个节点,这样也有可能使得父节点溢出,递归
  • 节点的翻转,会对边进行切换,如果x是y的父节点,现在就要让y成为x的父节点,x还必须接管y的另外一个子节点。

2-3树是B树的一种特殊情况,B树是几乎所有数据库,以及基于磁盘的树形系统的基石。B树结构可以拥有上千个键和子树,每个节点通常会在磁盘上被存储为一个连续的块。使用大块存储主要是为了减少访问磁盘的次数。

2-3树中,插入节点的话需要往叶节点内添加新的值,节点还有空间的话,就直接将值添加进去,没有的话,就是三个键了,这时候就要溢出了。方法是分割节点,将中间值向上移到父节点中。如果父节点也溢出,递归,最后树就是完全平衡。

  • AA树

是二叉树,但是模拟了三节点型的平衡法。两个节点连接在一起模拟单一的伪节点。并且树上的每个节点都会被分配层次,叶节点的层次是1。并且三节点型内部边线只可以指向右边。也就是右边节点大于左边节点,反正类似于2-3树吧。如果是非法节点,则必须翻转一下。因为其实还是二叉树,而且左侧节点的右指针只能指向内部的那个节点。原来的那个右子树就应该挂到右边节点的左边去。这种操作就是偏斜。

还有一个情况,就是溢出,应该要分割。把中间的元素移动到父节点上去。形成一个2个键的内部节点。然后将中间元素的节点的左子树挂靠在左侧节点的右部。然后中间节点左右分别挂靠的是之前要溢出的节点的左节点和右节点。

AA树中插入节点与二叉树结构中基本相同,后期要进行清理,对每个节点进行检测,应用偏斜和分割。

节点:

1
2
3
4
5
6
7
class Node:
lft = None
truergt = None
truelvl = 1
truedef __init__(self, key, val):
true self.key = key
truetrueself.val = val

偏斜即翻转操作

1
2
3
4
5
6
7
8
9
10
11
12
def skew(node):
# 如果都没有左侧节点,说明不需要偏斜
if None in [node, node.left]: return node
true# 左侧节点的level和现在节点不一样,说明不是一个内部节点
trueif node.lft.lvl != node.lvl: return node
true# 剩余情况就是既有左侧节点,而且level还一样
true# 过程参考想象2-3树
truelft = node.lft
truenode.lft = lft.rgt
truelft.rgt = node
true# 将真正的节点返回给父节点进行索引
truereturn lft

分割操作,溢出

1
2
3
4
5
6
7
8
9
10
11
def split(node):
# 说明没有溢出的节点
if None in [node.rgt, node.rgt.rgt, node]: return node
trueif node.rgt.rgt.lvl != node.lvl: return node
true# 溢出操作,想象2-3节点
truergt = node.rgt
truenode.rgt = rgt.lft
truergt.lft = node
true# 将level上升,即上升到父节点
truergt.lvl += 1
truereturn rgt

插入操作,普通的二叉树剪枝操作加偏斜和溢出

1
2
3
4
5
6
7
8
9
10
11
12
def insert(node, key, val):
if node is None: return Node(key, val)
trueif node.key == key: node.val = val
trueelif key < node.key:
true node.lft = insert(node.lft, key, val)
trueelse:
true node.rgt = insert(node.rgt, key, val)
true# 插入完成之后,对每一个节点进行偏斜和溢出(分割)操作
true# 返回正确的node
truenode = skew(node)
truenode = split(node)
truereturn node

二分堆结构与heapq,heapsort

优先级队列每个元素都会有优先级,总是会获取到剩余元素优先级最低的那一个。优先级队列数据结构是许多算法的重要组成,如Prim最小生成树算法,Dijkstra最短路径搜索算法。实现就是二分堆。

二分堆是一个二叉树结构,会始终保持平衡。除了底层可能不满,每一层都是满的,而且会从左边开始填满最底层。堆树形规定每个父节点的值都要小于子节点,那么根节点就是最小的。维持平衡方面,只需要根据堆属性对父节点和子节点进行交换即可,并且递归。

heapq实现了堆结构,list实现,并且a[i]的子节点是a[2*i+1]a[2*i+2]两个位置,根节点始终位于a[0]。heappush()和heappop()来创建堆,或者使用heapify()函数。

堆排序:首先创建最大值堆,使用heapify操作,然后使用heappop()操作弹出。整体是线性对数级的。

分治法,将大问题分解,然后解决这些小问题,递归法,然后合并。主要基础是工作量的平衡性。可以将一个平方级的问题将为线性级。