1

为了好玩，我写了一个字谜生成器。它需要一些输入的单词或短语，并以不同的组合重新排列字母以生成新的单词或短语。例如，如果您输入“cat and dog”，它将返回诸如“can dad got”或“ant cog dad”之类的内容。

一位朋友问运行时间是多少，我意识到在这种情况下我不确定如何计算它。在启动时，我读入了一个单词列表（一本字典）。就我而言，它大约有 200,000 个单词（它是标准的 unix /usr/share/dict/web2 字典）。这并没有真正考虑到运行时间，因为这是应用程序启动时的一次性事情，读取和索引字典需要不到一秒钟的时间。

当用户输入一个词时，应用程序会在字典中搜索候选词列表。如果一个词只包含来自输​​入词或短语的字母子集，那么它就是候选词。生成候选人是该过程的一个微不足道的部分，现在可以忽略。

然后它开始搜索。它选择候选列表中的第一个单词。接下来，它从输入字符串中的剩余字母中删除该单词的字母。然后它在候选词中搜索仅包含新减少的输入字符串的子集的任何剩余单词。然后它使用新的缩减输入词和缩减候选列表进行递归。它会重复此操作，直到没有候选对象，或者输入字符串全部用完。

所以它可能从它必须搜索的 100 个候选人开始。它选择一个，在删除任何具有相同字母的其他字母后，可能还剩下 90 个，或者可能还剩下 50 个，或者可能还剩下 10 个，所以当我们递归时，每次都剩下不同的数字要搜索。这就是为什么我无法理解运行时间的原因。

如果我们从未从列表中删除任何单词，那将是 O(n!)，其中 n 是候选者的数量。但是由于我们在每次迭代中都积极地修剪列表，所以它的结果远远小于 n！。例如，我尝试的一个短语生成了超过 4,000 个候选词，最终找到了超过 600,000 个组合。在最近的笔记本电脑（仅使用单核）上这样做只需要大约 30 秒，所以显然它不是 O(n!)。

为了了解运行时间，我是否需要一些统计数据来说明每次迭代或类似的东西平均修剪了多少候选列表？

我在想，如果每次迭代都从列表中删除 10 个候选者，那么对于 100 个候选者列表，我们会有这样的结果：100 * 90 * 80 * 70... 或更一般地说，n * (n - 10) * (n - 20) * (n - 30)... 在 100 个候选列表的情况下，结果为 O(n^10 - a*n^9 - b*n^8 ...)。

我的计算是否正确，或者还有更多？

4

3 回答 3

0

你是在正确的方向。考虑您在评估时获得的唯一最高次数的多项式。所以在你的情况下：
n*(n-10)*(n-20)*...10

会给(n)^(n/10)。

所以你的算法的运行时间是O( (n)^(n/10) )。

另请参阅此内容以更好地了解运行时间。

于 2013-07-07T17:13:13.933 回答
0

首先，请注意，运行时间取决于输入的长度：O(m). 如果用户多次输入一个包含所有字母的很长的短语：

一个快速的棕色修复跳过了懒惰的狗；一个快速的棕色修复跳过了懒惰的狗；一个快速的棕色修复跳过了这只懒惰的狗，......

您的算法将在第一次迭代中考虑完整的字典（大小n）O(m)，因此运行时间为n^O(m).

n^O(m)在这里，即使它是正确的，该语句也相当弱：确切的运行时间可能看起来像n^0.01mor n^0.1m; 您可能会认为两者都小于n^O(m)，但您无法准确找到存在哪个因素（这取决于英语语言的结构），因此n^O(m)这里的意思是“最坏情况下的指数运行时间；算法不会在较大的值下完成m”。

当然，您可能对较小值的运行时间感兴趣m。如果你假设m<20，很明显运行时间是 O(n^20); 您可能认为这是比O(n!)或更好的估计O(n^(n/10))。

为了得到更好的估计，必须考虑字典的结构；运行时间很大程度上取决于字典。例如，如果字典中的所有单词至少包含 2 个字母（不确定），则运行时间可以估计为O(n^(m/2))。

无论如何，big-O 符号似乎无法以任何有用的方式解决这个问题。

于 2013-07-07T21:30:34.247 回答
0

如果一个候选词的平均长度是k，并且源短语是这样的，所有候选词只被一个一个地删除，那么复杂度将是 O((n/k)!)。

如果初始候选数为M，并且每一步从候选列表中删除s单词，则复杂度为 O(M * (Ms) * (M-2s) * ...) = O((M/s)! * s米/秒）。

在最坏的情况下，你仍然有 O(n!)。

但是，嗯，n!这是人们对这样一项任务的期望。我想大多数优化应该在搜索和删除候选者的代码中执行。

于 2013-07-07T17:14:27.133 回答