algorithm - 时间复杂度理论

Question

如果 f(n) 是 O(g(n)) 并且 f(n) 是 O(h(n)) 那么 f(n)、g(n) 和 h(n) 之间的关系是什么？

我在很多地方看到过这个问题，但始终无法弄清楚其中的区别。对我来说，它看起来像 g(n) 和 h(n) 一样，但事实并非如此。

我给出的是可能的选项，请说出满足的条件:

一个。 f(n) + g(n) 是 O(h(n))

B. g(n) + h(n) 是 O(f(n))

C. f(n) 是 O(g(n) + h(n))

Answer 1

我们有:

• f(n) 是 O(g(n))(给定)
• f(n) 是 O(h(n))(给定)

对于 g(n) 和 h(n) 之间的关系，您不能说什么，因为一个可能比另一个“大”，反之亦然。你所知道的是 f(n) 受 g(n) 的限制，f(n) 受 h(n) 的限制，但这并没有说明 g(n) 和 h(n) 如何相互关联其他。