Big-Oh, Concequence einer Definition

Question

ich viel Zeit, Fragen und Antworten zu Big-Oh Lesen sowohl hier und math.stackexchange und scheint damit verbracht haben, dass dies der beste Ort für sie ist als math.stackexchange nicht tun scheinen Fragen dieser Art zu mögen. Also habe ich ein paar Kursarbeiten an der Uni auf meinem CS-Kurs bekommen und ich verstehe es nicht ganz und hoffte, dass ihr helfen könnt. Ich verstehe, dass „Hausaufgaben“ Fragen leicht auf hier verpönt sind, so habe ich ein anderes Beispiel gewählt, das nicht Teil meiner Studienleistungen, aber ist von ähnlichem Stil.

Also hier ist die Definition, die ich in den Anmerkungen gegeben wurde:

Und die Frage, die ich erhalten habe, ist:

Definition Mit 2.5 zeigen, dass, wenn f (n) ist O (g (n)), dann ist k + f (n) auch O (g (n)).

Ich habe 3 Tage im Internet nach einer Antwort auf solche Probleme gesucht. Betrachtet man Definition 2.5, so heißt es, dass f (n) O (g (n)) ist und k + f (n) O (g (n)) ist. Das ist genug für mich, aber es scheint, ich muss beweisen, wie das herkommt. Ich dachte zuerst, dass es irgendwie durch Induktion getan werden sollte, aber habe mich seitdem dagegen entschieden, und es muss einen einfacheren Weg geben.

Jede Hilfe wäre willkommen. Ich erwarte nicht, dass jemand mir einfach die Antwort gibt. Ich würde es vorziehen, mehr entweder eine Methode oder einen Hinweis darauf, wo ich die Technik, dies zu tun lernen. Kann ich Dich noch einmal daran erinnern, dass dieser nicht mein tatsächlicher Kurs sondern eine Frage von ähnlichem Stil.

Vielen Dank im Voraus.

Answer 1

angenommen, f (n) ist O (g (n))
dann gibt es ein c und ein k 's.t. für alle n> k ': f (n) < = cg (n)
jetzt f (n) + k
let k < = d * g (n) für alle n größer als k d sein st betrachten'
die man weiß, ist möglich, weil k in O (1)
dann
f (n) + k < = cg (n) + dg (n) = (d + c) (g (n))
ist dann verwenden Sie die Definition und Ersatz d + c für C ==> f + k ist in O (g)

Answer 2

dann k ist O(1), f(n) ist ein O(g(n)) dann können Sie diese Werte summieren Sie dann ha ve O(1+g(n)) Dies ist O(g(n));

f(n) ist O(g(n)) dann k + f(n) ist auch O(g(n)), weil Sie in Ihrem Buch

Ignorieren Addition einer Konstanten, weil

Constant werden immer ignoriert writed haben nicht Big-O ändern Notation, jede Konstante ist O(1) in Big-O Notation.

Answer 3

f (n) < = cg (n)

k + f (n) = < c'g (n) wobei c‘= ck

so k + f (n) ist O (g (n))

Answer 4

Für was es wert ist, ist dies eine etwas erfundene Definition der Groß-O-Notation. Die allgemeinere und meiner Meinung nach intuitivere Definition ist die f(n) ~ O(g(n)) als n->a iff lim|f(n)/g(n)| <= A als n->a für einige endliche reelle Zahl A.

Der wichtige Teil ist, dass ein Limit-Kontext erforderlich ist. In CS wird diese Grenze implizit als unendlich angenommen (da dies n ist, da die Problemgröße zunimmt), aber im Prinzip kann es alles sein. Zum Beispiel sin(x) ~ O(x) als x->0 (tatsächlich ist es exakt asymptotisch zu x; dies ist die Kleinwinkelapproximation).