为什么这段代码会产生一个指数循环网络，Levenshtein Distance

Question

所以最近我开始了一个编码项目，尝试创建一些代码来从数学上创建一种方法来描述两个字符串的相似程度。在我的研究中，我在网上找到了大量示例来帮助我创建我想要的代码。我有一个错误，我发现它在我的运行中正在创建，我称之为指数循环。它不是无限循环，它运行并解决问题，但我传递给方法的字符串越长，方法运行的时间就越长。代码在下面

public static int LevenshteinDistance(this string source, string target)
    {
        Console.WriteLine("Start of method");
        if (source.Length == 0) { return target.Length; }
        if (target.Length == 0) { return source.Length; }

        int distance = 0;

        Console.WriteLine("Distance creation");
        if (source[source.Length - 1] == target[target.Length - 1]) { distance = 0; }
        else { distance = 1; }

        Console.WriteLine("Recursive MethodCall");
        return Math.Min(Math.Min(LevenshteinDistance(source.Substring(0, source.Length - 1), target) + 1,
                                 LevenshteinDistance(source, target.Substring(0, target.Length - 1))) + 1,
                                 LevenshteinDistance(source.Substring(0, source.Length - 1), target.Substring(0, target.Length - 1)) + distance);
    }

因此，对于较小的字符串，此方法运行良好，但是，当我开始传递地址或长名称等内容时，它需要很长时间。事实上，我完全解散了这种方法并编写了另一种方法（如果有人需要，我会提供这种方法，但这对问题并不重要）这符合我的目的，但为了解决问题和学习，我试图弄清楚正是为什么递归编码时这个要花这么长时间。我在调试模式下用笔和纸单步执行我的代码，当我在此处进行递归调用时

return Math.Min(Math.Min(LevenshteinDistance(source.Substring(0, source.Length - 1), target) + 1,
                                 LevenshteinDistance(source, target.Substring(0, target.Length - 1))) + 1,
                                 LevenshteinDistance(source.Substring(0, source.Length - 1), target.Substring(0, target.Length - 1)) + distance);
    }

而且我可以弄清楚这些部分发生了什么

return Math.Min(***Math.Min(LevenshteinDistance(source.Substring(0, source.Length - 1), target) + 1,
                                 LevenshteinDistance(source, target.Substring(0, target.Length - 1))) + 1,***
                                 LevenshteinDistance(source.Substring(0, source.Length - 1), target.Substring(0, target.Length - 1)) + distance);
    }

我试着把我说的部分加粗和斜体化，就是用'***'包围的部分。进入我理解的那部分，但接下来的部分，第三次 LevenshteinDistance 调用和它的第一次迭代，我开始失去对递归及其工作方式以及我的困惑开始的地方的关注。这部分

LevenshteinDistance(source.Substring(0, source.Length - 1), target.Substring(0, target.Length - 1)) + distance);
    }

我收集的代码一旦到达此调用便开始重新执行第一个 LevenshteinDistance 调用并重复它刚刚执行的调用。这就是我感到困惑的地方。为什么它会再次调用递归调用的第一部分，然后再调用第二部分，是什么导致完成代码的时间呈指数增长？

注意：时间可能不是字面意义上的指数级，运行短字符串比较的时间是亚秒级的，一旦字符串变长一点，它就会从亚秒级跳转 -> ~15 秒 -> 2:30 分钟 -> 35 分钟

第二个注意：标记为无限循环，因为不存在指数循环，这有点接近它。

Answer 1

因为它是递归的，而不仅仅是单一递归（就像您将用于树视图一样），所以这只小狗传递了 return 自身 3 次递归调用的结果！

这就是为什么您看到的指数时间随着字符串的增加而增加。

Answer 2

对于大小为 n 和 m 的一对字符串（源、目标），您正在对该函数进行 3 次递归调用。

LevenshteinDistance(source[0..n - 1], target)
LevenshteinDistance(source, target[0..m - 1])
LevenshteinDistance(source[0..n - 1], target[0..m - 1])

因此您正在创建一棵树，每个节点有 3 个子节点，最小深度为 min(n,m)，最大深度为 max(m,n)

因此，在这棵树的每一层中，节点数量是上一层的 3 倍：

0
|- 1
    |- 2
    |- 2
    |- 2
|- 1
    |- 2
    |- 2
    |- 2
|- 1
    |- 2
    |- 2
    |- 2

以此类推

因此，对于树中的每个级别 k，您有 3^k 个节点。所以你的算法的复杂度是 O(3^max(n,m)) 这是指数级的。

Answer 3

标准递归算法多次计算值。

这里有两个大小为3的字符串的小例子，计算顺序是

D[2, 2] = min(recurse(1, 2), recurse(2, 1), recurse(1, 1) + eq(1, 1))

在你得到 3 个递归调用之后

//first recursive call
D[1, 2] = min(recurse(0, 2), recurse(1, 1), recurse(0, 1))

//second recursive call
D[2, 1] = min(recurse(1, 1), recurse(2, 0), recurse(1, 0))

//third recursive call
D[1, 1] = min(recurse(0, 1), recurse(1, 0), recurse(0, 0))

在这里您已经看到我们对同一个值进行了多次计算。

如您所知，复杂性呈指数级增长。更精确 Θ(3^min(m, n))。 Here is a good answer that explains and calculates the complexity.

但是，可以通过对计算值使用缓存并检查缓存是否已计算该值来解决这个问题。这个方法也叫Memoization，复杂度就变成了Θ(nm).

Answer 4

请注意，您为每个调用进行了 3 次递归调用。我的数学有点不对劲，但大致上你对每个级别进行了 3 次调用（在递归调用树中）。该级别对应于 2 个输入字符串之间的最小字符数。

对于 LevenshteinDistance("a", "x") 次调用，您最终将进行 4 次调用（首次调用 + 3 次递归调用）

对于 LevenshteinDistance("ab", "xy") 调用，您最终将进行 19 次调用（第一次调用 + 3 次递归调用，每次递归调用导致另外 3 次调用，其中 2 次调用将在最后一次再次递归）

(ab, xy)
        (a, xy)
                (<empty>, xy)
                (a, x)
                        (<empty>, x)
                        (a, <empty>)
                        (<empty>, <empty>)
                (<empty>, x)
        (ab, x)
                (a, x)
                        (<empty>, x)
                        (a, <empty>)
                        (<empty>, <empty>)
                (ab, <empty>)
                (a, <empty>)
        (a, x)
                (<empty>, x)
                (a, <empty>)
                (<empty>, <empty>)

请注意，调用树中的每个体面（处理字符串中的最后一个字符）不会将 n 减 1，导致总数介于 (3^(n+1)-1)/2 到(3^(n+2)-1)/2 次调用

希望能充分说明代码的性能

我没有过多地分析你的算法或实现，但我可以告诉你一些可以提高性能的东西

在本例中使用字符数组而不是字符串作为参数。并将指针传递给正在考虑的数组的最后一个字符。这不仅会减少很多不需要的分配，而且会删除所有子字符串调用
使用动态编程，即存储调用结果并在触发递归调用之前进行查找，因为相同的递归调用会进行很多次

为什么这段代码会产生一个指数循环网络，Levenshtein Distance

Why is this code producing an exponential loop? .Net, Lehvenstein Distance

.net

c#

recursion

infinite-loop

levenshtein-distance