解释多变量大符号(Interpreting multivariate big

解释多变量大符号(Interpreting multivariate big-Oh notation)

我正在处理一种情况，我现在有一个算法，其复杂性由三个独立变量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)更渐近？

I'm dealing with a situation right now where I have an algorithm whose complexity is determined by three independent variables l, m, and n. One implementation of the algorithm runs in O((l + m)*log^2(l + m) + (m + n)*log^2(m + n)) time and another runs in O((l + m + n)*log^2(l + m + n)). How can I interpret these complexities? Which one would be preferred? In general, if f and g are functions of n variables, how can I determine if O(f) is better asymptotically than O(g)?

最满意答案

如何判断O(f)是否比O(g)更渐近？

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

如果你对值的行为有隐含的知识（例如，如果值绑定在大小上相互关联），你可以将它们等同，例如用x替换它们。

如果决定对您有实际意义，我建议您实施两种算法并在实践中尝试将其包含在执行时间的常数因素上。

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

That depends on the relation between f and g, i.e. it depends on what actual arguments the caller uses. It's in other words impossible to answer the question without widening the scope of it.

If you have implicit knowledge of the behavior of the values (for instance if the values are bound to follow each other in magnitude) you could equate them and for instance replace them with x.

If the decision has practical implications for you I suggest you implement both algorithms and try them out in practice to include the constant factors on the execution time.