所以最近我开始了一个编码项目，试图创建一些代码，以数学方式创建一种描述两个字符串相似程度的方法。在我的研究中，我在网上找到了很多例子来帮助我创建我想要的代码。我发现了一个错误，在我运行它的过程中，它正在创建，我称之为指数循环。它不是一个无限循环，它运行并解决问题，但我传递到方法中的字符串越长，方法运行的时间就越长。代码在下方
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);
}
我试着用粗体和斜体表示，我的意思是，这是一个带有"***"的部分。到了那个部分，我理解了，但接下来的部分，第三个LevensteinDiskCall，这是第一次迭代，我开始失去对递归的关注，以及它是如何工作的，以及我的困惑是从哪里开始的。本部分
LevenshteinDistance(source.Substring(0, source.Length - 1), target.Substring(0, target.Length - 1)) + distance);
}
我收集到的代码一旦到达这个调用，就开始重新执行第一个LevensteinDistance调用，并重复它刚刚执行的调用。这就是我所困惑的。为什么它会再次调用递归调用的第一部分，然后调用第二部分，是什么导致完成代码的时间呈指数级延长？
注意：时间可能不是字面意义上的指数，运行短字符串比较的时间是亚秒，一旦字符串变长一点，它就会从亚秒跳起来->~15秒->2:30分钟->35分钟
第二个注意：标记为无限循环的指数循环不存在，这有点接近它。
因为它是递归的，而不仅仅是单个递归（就像你在树视图中使用的那样），所以这个小狗会传递自己3个递归调用的返回结果！
这就是为什么你看到的指数时间会随着字符串的增加而增加。
对于一对大小为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（3max（n，m）），它是指数的。
标准递归算法多次计算值。
这里是两个大小为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))。这里有一个很好的答案，可以解释和计算复杂性。
但是，这可以通过使用计算值的缓存来克服，并检查缓存中是否已经计算出该值。这种方法也被称为记忆化，然后复杂性变成Θ(nm)。
请注意，每个调用要进行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^
希望这能充分说明代码的性能
我还没有过多地分析你的算法或实现，但我可以告诉你一些提高性能的方法
- 在这种情况下，请使用字符数组而不是字符串作为参数。并将指针传递到正在考虑的数组的最后一个字符。这不仅可以减少大量不需要的分配，还可以删除所有子字符串调用
- 使用动态编程，即存储调用的结果，并在启动递归调用之前进行查找，因为相同的递归调用会进行很多次