检查两个任意字符串平等的预期时间复杂程度是多少？

Question

简单（天真？）答案是O（n），其中n是较短串的长度。因为在最坏的情况下，您必须比较每对字符。

到目前为止这么好。我认为我们都同意检查两个等长度字符串的平等需要O（n）运行时。

然而许多（大多数？）语言（我使用python 3.7）存储字符串的长度以允许持续的时间查找。因此，在两个不等长度字符串的情况下，您可以简单地验证生成的时间。您可以验证Python 3是否确实进行了此优化。

现在，如果我们检查两个真正任意字符串（任意长度）的平等，那么它更有可能（无限，我相信）字符串的长度比相同的长度。哪个（统计上）确保我们几乎总是在不断的时间内比较它们。

所以我们可以比较O（1）平均的两个任意字符串，具有非常罕见的O（n）的最差情况。如果我们认为字符串比较然后以同样的方式考虑o（1），我们认为哈希表查找为O（1）？

Answer 1

为了讨论操作的预期时间复杂性，您必须在输入上指定分发，也可以解释 $ n $ 的原因。

然而，

必须小心。例如，考虑评论中的建议，以便最多地考虑长度的单词的某种分布。在这种情况下，字符串比较显然是 $ o（1）$ ，因为20只是一个常数。有几种方法可以避免它：

• 询问非渐近时间复杂性。由于时间复杂性高度依赖于计算模型，因此可以计算（例如）访问的输入存储器单元的数量。

• 您可以指定输入分布，该输入分布取决于参数 $ m $ ，然后在 $ M $ 。

这里是一个例子。给定两个随机二进制字符串长度 $ n $ ，期望大约有4个访问。相反，如果从集合 $ 0 ^ i1 ^ {ni} $ 0 ^ i1 ^ {ni} $ ，则访问数将大致为 $（2/3）n $ 。即使我们使用渐近符号，可以分离这两个分布：在第一个分布上的 $ o（1）$ 中运行算法，在 $ \ theta（n）$ 在第二个。

另一个问题是 $ n $ 的含义。考虑例如字符串 $ 0 ^ m $ ，其中 $ m \ sim g（1/2）$ 是几何随机变量。在长度的输入中运行 $ a，b $ 时，运行时间是 $ \ theta（\ min（a，b ））$ 。我们应该如何以 $ n= a + b $ ？一个选择是要求输入的预期运行时间，因为输入长度是 $ n $ 。在这种情况下， $$ \ mathbb {e} [\ min（a，b）]=sum_ {a= 1} ^ {n-1} \ frac {frac {（1/2）^ a（1/2）^ {n-1-a }}} {\ sum_ {a'= 1} ^ {n-1}（1/2）^ {a'}（1/2）^ {n-1-a'}} \ min（a，na）=frac {1} {n-1} \ sum_ {a= 1} ^ {n-1} \ min（a，na）\ inft \ frac {n} {4}， $$ 因此，预期的运行时间是 $ \ theta（n）$ 。