Landausymbole bweise

xroads42

Hallo,

sei O(g)°O(h)={e°f|e ele. O(g), f ele. O(f)} und ° ele {+,-,*}

zeigen oder wiederlegen sie das gilt:

O(g)+O(h)=O(g+h)
...

=> FürAlle n0 ele |N existiert ein c : e+f<=c*(g+h)

hmm, weiter weiß ich net.... Kann mir jemand helfen??

WebFritzi

Vielleicht erklärst du allen hier mal, was eεO(g) bedeutet.

xroads42

Ich dachte das währe wegen der überschrift klar. Landausymbole.

link: http://de.wikipedia.org/wiki/Landau-Symbole

Soll heißen ab einen n0 ist für alle n>n0 a(n) echt kleiner als g(n).

WebFritzi

Ich zeig's dir:

Behauptung: O(g+h) = O(g) + O(h)
Beweis: (a) Sei fεO(g)+O(h). Dann existieren μεO(g) und λεO(h), so dass f = μ + λ. Es sei μ_n ≤ c(μ)g_n für n≥n(μ) und λ_n ≤ c(λ)h_n für n≥n(λ). Dann gilt mit c := max{c(μ),c(λ)} und n₀ := max{n(μ),n(λ)} für n ≥ n₀:

f[t]n[/t] = [e]mu[/e][t]n[/t] + [e]lambda[/e][t]n[/t]
            [e]le[/e] c([e]mu[/e])g[t]n[/t] + c([e]lambda[/e])h[t]n[/t]
            [e]le[/e] c (g[t]n[/t] + h[t]n[/t]),

also fεO(g+h). (b) Sei nun andersherum fεO(g+h). Dann existieren c > 0 und n₀ε|N, so dass f_n ≤ c (g_n + h_n) für n ≥ n₀. Setze dann λ := f - cg und μ := cg. Dann ist klar, dass μεO(g), und weiter gilt λ_n = f_n - cg_n ≤ ch_n für n≥n₀. Daraus folgt λεO(h), und insgesamt f = μ + λ ε O(g)+O(h).

Jester

Für - gilt's übrigens nicht:

f(n)=n, g(n) = 2n, beide εO(n), aber

(f-g)(n) = n ist nicht in O(0).
* sollte wieder funktionieren, / tut wieder nicht, ähnliches Beispiel wie oben.

MFG Jester

Das hast du niemals alleine bewiesen WebFritzi! Du hast das von wo kopiert.

WebFritzi

stutzig schrieb:

Das hast du niemals alleine bewiesen WebFritzi! Du hast das von wo kopiert.

Als Mathestudent im 12. Semester ist sowas für mich ein Klacks! Und das ist nicht mal angegeben.