O(n+log(m))能否简化？

Question

根据我的理解，不同的变量是分开处理的（但我可能错了）。

我知道O(n+log(n))可以简化为O(n)，O(n+m)不能简化，但O(n+log(m))呢？

谢谢大家的帮助!

Answer 1

大O是渐变的，所以如果你有条件f.e.m <=2*n，你可以简化这个问题。但如果没有这样的条件，你就不能简化。

Answer 2

一般来说，如果你有任何O(f(n，m))形式的大O，其中m和n是自由的独立变量，就没有一个很好的方法来简化表达式。也就是说，比如说，O(m+n)，O(m log n)，O(log_m+n n), O(m¹³⁷ + 2ⁿ)等，不能用一些更简单的函数来改写，纯粹取决于m或n，原因是大O符号衡量的是一些量在 "足够大 "的输入值下如何增长，如果m和n之间没有关系，那么m和n中的每一个都可以独立地 "足够大 "增长。

但有些情况下，m和n之间存在一些已知的关系，例如，在图算法中，通常假设m（边的数量）在n-1和n之间。²，代表了图是最小连接的情况，也代表了图有尽可能多的边的情况。在这些情况下，你有时确实会看到一些简化。例如，如果m和n之间的这种关系成立，那么你通常会看到O(log n)而不是O(log m)，因为在这种情况下，log (n-1)≤m≤2 log n。然而，即便如此，用n代替m也是不常见的。² 因为密集图和稀疏图是不同的情况，通过更精确的运行时间分析，可能会更好的预测运行时间。

希望对大家有所帮助!

Answer 3

我想。

如果m <=n^2，则O(n+log(m))简化为O(n)

这就是对数基2。现在举个例子，让n=8，现在取m=8^2=64，log(64)=6 < 8 所以，复杂度将是O(n).如果m=8^3=512，log(512)=9 > n，那么复杂度将是O(log(m))

如果n和m之间没有关系，那么不能简化O(n+log(n))。