Cooler Adblocker Abiunity kannst du auch ohne Adblocker werbefrei nutzen ;) Einfach registrieren und mehr als 10 Bedankungen sammeln!
 
blra
Schüler | Niedersachsen
02.11.2010 um 15:49 Uhr
Zitat:
Original von 0x3E9
@blra: Du sprichst hier von einem optimierten Algorithmus; bei dem im Struktogramm dargestellten Algorithmus hängt die Komplexiät nur von max ab (siehe unten)

Die "zentrale Anweisung" ist ja der Vergleich feld[j] > feld[j+1].
Also schauen wir uns einfach mal an, wie oft diese ausgeführt wird (den Algorithmus einfach mal im Kopf durchgehen):

max=1 --> 1-mal
max=2 --> (2+1) mal
max=3 --> (3+2+1) mal
max=4 --> (4+3+2+1) mal

allgemein: 1+2+3+...+max mal

Nach der gaußschen Summenformel gilt:
1+2+3+...+max = ( max*(max+1) ) / 2
=(max²+max)/2

Bei der Komplexität (dem geschätzten Aufwand) eines Algorithmus ist der lineare Teil gegenüber dem quadratischen zu vernachlässigen, da uns hier nur interessiert, wie sich der Algorithmus bei großen Datenmengen, also großen "max" verhält.

Folglich hat der Algorithmus quadratische Komplexität: t ~ max².


Hab ich ja auch geschrieben, dass es sich quadratisch verhält. Das max ist bei mir wie oft zu finden die Eingabegröße n, die du im Array hast.

Du beachtest in deiner Ausführung nicht die Beschaffenheit deines Arrays. Das könnte wie oben beschrieben schon sortiert sein oder nicht. Du gehst bei deinem Beispiel von der ungünstigsten Anordnung der Elemente aus (also umgekehrt sortiert, wodurch alle Elemente einmal vertauscht werden müssen). Im günstigsten Fall geht der Algortihmus einmal die Liste durch und stellt fest, dass sie sortiert ist. Übrigens musst du beachten, dass es sich beim Vertauschen auch um eine "Anweisung" handelt.

zu Bubble-Sort würde ich den Wikipedia-Artikel empfehlen: http://de.wikipedia.org/wiki/Bubblesort
0
#105013
 
0x3E9
Schüler | Niedersachsen
02.11.2010 um 21:09 Uhr
hm, ich weiß, was das Problem ist: Ich hab mir den Algorithmus so vorgenommen, wie er im Struktogramm steht, allerdings ist das nicht der "richtige" Bubblesort-Algorithmus.

Für den im Struktogramm angegebenen nicht optimierten Algorithmus stimmt meine Erläuterung (--> Komplexität: x²), da dieser ja die Liste einfach immer und immer wieder durchgeht, egal, ob sie schon sortiert ist.

Für den optimierten Bubblesort-Algorithmus mit folgendem Struktogramm stimmt das, was du gesagt hast:
[img]http://www.tinohempel.de/info/info/ti/images/bubbleII.gif[/img]
So sieht es ja auch im Bubblesort-Pseudocode von Wikipedia aus.
0
#105113
Cooler Adblocker Abiunity kannst du auch ohne Adblocker werbefrei nutzen ;) Einfach registrieren und mehr als 10 Bedankungen sammeln!
x
BBCodes