Wie Groß-O von rekurrenter Relation mit Logarithmus berechnen? |
| 21.03.2013, 00:15 | DerIcke | Auf diesen Beitrag antworten » |
| Wie Groß-O von rekurrenter Relation mit Logarithmus berechnen? Wie berechne ich die Groß-O-Notation einer rekurrenten Relation wie, z.B. 3T(n/2) + 4(n/4) + n log n ? Meine Ideen: Erst einmal ist 3T(n/2) + 4(n/4) + n log n < 3T(n/2) + 4(n/2) + n log n = 7T(n/2) + n log n Nach dem Master-Theorem ist a = 7, b=2 und c...ja...was ist c? (n^c) Kann mir da jemand auf die Sprünge helfen? |
||
| 21.03.2013, 08:41 | HAL 9000 | Auf diesen Beitrag antworten » |
Hast du dich zufällig verschrieben und meinst 4T(n/4) statt des oben stehenden 4(n/4) ? Und soll das ganze dann T(n) sein, d.h. insgesamt T(n) = 3T(n/2) + 4T(n/4) + n log n ? 
|
||
| 21.03.2013, 11:44 | DerIcke | Auf diesen Beitrag antworten » |
Ja, tut mir leid. Demnach geht es trotzdem um 7T(n/2) + n log n. Wie wende ich darauf denn das Master Theorem an? |
||
| 21.03.2013, 18:15 | HAL 9000 | Auf diesen Beitrag antworten » |
Bis eben habe ich vom "Master-Theorem" nichts gehört. Wenn ich mir das in der Wikipedia so anschaue, so scheint das (zumindest auf deine Folge bezogen) auch aus der gängigen Theorie linearer Differenzengleichungen zu folgen, angewandt auf die Folge . 
Allerdings ist deine Abschätzung viel zu grob: Für T(n) = 3T(n/2) + 4T(n/4) + n log n kann man T(n) = O(n²) nachweisen, was auf der Basis von T(n) < 7T(n/2) + n log n nicht gelingt. 
|
||
|
|
Verwandte Themen
| Die Beliebtesten » |
|
| Die Größten » |
|
| Die Neuesten » |
