为何第二款判断Levenshtein距离为2的Haskell代码时间复杂度为指数级？

核心问题原因 #

你的第二个版本出现指数级时间复杂度，核心是截断逻辑的执行时机完全搞反了，同时缺失了递归入口的分支限制，具体可以拆解为两点：

1. min nat3无法提前终止递归
   你把min nat3放到了递归调用的外层，意味着执行逻辑是：先完整执行go的递归调用算出编辑距离，再把结果和3取最小值。等你执行min的时候，递归分支已经全部展开完成，指数爆炸已经发生，此时的截断完全没有意义。
   你单独测试的短路逻辑有效，是因为测试用例里min的第一个参数已经可以确定结果，不需要求值第二个参数，但在你的算法场景中，minimum需要把三个go调用的结果都求值到可以比较大小的程度，每个go调用遇到不匹配字符又会生成三个新的递归分支，没有任何限制，分支数自然会随着不匹配字符的数量指数级增长。
2. 缺失递归入口的分支限制
   第一个版本能做到线性时间的核心，是go函数携带了当前已编辑次数total，在进入分支前就做了total < 2的判断，超过阈值就直接返回结果，不会生成分支，全程总分支数被限制在常数级，每个字符只会被扫描常数次。
   而第二个版本的go函数完全没有入口处的限制，不管已经累积了多少次编辑，只要遇到不匹配的字符，就会直接生成三个新的递归分支，最终的分支数会是O(3^k)，k是两个字符串的不匹配位置数量，自然就是指数级复杂度。

你的理解误区 #

你误以为对返回结果做min nat3就可以反向截断递归的执行，但Haskell的懒求值只会在确定不需要某个值的时候才会跳过求值，而你算法中的minimum要求必须比较三个分支的返回值大小，必然会触发所有分支的递归求值，不会出现你预期的“提前短路停止递归”的效果。

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