multipliziert 2 Funktionen, die beide große O eines dritten

Question

haben ein Problem mit einem Hausaufgaben-Problem. Frage fragt ob f(n) = O(h(n)) und g(n) = O(h(n)) dann f(n) * g(n) = O(h(n)) ist eine wahre Aussage.

Ich habe recherchiert und die beste Antwort, die ich finden kann ist, dass es wahr ist, aber nicht die ganze Zeit. Ich kann Beispiele finden, wo es wahr ist, aber ich habe Probleme mit einem Fall, wo es falsch ist. Kann mir jemand ein solches Beispiel geben oder mich zumindest auf einen Link verweisen, der für meine Frage relevant ist? Jede Hilfe würde sehr geschätzt werden.

Answer 1

Dies ist nicht wahr, da O(h(n)) eine enge Bindung sein könnte.

Zum Beispiel: f(n) = 2n ∈ O(n) und g(n) = 3n ∈ O(n). Dann f(n) ⋅ g(n) = 6n² aber das ist nicht in O(n).

Aber Hinweis: Big-O eine obere Schranke ist, bedeutet dies, Sie eine Funktion h(n), so dass dies wahr wird finden können. Für das obige Beispiel macht h(n) = n² die Aufgabe.

Um dies zu beheben, könnte man sagen:
Wenn f(n) ∈ O(h(n)) und g(n) ∈ O(h(n)), dann f(n) ⋅ g(n) ∈ O(h(n)²) hält.

Answer 2

Die Aussage ist immer wahr, aber es kann ein bisschen irreführend sein. Das liegt daran, dass die große O-Notation nicht darauf anspricht, wie eng die obere Grenze ist, die sie beschreibt. Sie können dumme Sachen wie für f(n) = 1, f(n) = O(n^2) sagen, wenn Sie wollen. Es ist nicht sehr hilfreich, das zu tun, da eine konstante Funktion nicht quadratisch wächst, aber bei einer großen O-Notation ist es immer noch wahr, da eine Polynomfunktion tatsächlich eine obere Grenze für eine konstante Funktion liefert. Die genauen oberen Grenzen von f(n) * g(n) sind O(f(n)) * O(g(n)). Wenn Sie h(n) Pick gleich zu dem am schnellsten wachsenden von O(f(n)), O(g(n)) und O(f(n)) * O(g(n)), dass die Aussagen f(n) = O(h(n)), g(n) = O(h(n)) und f(n) * g(n) = O(h(n)) alle wahr sein werden, so ziemlich per Definition. Aber Sie werden oft sehen, dass es kleinere Funktionen als h gibt, die auch eine oder mehrere der Funktionen begrenzen.

Wenn Sie die lockeren Grenzen, die die Groß-O-Notation erlaubt, vermeiden möchten, sollten Sie stattdessen big-Theta (Θ) verwenden. Wenn f(n) = Θ(h(n)), dann für einige c1 und c2, c1 * h(n) <= f(n) <= c2 * h(n) für alle ausreichend große Werte von n. Das heißt, h(n) ist sowohl eine obere als auch eine untere asymptotische Grenze für f(n). Die Aussage in der Frage gilt nicht für Big-Theta-Grenzen (obwohl sie für einige triviale Fälle funktioniert, wie f und g sind konstante Funktionen).