Bubblesort < Algor.+Datenstr. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 22:43 Mi 13.01.2010 | | Autor: | jumape |
| Aufgabe | | Welche Komplexität hat Bubblesort? |
Wenn der Array schon sortiert ist benötigt man n-1 vergleiche um zu erfahren dass er schon sortiert ist. das ist mir klar. damit haben wir den best case.
im worst case haben wir den array genau falschrum sortiert, dann müssen wir im k-ten schritt n-k vergleiche durchführen, weil in diesem k-ten schritt das k-te element an die richtige stelle gesetzt wird. die letzten k elemente sind damit sortiert nach dem k-ten schritt. so kommen wir auf
[mm] \summe_{i=1}^{n}(n-i)=\bruch{n(n-1)}{2} [/mm] vergleiche.
Das ist auch klar.
einzige frage: Wieso ist das so? wie kann man die gleichheit beweisen?
im average case steht da was von
[mm] \bruch{3}{8}n(n-2) [/mm] vergleichen
und das ist mir gar nicht klar. Warum ist das so, kennt jemand einen guten beweis?
es wäre nett, wenn mir jemand helfen könnte.
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 11:08 Do 14.01.2010 | | Autor: | dawu |
Hi jumape!
Die Formel
$ [mm] \summe_{i=1}^{n}(n-i)=\bruch{n(n-1)}{2} [/mm] $
kann man relativ einfach per Induktion nach $n$ Beweisen:
Induktionsanfang: $ [mm] \summe_{i=1}^{0}(n-i)= [/mm] 0 $, da es sich um eine ![[]](/images/popup.gif) leere Summe handelt.
Induktionsvoraussetzung (I.V.): Es gelte $ [mm] \summe_{i=1}^{n}(n-i)=\bruch{n(n-1)}{2} [/mm] $ für ein beliebiges $n [mm] \in \mathbb{N}$.
[/mm]
Induktionsschritt: Für $n+1$ gilt:
[mm]\summe_{i=1}^{n+1}((n+1)-i) & =\summe_{i=1}^{n}(n+1-i) + \underbrace{(n+1-n-1)}_{=0} = \underbrace{\summe_{i=1}^{n}(n-i)}_{=\textnormal{(I.V.)}} + n = \bruch{n(n-1)}{2} + n[/mm]
[mm] = \frac{n^2 - n}{2} + \frac{2n}{2} = \frac{n^2 + n}{2} = \frac{(n+1)n}{2} = \frac{(n+1)(n+1-1)}{2}[/mm]
Der letzte Term ist jetzt genau [mm] $\frac{n(n-1)}{2}$ [/mm] mit $n$ ersetzt durch $n+1$. Somit ist die Formel bewiesen.
Wie man den Average Case herleitet weiß ich leider nicht... :-(
Viele Grüße,
dawu
|
|
|
|
