如果 m<n，O(n+m) 和 O(n) 符号是否等价？
Are O(n+m) and O(n) notations equivalent if m<n?
我正在阅读维基百科上的 Rabin-Karp 算法，其中提到的时间复杂度为 O(n+m)。现在，根据我的理解，m 必然在 0 和 n 之间，所以在最好的情况下复杂度是 O(n)，在最坏的情况下它也是 O(2n)=O(n)，所以为什么不呢只是 O(n)?
m 和 n 测量输入数据的不同维度。长度为 n 的文本和长度为 m 的模式与长度为 2n 的文本和长度为 0 的模式不同。
O(m+n) 告诉我们，复杂度与文本的长度和模式的长度成正比。
基本上，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
在某些情况下，以 O(n+m) 的形式表达复杂性比仅仅说 O(max(m,n)) 更合适。
场景:
考虑BFS（广度优先搜索）或DFS（深度优先搜索）作为场景。
说复杂度是 O(E+V) 比 max{E,V} 会更直观，会传达更多信息。前者与实际算法描述同步。
我正在阅读维基百科上的 Rabin-Karp 算法，其中提到的时间复杂度为 O(n+m)。现在，根据我的理解，m 必然在 0 和 n 之间，所以在最好的情况下复杂度是 O(n)，在最坏的情况下它也是 O(2n)=O(n)，所以为什么不呢只是 O(n)?
m 和 n 测量输入数据的不同维度。长度为 n 的文本和长度为 m 的模式与长度为 2n 的文本和长度为 0 的模式不同。
O(m+n) 告诉我们，复杂度与文本的长度和模式的长度成正比。
基本上，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
在某些情况下，以 O(n+m) 的形式表达复杂性比仅仅说 O(max(m,n)) 更合适。
场景:
考虑BFS（广度优先搜索）或DFS（深度优先搜索）作为场景。
说复杂度是 O(E+V) 比 max{E,V} 会更直观，会传达更多信息。前者与实际算法描述同步。