algorithm - 如果 m，O(n+m) 和 O(n) 符号是否等效 我正在阅读 Wikipedia 上的Rabin-Karp算法，其中提到的时间复杂度为 O(n+m)。现在，根据我的理解，m 必然在 0 和 n 之间，所以在最好的情况下复杂度是 O(n)，在最坏的情况下

Question

我正在阅读 Wikipedia 上的Rabin-Karp算法，其中提到的时间复杂度为 O(n+m)。现在，根据我的理解，m 必然在 0 和 n 之间，所以在最好的情况下复杂度是 O(n)，在最坏的情况下也是 O(2n)=O(n)，那为什么不是只是 O(n)？

Answer 1

基本上，Robin-Karp 将它的渐近符号表示O(m+n)为一种表示它需要相对于m+n而不只是线性时间这一事实的手段n。本质上，每当您使用渐近符号时，变量m和都必须有意义。n对于 Robin-Karp 算法的情况，n表示文本的长度，并m表示文本和模式的组合长度。请注意，O(2n)这与 的含义相同O(n)，因为O(2n)仍然是 的线性函数 n。然而，在 Robin-Karp 的例子中，m+n并不是真的只是 n. 相反，它是两者的m函数n，它们是两个自变量。因此，O(m+n)与O(n)等同O(2n)于O(n).

我希望这是有道理的。:-P

Answer 2

在某些情况下，以形式表示复杂性O(n+m)比只说 . 更合适O(max(m,n))。

场景：

考虑BFS（广度优先搜索）或DFS（深度优先搜索）作为场景。它会更直观，并且会传达更多信息来说明复杂性O(E+V)比max{E,V}. 前者与实际算法描述同步。

Answer 3

m并n测量输入数据的不同维度。长度文本和长度n模式与长度m文本和长度2n模式不同0。

O(m+n)告诉我们复杂度与文本长度和模式长度成正比。