我现在正在处理一种情况,我有一个复杂度由三个独立变量决定的算法 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)
渐近更好?
最佳答案
how can I determine if
O(f)
is better asymptotically thanO(g)
?
这取决于 f
之间的关系和 g
,即它取决于调用者使用的实际参数。换句话说,如果不扩大问题的范围,就不可能回答这个问题。
如果您对这些值的行为有隐含的了解(例如,如果这些值必然在大小上相互跟随),您可以将它们等同起来,例如用 x
替换它们.
如果该决定对您有实际影响,我建议您实现这两种算法并在实践中尝试它们以包括执行时间的常数因素。
关于algorithm - 解释多元大 O 符号,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/28656470/