解释多元大 O 符号

Question

我现在正在处理一种情况，我有一个算法，其复杂性由三个独立变量 l、m 和 n 决定。该算法的一个实现在 O((l + m)*log^2(l + m) + (m + n)*log^2(m + n)) 时间内运行，而另一个在 O((l + m + n)*log^2(l + m + n)) 内运行。我该如何解释这些复杂性？哪一个会更受欢迎？一般来说，如果 f 和 g 是 n 变量的函数，我如何确定 O(f) 是否比 O(g) 渐近更好？

Answer 1

how can I determine if O(f) is better asymptotically than O(g)?

这取决于 f 和 g 之间的关系，即它取决于调用者使用的实际参数。换句话说，如果不扩大问题的范围，就不可能回答这个问题。

如果您对这些值的行为有隐含的了解（例如，如果这些值必然在大小上相互跟随），您可以将它们等同起来，例如用 x.[=16 替换它们=]

如果这个决定对您有实际影响，我建议您实现这两种算法并在实践中尝试它们以包括执行时间的常数因素。

Answer 2

一般情况下，两个功能没有可比性是可能的。可能是不管常数 c_1 和 c_2，对于某些输入值，c_1 f > c_2 g 而对于其他输入，c_1 f < c_2 g。

对于这些特定的函数，如果变量 l、m 和 n 至少为 1，你的两个边界是等价的：f=O(g) 和 g=O （F）。

令 h(x) = x log^2 x。 h(l+m)+h(m+n) 在 h(l+m+n) 的常数内，只要 l,m,n>=1。

不失一般性，假设n>=l，所以

m+n>=l+m 
log(m+n)>=log(l+m)
log^2(m+n)>=log^2(l+m)
h(m+n) >= h(l+m)

然后我们可以使用 h 在 log 为正的情况下增加。

h(l+m)+h(m+n) <= 2 h(m+n) <= 2 h(l+m+n).

h(l+m+n) <= h((l+m)+(m+n)) 
         <= h(2(m+n))
          = 2(m+n)log^2(2(m+n))
          = 2(m+n)(log 2 + log(m+n))^2
         <= 2(m+n)(2log(m+n))^2
         <= 8(m+n)log^2(m+n)
          = 8h(m+n)
         <= 8(h(l+m)+h(m+n)).

可能会有更准确的估计，但这表明当 l、m 和 n 的值至少为 1 时，这两个估计是等价的。（当所有的变量接近于 0，因此需要一些假设将 l+m 和 m+n 推离 0。）

解释多元大 O 符号

Interpreting multivariate big-Oh notation

algorithm

big-o