умножение 2 функций, которые являются большими O третьего

Question

Имея проблему с домашней проблемой. Вопрос спрашивает, является ли f(n) = O(h(n)) и g(n) = O(h(n)), тогда f(n) * g(n) = O(h(n)) является истинным заявлением.

Я занимаюсь исследованиями, и лучший ответ, который я могу придумать, заключается в том, что это правда, но не во всех случаях. Я могу придумать примеры, где это правда, но у меня возникают проблемы с случаем, когда он является ложным. Может ли кто-нибудь дать мне такой пример или, по крайней мере, направить меня к ссылке, имеющей отношение к моему вопросу? Любая помощь будет принята с благодарностью.

Answer 1

Это неправда, так как O(h(n)) может быть плотно связан.

E.g .: 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)²) держит.

Answer 2

Утверждение всегда верно, но оно может быть немного обманчивым. Это связано с тем, что большая нотация O не говорит о том, насколько плотно описывается верхняя граница. Вы можете сказать глупые вещи, например, для f(n) = 1, f(n) = O(n^2), если хотите. Это не очень полезно для этого, поскольку постоянная функция фактически не растет квадратично, но с большой нотацией O, она по-прежнему верна, так как полиномиальная функция действительно обеспечивает верхнюю границу постоянной функции.

Точные верхние границы f(n) * g(n): O(f(n)) * O(g(n)). Если вы выбираете h(n) быть равен наиболее быстро растущих из O(f(n)), O(g(n)) и O(f(n)) * O(g(n)), утверждения, что f(n) = O(h(n)), g(n) = O(h(n)) и f(n) * g(n) = O(h(n)) все собираются, чтобы быть правдой, в значительной степени по определению. Но вы часто увидите, что существуют меньшие функции, чем h, которые также ограничивают одну или несколько функций.

Если вы хотите избежать свободных границ, которые допускаются для обозначения большого О, вы можете использовать вместо этого большую тэта (Θ). Если f(n) = Θ(h(n)), то для некоторых c1 и c2, c1 * h(n) <= f(n) <= c2 * h(n) для всех достаточно больших значений n. То есть h(n) является как верхней, так и нижней асимптотической границей для f(n). Утверждение в вопросе неверно для оценок с большими тетами (хотя это работает для нескольких тривиальных случаев, таких как f и g - постоянные функции).