| Autor |
 Div and Conquer |
|
KarlStein
Junior 
Dabei seit: 30.06.2012
Mitteilungen: 8
Aus:
 |      Themenstart: 2012-07-05 10:42
|
Danke!
[ Nachricht wurde editiert von KarlStein am 07.07.2012 13:29:29 ]
|
 Profil
 Quote
 Link |
Klacks
Aktiv 
Dabei seit: 04.07.2012
Mitteilungen: 88
Aus: S. bei W.
 | Beitrag No.1, eingetragen 2012-07-05 10:46
|
Rat wobei? Ich sehe keine Frage.
Wenn dir das Aufteilen in zwei Hälften und das anschließende Vergleichen der Teilergebnisse in O(n) gelingt, dann stimmen deine ersten Überlegungen jedenfalls schonmal.
|
Profil
Quote
Link |
Kitaktus
Senior 
Dabei seit: 11.09.2008
Mitteilungen: 2580
Aus: Gifhorn(NDS)/Panketal(BRB)
| Beitrag No.2, eingetragen 2012-07-05 11:09
|
  
\ Hallo und herzlich Willkommen auf dem Matheplaneten, vielleicht möchtest Du die Komplexitätsklasse von T wissen? Hier kann man noch ziemlich direkt nachrechnen, dass T(n)=d*n*log_2(n) mit passendem d eine Lösung ist. Wenn der Aufwand für das Zusammenführen der Ergebnisse c*n ist, dann kommt man zur Gleichung d*n*log(n) = 2*d*(n/2)*log_2(n/2) + c*n. Wenn man hier vereinfacht, dann kommt man auf einen Zusammenhang zwischen c und d. Es stellt sich die Frage, wie kommt man auf den Ansatz T(n)=d*n*log_2(n)? Man kann sich Daten ansehen und einfach raten oder man verwendet das Mastertheorem. Kennst Du das? Viele Grüße, Kitaktus
|
Profil
Quote
Link |
KarlStein
Junior
Dabei seit: 30.06.2012
Mitteilungen: 8
Aus:
| Beitrag No.3, vom Themenstarter, eingetragen 2012-07-05 14:24
|
Stimmt das?:
Wenn ich die Menge immer halbiere, beträgt der Aufwand für das Zusammenfügen O(1)
Wenn ich die Menge immer achtele, beträgt der Aufwand für das Zusammenfügen O(n)? (Weil ich ja dann mit einer Schleife drüberlaufen muss, um die Ergebnisse zu vergleichen)
[ Nachricht wurde editiert von KarlStein am 05.07.2012 19:14:18 ]
|
Profil
Quote
Link |
Kitaktus
Senior
Dabei seit: 11.09.2008
Mitteilungen: 2580
Aus: Gifhorn(NDS)/Panketal(BRB)
| Beitrag No.4, eingetragen 2012-07-05 21:01
|
Entschuldige,
ich hatte nur auf die Rekurenzgleichung geschaut (oder Du hast etwas geändert, nachdem ich es gelesen hatte).
Nein, die Rekurrenzgleichung stimmt nicht. Wenn Du Minimum und Maximum suchst, ist der Aufwand für das Zusammenfügen O(1). Das Gesamtmaximum ist einfach das größere der beiden Einzelmaxima (beim Minimum ist das ähnlich).
Das ändert sich auch nicht, wenn man in acht Teile zerlegt, die einzelnen Extrema sucht und dann zusammenfügt.
Auch ohne Teile- und Herrsche-Ansatz sollte klar sein, das man Minimum und Maximum in O(n) finden kann und dass es besser auch nicht geht.
Kitaktus
[ Nachricht wurde editiert von Kitaktus am 06.07.2012 11:17:17 ]
|
Profil
Quote
Link |
KarlStein
Junior
Dabei seit: 30.06.2012
Mitteilungen: 8
Aus:
| Beitrag No.5, vom Themenstarter, eingetragen 2012-07-06 10:21
|
Ah ok. O(n) deswegen z. B. weil ich das mit einer einfachen Schleife feststellen kann.
Danke!
[ Nachricht wurde editiert von KarlStein am 06.07.2012 11:15:44 ]
|
Profil
Quote
Link |
Kitaktus
Senior
Dabei seit: 11.09.2008
Mitteilungen: 2580
Aus: Gifhorn(NDS)/Panketal(BRB)
| Beitrag No.6, eingetragen 2012-07-06 11:16
|
2012-07-06 10:21 - KarlStein in Beitrag No. 5 schreibt:
Und wie sieht man ohne Analyse sofort, dass es sich hierbei um O(n) handelt?
Ohne "Teile und Herrsche" ist das Ergebnis sehr naheliegend. Um das Maximum zu bestimmen, muss man jede Zahl mindestens einmal ansehen. Besser als O(n) kann es also nicht gehen. In O(n) kommt man andererseits problemlos hin. Man merkt sich die erste Zahl und geht der Reihe nach durch und vergleicht. Ist die gemerkte Zahl größer als die aktuelle, dann geht man einfach weiter. Anderenfalls merkt man sich die aktuelle Zahl. Das führt dazu, dass man sich nach dem k-ten Schritt gerade das Maximum der ersten k Zahlen gemerkt hat. Der Aufwand für jeden einzelnen Schritt ist durch eine Konstante nach oben beschränkt (ein Vergleich, max. eine Variablenzuweisung).
Mit "Teile und Herrsche" sieht es so aus: auf der untersten Ebene hat man n Einzelergebnisse. Bei jedem Zusammenfassungsschritt fässt man zwei Ergebnisse zu einem zusammen. Es gibt also n-1 Zusammenfassungsschritte. In jedem davon ist der Aufwand O(1). Man hat also schon für die Zusammenfassungsschritte den Aufwand O(n). Andererseits sieht man, dass O(n) die Rekurrenzgleichung erfüllt.
Hier nochmal ein Link.
Kitaktus
|
Profil
Quote
Link |
Wie unterstütze ich den Matheplaneten mit Geld?
[Neues Thema]