我有一个关于我学校的测验问题
“Boyer Moore 算法的最坏情况时间复杂度为 O(MN)，其中 M 是字符串的长度，N 是模式的长度。”
这是真假问题，我对上面的陈述回答了假，因为我总是读到 N 是文本的长度，M 是模式的长度，但我的导师说你如何定义 M 和 N 并不重要，因为它索赔声明是真的是正确的吗？如果不是，我怎么能证明他的说法在科学上是错误的？
问问题
200 次
2 回答
4
你的导师是对的。更改名称根本不重要，时间复杂度为 M * N。一切都简化为表达式：“因子的顺序不会改变乘积”。
如果 M 和 N 倒置，复杂度仍然是 N * M 或 M * N。
如果时间复杂度是完全不同的，例如 O (M^2 log N)，那么是的，如果你反转 M 的含义和 N 的含义，复杂度是完全不同的。
于 2020-06-23T17:37:45.917 回答
0
当我们编写一个数学表达式，然后跟进“其中 M 是某物，N 是某物”时，我们在本文中明确定义了 M 和 N 的含义。其他文本是否使用不同的字母来表示这些内容并不重要，因为我们的文本是独立的。现在这可能会令人困惑，因为这里 O(...) 本身就是一个标准符号。O(...) 的含义是从上下文中隐含的（我们正在谈论时间复杂度），并且这里没有任何内容可以覆盖它。但实际上，关于变量名称的唯一约定是，如果输入的一个相关维度要测量，我们通常使用 N，如果有两个，我们通常使用 M 和 N，但无论如何我们仍然需要说出我们的内容'
于 2020-06-23T17:40:56.710 回答