Bedeutung von "Multiplikation einer Funktion durch eine Konstante ändert nicht sein asymptotisches Verhalten"

Question

Ich habe dies grob verstanden als eine Funktion f (n) gegeben, wenn ich es mit einigen Konstanten "K" multiplizieren & f (n) = O (g (n)) :: f (n) < = cg (n) für einige n> = n1 dann, wenn ich f (n) als K f (n) mache, dann muss es eine andere Konstante c1 geben, durch die Wir können g (n) und cap (setzen eine höhere Grenze) zu K f (n) multiplizieren.

Was ich schwierig bin zu finden, zu verstehen ist die richtige mathematische Erklärung in dem Buch:

Answer 1

es bedeutet nur, dass unabhängig von der konstanten Zeit das asymptotische Verhalten gleich bleibt. Beispiel:

int fact; 
for (fact=1;n>1;n--) fact*=n; 

sind einfach O(n) faktoriellen mit konstanter Zeit c durch die Zeit der einzelnen Iteration der Schleife und die Multiplikation fact*=n gegeben. Multipliziert man dies durch eine Konstante bedeutet nur, dass die c hat zum Beispiel geändert:

int fact; 
for (fact=1;n>1;n--) 
if (bits(fact)+bits(n)<32) 
    fact*=n; 

Nun ist die c größer ist, weil ich Zustand in die Schleife hinzugefügt, die eine gewisse Zeit in Anspruch nimmt. Aber die O(n) bleibt. Was sich ändert, ist die Laufzeit. Auf der anderen Seite, wenn ich den Code wie folgt zu ändern:

int fact; 
for (fact=1;n>1;n--) 
if (bits(fact)+bits(n)<32) fact*=n; 
    else break; 

Dann änderte ich nicht nur die konstante Zeit c sondern auch die Basis asymptotische obere Schranke zu O(1) weil, egal wie groß n dies, wenn das Ergebnis stoppt ist erreichte 32-Bit-Grenze, die in konstanter Zeit von Schritten für groß genug sein wird n, aber dies wird nicht durch eine Konstante von grob multipliziert.

Answer 2

Nehmen wir an, wir haben eine Funktion f(n), die wir in O(g(n) zu sein wissen. Das heißt, es gibt ein n0 und c, so dass:

f(n) <= c * g(n) \forall n >= n0 

Wenn wir nun K * f(n) analysieren, ist es aus der obigen Definition folgt:

K * f(n) <= K * c * g(n) \forall n >= n0 

Wir beobachten, dass K * c ist wieder eine Konstante . Daher können wir eine weitere Konstante c' = K * c und schreiben vorstellen:

K * f(n) <= c' * g(n) \forall n >= n0 

Und das ist genau die Big-O-Definition von oben. Schließlich:

K * f(n) \in O(g(n)) 

Es ist nur eine weitere Konstante.