Die letzten 2 Beiträge |
JayJay |
RE: Beweisführung / Landau-Notation
Entschuldigt den ASCII Fehler, ∈ = ELEMENT_VON |
JayJay |
Beweisführung / Landau-Notation
Hallo liebe Informatiker
Ich muss folgende Aussage beweisen:
Gilt f(n) ∈ O(g(n)) und g(n) ∈ o(h(n)), dann auch f(n) ∈ o(h(n))
Durch prädikatenlogische Umformungen bin ich schon soweit gekommen, dass
f(n) ∈ ¸ (g(n)) ∧ g(n) ∈ o(h(n))
äquivalent ist zu
f(n) ∈ o(h(n))
sein muss. Allerdings weiß ich nicht, wie ich das zeigen kann.
Bis jetzt habe ich nur Dinge wie O(n) in o(n) ∧ ¸(n) aufgespalten und das Distributionsgesetz angewendet.
Hoffentlich habt ihr einen guten Ratschlag für mich,
JayJay |
|
|