编辑距离的最坏时间复杂度计算问题问询

本次测算完全匹配你提出的场景约束，基于无额外剪枝的通用动态规划编辑距离实现（Needleman-Wunsch全局对齐）完成计算，无多余假设：

分层复杂度推导 #

• 单组单词对的最坏时间复杂度：O(MAX_LEN²)
  当两个长度为MAX_LEN的单词无任何可触发提前中断的公共匹配特征时，算法需要完整填充尺寸为(MAX_LEN+1) × (MAX_LEN+1)的DP状态矩阵，每个矩阵单元仅需常量时间的转移运算，不存在可跳过的计算分支。
• 全量配对场景的总最坏时间复杂度：O(T * D * MAX_LEN²)
  由于需要完成T个测试单词与D个词典单词的全量两两计算，总复杂度为单组计算复杂度乘以总配对数T*D。

最坏情况的触发条件 #

当测试词与词典词的字符集完全无交集（例如测试词全部为MAX_LEN长度的连续'a'组成的字符串，词典词全部为MAX_LEN长度的连续'b'组成的字符串）时，算法无任何剪枝空间，必须遍历完整个DP矩阵才能输出最终结果，此时运行开销达到上述复杂度的上界。

工程实现提示：如果在计算中引入阈值剪枝、公共前后缀裁剪等优化手段，实际运行开销会远低于上述上界，但该测算值是无优化场景下的严格最坏复杂度上限。

内容的提问来源于stack exchange，提问作者blurred42