最长公共子序列问题 动态规划

Longest common sequences(LCS)

abdcd 和 rtdaibicpd的最长公共子序列就是abcd

这个问题如何求解?首先考虑暴力求解的方法,以一个串的第i个字符为基准,在另一个串中找到第一个相同的元素,然后将串截短,递归查找两个串的相同元素,然后直到i遍历完成。

abdcd rtdaibicpd。变成 bdcd ibicpd 中找LCS

递归总是不太友好的,容易联想到这种问题存在最优子结构的性质。 因此可以考虑用动态规划的思想来解决问题。

定义\(dp[i][j]\)表示第一串从第0到第i个字符构成的串可第二个字符从第0个到第j个字符构成的串的LCS长度。

考虑好dp数组边界条件就可以了,解是dp[n][m]。求解顺序是从小到大,时间复杂度在O(nm)量级上。

一种用python的简单实现:

def LCS(a, b):
    n, m = len(a), len(b)
    dp = {}
    for i in range(n + 1):
        dp[i, 0] = 0
    for j in range(n + 1):
        dp[0, j] = 0
    for i in range(1, n + 1):
        for j in range(m + 1):
            if a[i - 1] == b[j - 1]:
                dp[i, j] = dp[i - 1, j - 1] + 1
            else:
                dp[i, j] = max(dp[i -1, j], dp[i, j - 1])
    return dp[n, m]

在自然语言处理中的文本摘要任务中的一个评价指标ROUGH-L中,就用这个算法的应用,也可以在rouge这个python第三方库中rough-l算法的实现方法中看到动态规划方法实现的LCS算法的身影,见下图。

谈插入排序与冒泡排序

这里讨论的主要是关于插入排序和冒泡排序这两种算法的复杂度以及背后的一些思想。

这两种排序算法的实现过程的比较简单,这里就不提了。并且也很容易证明这两种算法的平均时间复杂度和最坏时间复杂度都是\(O(n^2)\)量级的。

这两种算法背后一个思想,就是一次比较之至多能够消除一个逆序对,那么这种算法排序的时间复杂度的下限就是逆序对的数量。什么是逆序对,就是3个数,2,1,3进行排序(升序)时,逆序对有1对,就是2,1这一对,如果是3,2,1,就是有三个逆序对。

很容易想象,当n个数完全逆序的时候,逆序对的数量是最多的n(n-1)/2,这也就对应了最坏的时间复杂度是\(O(n^2)\),而平均情况下,假设各种序列出现的概率相同,平均一个序列的逆序对的个数是n(n-1)/4,因为一个序列和这个序列倒置过后的总共的逆序对是n(n-1)/2,平均下来一人一半。所以一次比较之至多能够消除一个逆序对的算法平均时间复杂度逃脱不了\(O(n^2)\),如果要突破,你只能从算法策略上下手了,比如快速排序一次比较之后交换元素可能会消灭多个逆序对,再比如归并排序,在merge的时候也可能消灭多个逆序对。这两种排序算法就有别与插入和冒泡了,突然想起来选择排序,也是一样的。

从二叉排序树到红黑树

二叉排序树

二叉排序树是一种比较简单的数据结构,即某个节点左边的节点都是比较小的节点,右边的节点都是比较大的节点,并且某一个节点的左右子树都是一颗二叉排序树。利用树的结构特性可以提高查找元素的效率。

但是二叉排序树无法面对一种最坏情况,当树是一颗单支树,这样的树虽然也满足二叉排序树的定义,但是和普通的数组也没有区别了。

所有我们需要一定的策略来保证二叉排序树的结构,提高二叉排序树的查找效率,这就引入了平衡二叉排序树。

平衡二叉树

平衡二叉排序树之于普通的二叉排序树有一个额外的要求就是,任意节点的左右子树的高度之差不能超过1。这样可以避免二叉树成为单支树的最坏情况,还能保证查找某个元素时的时间复杂度基本在\(O(nlogn)\)量级。

但是平衡二叉树也存在一个问题,就是当平衡二叉树的插入和删除操作比较多的时候,维持树平衡时涉及到节点的旋转操作会带来比较大的开销,进而导致这种数据结构的效率降低。因为插入或者删除元素破坏了原来二叉树的结构,可能破坏平衡性条件,因此需要相应的调整措施来保证其符合平衡二叉树的定义。

