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

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的时候也可能消灭多个逆序对。这两种排序算法就有别与插入和冒泡了,突然想起来选择排序,也是一样的。