Landau-Symbole

Aufrufe: 370     Aktiv: 30.11.2021 um 17:53
0

  1. (b)  Seien f,g:N→R>0.Dann folgt aus f(n)=O(g(n)),dass (f+g)(n)=Θ(g(n)) ist.
    ich bin verzweifelt wie ich das beweisen soll

Diese Frage melden
gefragt

Punkte: 6

 
das zweite ist theta
ich habe folgendes
θ(g(n)) = O(g(n)) ∩ Ω(g(n))
= f(n) ≤ c.g(n) ∩ f(n) ≤ cg(n)
= cg(n)≤g(n)≤cg(n)
aber (f+g)(n) = f(n) + g(n)
O(g(n)) + g(n)
f(n)≤cg(n) +g(n)
und dieses +g(n) ist problematisch für mich
   ─   tsubasa 30.11.2021 um 17:30
Kommentar schreiben
2 Antworten
0
Dein Kommentar oben ist eine unlesbare Mischung von Zahlen, Ungleichungen, Mengenoperationen. Kein Wunder, dass Du verwirrt bist.
Schreib Dir die Bedingungen ordentlich(!) hin, mit Ungleichungen.
Ordentlich steht es z.B. bei wikipedia
Schreib dazu "Voraussetzung:" gefolgt von der Bedingung mit O
Dadrunter "Behauptung:" gefolgt von der Bedingung für Theta
Achte darauf, verschiedene Konstanten zu verwenden (das C aus der Beh. muss nicht das C aus der Vor. sein).
Dann stelle um usw. Bei weiteren Fragen poste das, was Du zu "Vor."/"Beh." aufgeschreiben hast (Foto).
Diese Antwort melden
geantwortet

Lehrer/Professor, Punkte: 38.93K

 

Leider scheint diese Antwort Unstimmigkeiten zu enthalten und muss korrigiert werden. Mikn wurde bereits informiert.
1

Überlege dir mal, welche Infos du aus der Information f(n) = O(g(n)) ziehen kannst.

Laut Definition weißt du ja schon, dass für eine Konstante $c > 0 $ gilt:  $f(n) \leq c*g(n)$

Damit kannst du Rückschlüsse ziehen (durch umstellen der Gleichung) und rausfinden, was für g(n) gilt.

Diese Antwort melden
geantwortet

Student, Punkte: 34

 

Kommentar schreiben