红黑树

红黑树也是为了避免出现单支树的情况,即为了提高二叉排序树的查找效率。同时也为了改善平衡二叉排序树中的插入和删除操作频繁而导致开销过大的情况。

因此红黑树也有一些规则对二叉排序树的结构进行约束(就像AVL中左右子树高度差不能超过1的约束),首先红黑树定义了一些内容如节点的颜色(红或者黑),外部节点(空树,黑色的),黑边(连向黑色节点的边),黑长度(两个节点中黑边数量),黑高度(任意节点到该节点的黑长度) ,黑深度(根节点到该节点的黑长度),在以上定义下,一颗红黑树要满足如下的约束:

  • 根节点是黑色的
  • 红节点没有红孩子(孩子节点只能是黑色的)
  • 任意一个节点u到外部节点的黑高度相同

可以通过数学证明(证明有空再补上),具有n个节点的红黑树的高度至多为\(2nlog(n+1)\).这样也就是说在红黑树中查找元素的时间复杂度为 \(O(2nlog(n+1)=O(nlogn)\) ,虽然时间复杂度比AVL高,但是数量级和AVL相同。

同时红黑树由于其特殊的约束条件以及对应的元素插入和删除策略,使得调整二叉树结构使其满足约束时的额外开销比较小。因此在实际应用中红黑树的应用很广泛。

红黑树的插入和删除操作策略比较复杂,并且情况也比较多,网上也有很多相应的技术博客进行了介绍,这里简单总结一下,供温习是快速回想起来。

插入元素

  • 插入时插红节点,若插入为根节点则直接改成黑色。
  • 如果父亲节点是黑色,插入成功。
  • 如果父亲节点和叔叔节点都是红色,则父亲叔叔变黑,爷爷变红,并且将爷爷作为新插入节点,向上继续调整。
  • 如果父亲红叔叔黑,则存在一次旋转和两次旋转的问题。

删除元素

  • 删除非叶子节点时,首先将该元素替换成右子树的最小值,然后删除最小值的那个节点。
  • p父亲 s兄弟 l兄弟做孩子 r 兄弟右孩子
  • 分为5种情况(当删除为父亲的左孩子)
    • pslr全黑,s变红,继续向上调整
    • l为红…….
    • p 为红…….
    • r 为红…….
    • s 为红…….
    • 当删除为父亲的右孩子,对称地查看 r p l s

基于比较操作的排序问题的时间复杂度下界

基于比较操作的排序算法的实现过程都可以用一颗二叉树进行描述,其中非叶子节点表示一次比较操作,而比较之后的两种情况就可以用左右子树进行描述,叶子节点表示每种排序的结果。

默认根节点的高度为0,而下面每个节点的高度为根节点的高度加上根节点到该节点的路径长度。

举一个例子,两个元素 \(a,b\) 进行排序,那么只需要一次比较就可以了,所以根节点就是那一次比较操作,左叶子节点就是\(a<b\),右叶子节点就是\(a>=b\)。这棵树的高度为h=1,比较次数也为1

因此排序算法构造出来的排序树的高度,就可以反映出一个排序算法的比较次数。

我们考虑最坏的情况,假设对n个元素进行排序,那么n个元素的排列方式一共有n!种,即对应到排序树种一共有n!个叶子节点,有n!个叶子节点的二叉树的高度至少为\(log_2n!\)(满二叉树/完全二叉树),向上取整。

因为一些劣质的排序算法,可能做了很多无用的比较操作,导致非叶子节点的数量过多,或者叶子节点的数目超过n!,出现重复等,导致排序树的高度远大于 \(log_2n!\) ,那么我们可以说这个排序算法不够好。

证明基于比较操作的排序算法的时间复杂度的下界(最好的情况不能低于这个值)是O(nlogn).

练习题:n=3是画出插入排序和归并排序的排序树,并判断这种情况下对应的排序算法是不是优的

练习题:n=5时,最好的排序算法需要几次比较?并描述这种排序算法的实现过程。

快速排序

快速排序采用了分治的思想,首先选择一个元素作为主元(pivot,通常选择第一个元素),然后将剩下的元素都和该主元进行比较,小的放到主元左侧,大的放到主元右侧,这样一轮之后,主元在中间,左右两侧分别都小于或大于主元,但不一定有序,左右两侧就可以作为子问题迭代求解。

快排是基于比较的排序算法,平均时间复杂度为\(O(n\log n)\),但属于一种不稳定的算法,最坏情况会达到\(O(n^2)\)的时间复杂度。

通常快排对于n比较大的情况会比较好,对于规模比较小的问题直接用插入排序就可以了。

为了避免最坏情况,也可以主元选取的方式上做一些文章。

一般数据结构课程中的快速排序实现方式如下:

python语言的一行快排实现:

一行

def quick_sort(arr):
    if len(arr) < 2: return arr
    else: reutrn quick_sort([item for item in arr[1:] if item <= arr[0]) + \
          arr[0:1] + \
          quick_sort([item for item in arr[1:] if item > arr[0])

一行

quick_sort= lambda x: x if len(x) < 2 else quick_sort([item for item in arr[1:] if item <= arr[0]) + x[0:1] + quick_sort([item for item in arr[1:] if item > arr[0])

或者这样,参考自这篇文章

qsort = lambda arr: len(arr) > 1 and qsort(list(filter(lambda x: x <= arr[0], arr[1:]))) + arr[0:1] + qsort(list(filter(lambda x: x > arr[0], arr[1:]))) or arr

上述代码中涉及的python语法要点包括:lambda 匿名函数,一行if-else语句, 列表推导式,带有过滤的列表推导式,列表切片,函数递归定义,and和or的返回值问题等。当然这样的代码看个有趣就行。

出栈序列的个数问题

当n个元素\(a_1,a_2,\cdots,a_n\)有序进栈,但不约束出栈时机,但是进栈一定按照排好的顺序,问一共有多少个出栈序列。

如何进行计算出栈序列的个数呢?

首先定义一个函数\(f(n)\),表示n个元素有序进栈时,可能的出栈序列个数

那么现在考虑一个问题在n个元素中,假设第i个元素 \( a_i \)是最后出栈的,这种情况下有多少种可能呢?

分析思路1

参考这篇博客

分析:设f(n)为“n个元素以一定的顺序入栈,出栈顺序的种类数”。显然f(1)=1,f(2)=2。我们现在来分析一般情况。一般情况下,我们可以按照“第一个入栈的元素,在出栈序列中的位置”作为分类手段。

举个例子,我们假设入栈元素为A,B,C,D。我们按照“A在出栈序列中的位置”分类讨论:

(1)当A第一个出栈时,A先进,然后马上出栈。这种情况下,共有“BCD出栈顺序的种类数”种方案。也就是f(n-1)。

(2)当A第二个出栈时,A先进,B再进,之后B需要马上出来(这样才能确保A排第二)。此时共有f(n-2)种方案。

(3)当A第三个出栈时,A先进,之后只要确保排在A后面两个的元素比A先出即可。此时共有f(2)*f(1)种方案。f(2)是指“BC入栈出栈顺序的种类数”,f(1)是指”D入栈出栈的种类数”。

分析思路2

按照分析最后出栈元素进行讨论

首先考虑 元素 \( a_i \) 进栈之前, \(a_1,a_2,\cdots,a_{i-1}\) 这些元素肯定都进过栈了,因为进栈是按照指定顺序的。在由于 \( a_i \) 是最后出栈的,而栈是先进后出、后进先出的特定,因此 \( a_i \) 进栈的时候,栈应该是空栈,否则 \( a_i \) 不可能是最后一个出栈,这也意味着 \(a_1,a_2,\cdots,a_{i-1}\) 这些元素在 \( a_i \) 进栈之前都已经出栈了。

总结一下就是当 \( a_i \) 是最后出栈的元素时, \( a_i \) 在进栈之前, \(a_1,a_2,\cdots,a_{i-1}\) 都已经完成了进栈和出栈,这就是一个符合我们函数定义的子问题 \(f(i-1)\)。

再考虑 \( a_i \)之后的元素,由于 \( a_i \) 是最后出栈的元素, \( a_i \) 元素进栈之后就只可能一直待在栈底,那么 \(a_{i+1},a_{i+2},\cdots,a_{n}\) 这些元素在 \( a_i \) 元素进栈之后完成了进栈和出栈的操作,这又是一个子问题f(n-i).

那么这样,当 \( a_i \) 是最后出栈的元素,那么这种前提下的可能出栈序列数目为 \( f(i-1) * f(n-i) \)

所以有 \( f(n)=\sum_{i=1}^n f(i-1) f(n-i) \)

实际这个是卡特兰数,有兴趣可以看看相关资料

令f(0)=f(1)=1这样可以正确进行递归过程

\( f(n)=C_{2n}^{n}-C_{2n}^{n-1}= \frac{ C_{2n}^{n} }{n+1} \)

相关推导可以参见下面的视频

个数是指数量级的。

参考文章:

https://blog.csdn.net/harryhare/article/details/69388827?skintest=skin3-template-test

https://blog.csdn.net/qq_26286193/article/details/80216479

最优二叉搜索树(带有查询失败情况)

最优二叉搜索树(不考虑查找失败的情况)详情见另一篇文章

这里是简单地介绍一些这个问题的解题思路,也是采用动态规划策略,思路也大致相似。

问题定义: 现有n个排好序的数\(a_1,a_2,\cdots,a_n\),并且它们的查找概率分别是 \(p_1,p_2,\cdots,p_n\),查找失败的概率为: \(q_0,q_1,q_2,\cdots,q_n\) 如何构造一颗二叉排序树,使得平均查找次数最少?

首先易知该问题满足最优子结构性质,可以采用动态规划求解,动态数组dp定义通上一篇文章。 定义\(A[i][j]\)表示序列 \(a_{i},a_{i+1},\cdots,a_j\)对应的最优二叉排序树下的最小查询次数。因此原问题就是要求解 \(A[1][n]\)

不同的是分析状态转移方程。

这里需要将查找失败的情况当做与父亲节点同高度的虚拟节点,初始化就比较好分析。当选择某一个节点k作为根节点时,左右子树的所有节点的高度都增加1(包括真实节点和虚拟节点1)。这样额外的开销可以分为三个部分:左子树\(\sum^{k-1}_{x=i}p_x\), \(\sum^{k-1}_{x=i-1}q_x\) ,右子树 \(\sum^{j}_{x=k+1}p_x\), \(\sum^{j}_{x=k}\),根节点 \(p_k\)。

累加起来就是 \(\sum^{j}_{x=i}p_x+\sum^{j}_{x=i-1}q_x\)

那么状态转移方程就是: \(A[i][j]=\mathop{min}_{i\leq k\leq j} \{ A[i][k-1]+A[k+1][j] + \sum^{j}_{x=i}p_x+\sum^{j}_{x=i-1}q_x \}\)

比不考虑查询失败情况下多加了一项而已。

考虑边界和初始化情况,当i>j时,视为空树,代价为0。当i=j时,代价为\(p_i+q_{i-1}+q_i\)符合状态转移方程的定义,因此后续的逻辑就是正确的。

求解过程,自底向上求解,最终求出 \(A[1][n]\)

时间复杂度上界同样是 \(O(n^3)\),空间复杂度 \(O(n^2)\)

练习:

答案:

最优二叉搜索树 动态规划

问题描述:现有n个排好序的数\(a_1,a_2,\cdots,a_n\),并且它们的查找概率分别是 \(p_1,p_2,\cdots,p_n\),如何构造一颗二叉排序树,使得平均查找次数最少?

贪心策略:每次选择查询最大的那个元素作为根节点,然后依次左右子树递归构建下去。但是贪心问题不是最优的,可以举一个反例进行反驳。

最优子结构分析:假设有一颗树是当前问题的一个最优查询树,根节点为 \(a_i\) ,那么根节点连接的两颗子树(两个子问题 \(a_1,a_2,\cdots,a_{i-1}\)和 \(a_{i+1},a_{i+2},\cdots,a_n\) )也应该是对应的最优查询树(平均查找次数最少),否则原来那个树就不是最优的树,产生矛盾。因此该问题存在最优子结构性质。

动态规划策略:

首先定义dp数组,定义\(A[i][j]\)表示序列 \(a_{i},a_{i+1},\cdots,a_j\)对应的最优二叉排序树下的最小查询次数。因此原问题就是要求解 \(A[1][n]\)

下面推导状态转移方程:

根据问题的特性当两个子问题要合并成一个大问题的时候,在子问题的基础开销上,子问题的子树上所有节点的高度都增加1,也就是每个节点的开销都需要加上该节点的访问概率,同时根节点的开销是根节点的访问概率,因此也就是从左子问题的头节点的访问概率累加到右子问题的尾节点的访问概率。因此有下面的转态转移方程:

\(A[i][j]=\mathop{min}_{i\leq k\leq j} \{ A[i][k-1]+A[k+1][j] +\sum^{j}_{x=i}p_x \}\)

初始化条件:,当i=j时,即只有一个元素,只能作为根节点。故此时 \( A[i][i]=p_i\)

边界条件:当i>j是,这种情况不合常理,当时在求解的时候回设计到,为了保障算法的正确运行,将这个值设为0,即没有代价。有了这一步,实际上初始化条件都可以改为将\(A[i][i-1]\)直接设为0,可以结合转态转移方程,并分析自底向上计算过程得到这个结论。

计算顺序:自底向上方法,如果要求最优的二叉排序树的结构,可能该需要一个二维数组记录一下树的结构。

时间复杂度:三层循环,上界为O(n*n*n)

空间复杂度:O(n*n)

练习:

答案

硬币问题(凑零钱) 动态规划

infinity = 9999
def coin_change(coins, a):
    dp = []
    '''初始化过程'''
    dp.append(0)
    min_amount = min(coins)
    for i in range(1, min_amount):
        dp.append(infinity);
    
    '''动态规划自底向上方法计算过程'''
    for i in range(min_amount, a + 1):
        min_count = infinity
        for c_j in coins:
            if i >= c_j and dp[i - c_j] + 1 < min_count:
                min_count = dp[i - c_j] + 1
        dp.append(min_count)
    return dp[a]

时间复杂度分析:求最小硬币面值(\(O(n)\))和初始化dp数组( \( O(1) \) )可以忽略不计,动态规划过程中有两层循环,外层最多执行a次,内层最多执行n次,因此该算法最坏的时间复杂度的 \( O(an) \)

空间复杂度分析 :dp数组所占用的空间为 \(O(a) \)

矩阵连乘

\(A_{n×p}\)和\(B_{p×m}\) 是两个矩阵,这两个矩阵进行相乘的乘法次数为n×p×m。那么考虑一共有N个矩阵进行连续乘法的时候,求最优的乘法次序,使得乘法的次数最少,前提是矩阵乘法满足结合律。

穷举法:所有乘法次序为(N-1)!种,代价太大。

贪心策略:容易观察,矩阵维度 n p p m 变为 n m ,如果p较大的会带来较大的乘法开销,所以我们希望在顺次确定第一步乘法是,贪心地优先消去最大的那个p。

如何确定该贪心策略是否是正确的,举个反例?

。上面是一个反例,这种贪心主要面对当一个最大维度周围是次大或者次次大维度时,造成一步的乘法次数剧增。因此这种贪心策略不满足最优条件。

逆向地思考问题,最优结构的乘法次序总有最后两个矩阵之间进行,可以这两个矩阵将原始矩阵序列划分为,两个子矩阵序列,那么这两个子矩阵序列的乘法序列也应该是最优的,否则与前提矛盾。因此这样思考,矩阵连乘存在最优子结构特性

具有最优子结构特性,那么就动态规划三步走。

最简单的方法,第一步:暴力搜索(通常是用递归来实现),遍历所有的可能,但是对于这个问题,最终的结果是各个步骤的累加,因此在暴力搜素中掺杂了回溯的思想。(自顶向下)

第二步,带有备忘录的暴力搜索,暴力搜索生成树中存在大量的重复子树,可以将已经计算的结果存下来,下次遇到直接取就可以了。 (自顶向下)

第三部,动态规划法(四个步骤) (自底向上)

  • 定义dp数组,这里用cost[i,j],表示矩阵i到矩阵j的最优的乘法次序的代价
  • 写出dp数组包含的最优子结构的递推关系
  • 确定问题的初始条件以及边界条件
  • 自底向上开始计算结果