tkiela
Hüüüüäääh? :):)
- 25 August 2007
- 634
- 44
Hallo.
Ich bin gerade dabei, den Bubblesort-Algorithmus zu analysieren.
Die genaue Anzahl an Vertauschungen für den Worst-Case ist ja:
Ich hab mir das bisher soweit klar gemacht, dass ich mir 2 Beispiele angeschaut hab. Das kommt auch soweit immer hin.
"Mathematisch" ist mir auch klar, dass man (n-1) Durchläufe benötigt, in denen jeweils (n-1) Vergleiche getätigt werden. Soweit ist es also (n-1)*(n-1). Wiegenau bekomm ich jetzt noch erkenntlich in die Formel, dass pro Durchlauf ein Vergleich wegfällt, da ja das letzte Element nicht mehr verglichen werden muss?
Bzw. wie komm ich von der oben Dargestellten Summe zu der fertigen Anzahl: (n²-n)/2 ?
Besten Dank schonmal!
Achja: Bild von https://de.wikiversity.org/wiki/Kur...turen/Kapitel_2/BubbleSort#Worst-Case_Analyse wo ich mir das soweit auch (fast) schon klar gemacht habe.
Ich bin gerade dabei, den Bubblesort-Algorithmus zu analysieren.
Die genaue Anzahl an Vertauschungen für den Worst-Case ist ja:
Ich hab mir das bisher soweit klar gemacht, dass ich mir 2 Beispiele angeschaut hab. Das kommt auch soweit immer hin.
"Mathematisch" ist mir auch klar, dass man (n-1) Durchläufe benötigt, in denen jeweils (n-1) Vergleiche getätigt werden. Soweit ist es also (n-1)*(n-1). Wiegenau bekomm ich jetzt noch erkenntlich in die Formel, dass pro Durchlauf ein Vergleich wegfällt, da ja das letzte Element nicht mehr verglichen werden muss?
Bzw. wie komm ich von der oben Dargestellten Summe zu der fertigen Anzahl: (n²-n)/2 ?
Besten Dank schonmal!
Achja: Bild von https://de.wikiversity.org/wiki/Kur...turen/Kapitel_2/BubbleSort#Worst-Case_Analyse wo ich mir das soweit auch (fast) schon klar gemacht habe.
