基于HashTable的动态规划编辑距离算法复杂度验证及影响问询

先直接给你结论：你认为这个算法时间复杂度是O(logn)的结论不正确，接下来咱们一步步拆解原因，以及HashTable在这里扮演的角色。

1. 算法本质：带记忆化的Levenshtein编辑距离 #

这段代码实现的是带记忆化（Memoization）的Levenshtein编辑距离——核心逻辑是通过递归将原问题拆解成更小的子问题（比如比较两个字符串的首字符后，递归处理剩余子串），并用HashTable缓存已经计算过的子问题结果，避免重复计算。

2. 时间复杂度的正确推导 #

无记忆化的情况（去掉HashTable） #

如果没有HashTable的缓存逻辑，这个递归算法的时间复杂度是O(3^max(m,n))：因为每一步递归最多会产生3个分支（删除操作、插入操作、无操作），随着字符串长度增加，计算量会呈指数级爆炸，完全无法处理稍长的字符串。

有记忆化的情况（当前代码） #

有了HashTable的缓存后，每个不同的子问题（即不同的<s1子串, s2子串>组合）只会被计算一次。假设s1的长度为m，s2的长度为n，那么所有可能的子问题总数是**(m+1)*(n+1)**——因为s1可以取从长度0到m的所有剩余子串，s2同理，两者的组合数就是二维的规模。

每个子问题的处理中，HashTable的containsKey、get、put操作平均时间复杂度为O(1)（理想哈希函数下无冲突），所以整体时间复杂度是O(m*n)，这和你认为的O(logn)完全不同——O(logn)一般是二分查找这类每次将问题规模减半的算法的复杂度，而这里的子问题是二维乘积级的，和logn没有关系。

3. HashTable对复杂度的核心影响 #

HashTable在这里是决定性的优化手段：

• 它直接将算法的时间复杂度从指数级降到了多项式级（O(mn)），避免了大量重复计算；
• 从细节来看，如果Pair类的哈希函数实现不合理（比如所有键都哈希到同一个桶），HashTable的操作会退化成O(k)（k为哈希表元素数，即O(mn)），此时整体复杂度会变成O((mn)^2)，但这种极端情况在实际中很少见；
• 另外，如果你用Java的HashMap替代HashTable，本质时间复杂度不会变化——只是HashTable是线程安全的，会有轻微的同步开销，但复杂度量级一致。

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