hallo
wie kann ich folgendes beweisen, hab leider keinen blassen schimmer, für mich ist da einfach nur trivial:
aus f(n) = O(g(n)) und g(n) = O(h(n)) folgt, dass f(n) = O(h(n))
Mir schwant etwas, dass O() nur eine andere Schreibweise von lim x->oo ist.
MfG Georg V.
Hallo
Naja eigentlich ist das auch logisch.
Wenn f nicht wesentlich schneller als g wächst und g nicht wesentlich schneller als h, dann wird auch f nicht wesentlich schneller als h wachsen.
Um das mathematisch zu untermauern vielleicht diesen recht kryptischen Ausdruck von Wikipedia verwenden den du unter „Definition durch Quantoren“ findest!
http://de.wikipedia.org/wiki/Landau-Symbole#Definiti…
MfG IGnow
[Bei dieser Antwort wurde das Vollzitat nachträglich automatisiert entfernt]
nein eigentlich ist es ein hilfsmittel aus der informatik um algorithmen bewerten zu können…
ähm, selbstverständlich geht um die Laufzeit von Algorithmen. Und zwar um die Differenz zwischen der Laufzeit des Algorithmus und einer Funktion, die zwischen den Klammer von O steht. Also genauer f(n)= O(g(n)) => lim (n->oo) Laufzeit (f(n))-g(n)=0.
Hallo,
wie kann ich folgendes beweisen, hab leider keinen blassen
schimmer, für mich ist da einfach nur trivial:aus f(n) = O(g(n)) und g(n) = O(h(n)) folgt, dass f(n) =
O(h(n))
Dann musst du halt die Definition on O(g(n)) anwenden:
(Aus dem Gedächtnis, schau lieber noch mal nach):
Es existieren c1, s1 > 0 sodass für alle n > s1 gilt:
(1): c1 * g(n) >= f(n)
Dann das gleiche für die zweite Aussage:
Es existieren c2, s2 > 0 sodass für alle n > s2 gilt:
(2): c2 * h(n) >= g(n)
(1) in (2) einsetzen:
c2 * c1 * h(n) >= f(n) für n > s1 und n > s2
Also kannst du
c3 = c2 * c1
s3 = max(s1, s2)
finden, sodass für alle n > s3 gilt:
c3 * h(n) >= f(n)
und damit f element O(h(n))
Grüße,
Moritz
(Heute mal in Hausaufgabenerledigungslaune).