本文参考UCAS卜东波老师算法设计与分析课程撰写

前言

这个标题说实话有点长，本文主要想借上文的例子来说明在实际应用问题中通过对考虑对象的筛选将问题讨论范围压缩，使得计算的冗余点突出出来，再以此入手，降低算法时间复杂度。

在前文算法设计与分析：动态规划（3）-序列联配问题（以算代存）中，我们已经利用分治思想，将原本需要$O(mn)$O(mn)空间复杂度的动态规划问题转换成只需要$O(m+n)$O(m+n)，进一步地，在本文中，我们考虑能否将时间复杂度也降低。
最终实现的结果是将$O(mn)$O(mn)的时间复杂度降低到$O(\alpha \max\{m,n\})$O(αmax{m,n})。

降低对齐时间复杂度

问题再分析

我们先考虑一个问题，假设给我们的两个需要对齐的字符串本身就很不相似（例如“hello”，“father”），我们是否还有必要用动态规划的方式对其计算相似度？设计动态规划对齐两个字符串的目的（我们从应用出发），如修正用户的错误输入，对比文章是否抄袭，这些都建立在两者较为相似的情况下（这个较为相似的标准由使用者制定）。因此，我们可以对那些很多字符对不上的字符串做一个预处理，直接在这个阶段将其淘汰，而相似度较高的两个字符串体现在动态规划中有什么特点？

我们不妨看下面一个图

其中，箭头表示该结果由指向的数字计算而来，红色箭头表示了回溯得到的对齐路径。我用橙色区域标出的部分实际上是可避免计算部分。

为什么橙色可避免计算？先要理解箭头的方向意味着什么。

• 向上的箭头：S用空格与T中字符对齐
• 向左的箭头：T用空格与S中字符对齐
• 斜向上的箭头：S与T中字符与字符对齐（可能相等&不等）

可以发现-30根本不会影响到最终路径的结果，由于我们做了预处理，可以保证最终的路径应该不会离对角线太远（即在对角线附近）。因此，我们真正需要考虑的部分是对角线附近的区域。

解决思路

我们通过设置一个参数$\alpha$α在原数组上开出一个条带，如下图：

反映在原动态数组中即如下：

空白的区域表示我们没有进行计算

我们发现蓝色区域的数字在计算结果的时候其左上角的三个数缺了一个，但是这个并不会影响其结果（因为它根本不会是从缺少的那个格子通过一个加分变化得来），因此我们直接将对应的橙色格子赋$-\infty$−∞，最终我们依然能得到路径结果。

伪代码对比实现

有了上面的思路之后，我们思考原来这部分的伪代码

采用双重for循环，将每一个格子的结果计算出来，计算了太多不必要的格子。
新的伪代码可以设计如下：

这里说明一下，根据上文给出的例子中，我们初始化的两行，只需分别初始化到-9和-6即可，而在for循环中，我们对有限的数组对（i,j）进行计算，而计算(i,j)考虑三个格子，分别是左(L)、上(U)、斜，我们需要判断L，U是否在条带内（即其是否有值），如果其在条带内，计算结果不变，否则，将对应部分赋值为负无穷。

那么这样子计算复杂度降为多少呢？影响复杂度的就是要进行计算的格子数。似乎不好直接计算，我们在原图上做一个扩展，你就明白了，如下：

将图中不足条带$\alpha$α长度的部分补足，可以发现总的计算格子数量不大于$\alpha \max\{m,n\}$αmax{m,n}
新的时间复杂度是$O(\alpha \max\{m,n\})$O(αmax{m,n})

总结

通常我们降低算法运行时间复杂度办法是减少冗余计算（不必要计算），而在之前的动态规划问题中，看似所有的值都是有必要进行计算的，因为后续的值需要依靠前面多个值进行加分求最大得来。但我们结合了实际案例（错词修改，抄袭比对），发现我们真正要考虑的是那些可能引起混淆（相似度较高）的情况，对于一些差异较大的，我们直接在预处理部分就可以淘汰。因此我们发现这类结果路径通常位于对角线附近，这就发现了，其实侧边的结果实际上是冗余计算。为了避免，设计了步骤如下：

1. 将可能区域用条带包裹起来，这个条带的表现就是参数$\alpha$α
2. 对数组对重新定义计算方式$（BANDED-DP(T,S,\alpha)）$（BANDED−DP(T,S,α)），多考虑了一层其是否在条带内的因素，这里减少了冗余计算。

从这个案例也可以看出，为了减少实际使用过程的时间复杂度，我们可以通过结合应用将所有可能案例进行拆分，对于明显不成立的情况，可以在预处理阶段进行筛除，为后续降低时间复杂度提供基础。

如果你觉得文章对你有用，不妨顺手点个赞哦～

• 上一篇：算法设计与分析：动态规划（3）-序列联配问题（以算代存）
• 下一篇：to be continue>>>
• 目录