<分区>
遇到家庭作业问题。问题询问如果 f(n) = O(h(n)) 和 g(n) = O(h(n)) 那么 f(n) * g(n) = O(h(n)) 是一个正确的陈述。
我一直在研究，我能想到的最佳答案是它是真实的，但并非总是如此。我可以举出正确的例子，但我遇到了错误的例子。任何人都可以给我这样的例子，或者至少指导我找到与我的问题相关的链接吗？任何帮助将不胜感激。
<分区>
遇到家庭作业问题。问题询问如果 f(n) = O(h(n)) 和 g(n) = O(h(n)) 那么 f(n) * g(n) = O(h(n)) 是一个正确的陈述。
我一直在研究，我能想到的最佳答案是它是真实的，但并非总是如此。我可以举出正确的例子，但我遇到了错误的例子。任何人都可以给我这样的例子，或者至少指导我找到与我的问题相关的链接吗？任何帮助将不胜感激。
最佳答案
这不是真的，因为 O(h(n)) 可能是一个紧密的界限。
例如:
f(n) = 2n ∈ O(n) 和 g(n) = 3n ∈ O(n)。然后 f(n) ⋅ g(n) = 6n² 但这不在 O(n) 中。
但请注意:Big-O 是一个上限，这意味着您可以找到一个函数h(n) 使它变为真。对于上面的示例，h(n) = n² 完成了这项工作。
要解决这个问题，你可以说:
如果 f(n) ∈ O(h(n)) 且 g(n) ∈ O(h(n))，则 f(n) ⋅ g(n) ∈ O(h(n)²) 成立。
关于algorithm - 将 2 个函数相乘，这两个函数都是三分之一的大 O，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/36122865/