Boyer-Moore 子串搜索最坏情况
Boyer-Moore Substring Search Worst Case
我有一个关于我学校的测验问题
“Boyer Moore 算法的最坏情况时间复杂度为 O(MN)，其中 M 是字符串的长度，N 是模式的长度。”
这是正确的错误问题，我对上面的陈述回答错误，因为我总是读到 N 是文本的长度，M 是模式的长度，但我的老师说你如何定义 M 和N 所以因为它声称声明是 True 是正确的吗？如果不是，我如何从科学上证明他的说法是错误的？
你的导师是对的。改名字根本不重要，时间复杂度是M * N。一切都简化为表达式：'因素的顺序不会改变产品'。
如果M和N倒过来，复杂度还是N * M或者M * N。
如果时间复杂度是，比如O(M^2 log N)，那就完全不同了，那么是的，如果你把M和N的意思倒过来，复杂度就完全不同了。
当我们写一个数学表达式然后跟进“其中 M 是 某物 并且 N 是 某物”时，我们是当我们在本文中使用 M 和 N 时，明确定义 M 和 N 的含义。其他文本是否使用不同的字母来表示那些东西并不重要，因为我们的文本是独立的。现在这可能会令人困惑，因为这里 O(...) 本身 是 一个标准符号。从上下文（我们谈论的是时间复杂度）中隐含了 O(...) 的含义，这里没有任何东西可以覆盖它。但实际上关于变量名称的唯一约定是，如果输入的一个相关维度要测量，我们通常使用 N，如果有两个，则使用 M 和 N，但无论如何我们仍然需要说明我们将它们分配给什么。
我有一个关于我学校的测验问题
“Boyer Moore 算法的最坏情况时间复杂度为 O(MN)，其中 M 是字符串的长度，N 是模式的长度。”
这是正确的错误问题，我对上面的陈述回答错误，因为我总是读到 N 是文本的长度，M 是模式的长度，但我的老师说你如何定义 M 和N 所以因为它声称声明是 True 是正确的吗？如果不是，我如何从科学上证明他的说法是错误的？
你的导师是对的。改名字根本不重要，时间复杂度是M * N。一切都简化为表达式：'因素的顺序不会改变产品'。
如果M和N倒过来，复杂度还是N * M或者M * N。
如果时间复杂度是，比如O(M^2 log N)，那就完全不同了，那么是的，如果你把M和N的意思倒过来，复杂度就完全不同了。
当我们写一个数学表达式然后跟进“其中 M 是 某物 并且 N 是 某物”时，我们是当我们在本文中使用 M 和 N 时，明确定义 M 和 N 的含义。其他文本是否使用不同的字母来表示那些东西并不重要，因为我们的文本是独立的。现在这可能会令人困惑，因为这里 O(...) 本身 是 一个标准符号。从上下文（我们谈论的是时间复杂度）中隐含了 O(...) 的含义，这里没有任何东西可以覆盖它。但实际上关于变量名称的唯一约定是，如果输入的一个相关维度要测量，我们通常使用 N，如果有两个，则使用 M 和 N，但无论如何我们仍然需要说明我们将它们分配给什么。