Mergesort < Algor.+Datenstr. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 22:31 Mi 13.01.2010 | | Autor: | jumape |
| Aufgabe | | Berechnen Sie die Komplexität von Mergesort. |
Die Komplexität von Mergesort beträgt O(nlogn).
Der Beweis:
Wir gehen davon aus das der array [mm] n=2^k [/mm] elemente hat.
Dann hat mergesort [mm] log_2(n) [/mm] rekursive Ebenen, weil der Array in jedem Schritt genau in der Mitte geteilt wird.
Beim mischen werden in jeder Ebene n Vergleiche durchgeführt. so kommt man zu nlog(n)
ist das so weil jeder Vergleich dem Element zugeordnet werden kann dass nach dem Vergleich in den gemischten Array einsortiert wird? und so kommt es in jeder Ebene zu n Vergleichen?
Ist die Komplexität im worst case im best case und im average case gleich, weil ein vorher schon sortierter Teil des Arrays auch aufgespalten wird und dann zusammengefügt?
Es wäre nett wenn mir jemand antworten könnte.
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 12:51 Mi 20.01.2010 | | Autor: | bazzzty |
> Berechnen Sie die Komplexität von Mergesort.
> Die Komplexität von Mergesort beträgt O(nlogn).
> Der Beweis:
>
> Wir gehen davon aus das der array [mm]n=2^k[/mm] elemente hat.
> Dann hat mergesort [mm]log_2(n)[/mm] rekursive Ebenen, weil der
> Array in jedem Schritt genau in der Mitte geteilt wird.
> Beim mischen werden in jeder Ebene n Vergleiche
> durchgeführt. so kommt man zu nlog(n)
>
> ist das so weil jeder Vergleich dem Element zugeordnet
> werden kann dass nach dem Vergleich in den gemischten Array
> einsortiert wird? und so kommt es in jeder Ebene zu n
> Vergleichen?
Ja. Auf einer Ebene hast Du eine Menge sortierter Listen, die Du jeweils paarweise zusammenführst. Dafür benötigst Du maximal n-1 Vergleiche, um zu entscheiden, aus welcher (sortierten) Liste das nächste Element stammt. Mindestens brauchst Du n/2 Vergleiche, wenn Du nämlich erst die komplette erste Liste leerst, kannst Du Die zweite ohne Vergleiche übernehmen. Asymptotisch ändert das aber nichts.
> Ist die Komplexität im worst case im best case und im
> average case gleich, weil ein vorher schon sortierter Teil
> des Arrays auch aufgespalten wird und dann zusammengefügt?
Asymtotisch ja, tatsächlich lassen sich Vergleiche einsparen, wenn die Liste schon sortiert ist (best-case).
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 12:35 So 24.01.2010 | | Autor: | jumape |
| Aufgabe | Ich habe einen Beweis gefunden, nachdem [mm] M(n)=n\overline{log(n)}-2^{\overline{log(n)}}+1
[/mm]
und dazu braucht man, dass für n [mm] \not= 2^k+1 [/mm] gilt:
[mm] \overline{log(\underline{\bruch{n}{2}})}=\overline{log(\overline{\bruch{n}{2}})}=\overline{log(n)}-1
[/mm]
und das kann ich leider nicht beweisen, viel leicht kann mir jemand helfen. Vielen Dank im voraus.
Hierbei heisst der Strich darüber, dass das ganze aufgerundet wird und der Strich darunter, dass es abgerundet wird auf ganze Zahlen.
|
Leider weiß ich nicht wie das funktionieren soll. Ich habe mir schon überlegt verschiedene Klassen aufzuteilen also [mm] 2^k,da [/mm] stimmt es auf jeden Fall, aber dann bn ich nicht mehr weitergekommen, weil es einfach zu viele Möglichkeiten gibt, es muss irgendwie ohne diese Aufteilung gehen.
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 01:52 Mo 25.01.2010 | | Autor: | felixf |
Hallo!
> Ich habe einen Beweis gefunden, nachdem
> [mm]M(n)=n\overline{log(n)}-2^{\overline{log(n)}}+1[/mm]
> und dazu braucht man, dass für n [mm]\not= 2^k+1[/mm] gilt:
>
> [mm]\overline{log(\underline{\bruch{n}{2}})}=\overline{log(\overline{\bruch{n}{2}})}=\overline{log(n)}-1[/mm]
> und das kann ich leider nicht beweisen, viel leicht kann
> mir jemand helfen. Vielen Dank im voraus.
>
> Hierbei heisst der Strich darüber, dass das ganze
> aufgerundet wird und der Strich darunter, dass es
> abgerundet wird auf ganze Zahlen.
Sei $t [mm] \in \IN$ [/mm] maximal mit [mm] $2^t \le [/mm] n$; dann gilt $n = [mm] 2^t [/mm] + a$ mit $0 [mm] \le [/mm] a < [mm] 2^t$. [/mm] Nach Voraussetzung ist $a [mm] \neq [/mm] 1$. Den Fall $n = 1$ koennen wir uns sparen (da gibt's eh Probleme), also sei $n [mm] \ge [/mm] 2$ und somit $t [mm] \ge [/mm] 1$.
Damit ist erstmal $t [mm] \le \log_2 [/mm] n < t + 1$, und [mm] $\log_2 [/mm] n = t$ ist genau dann der Fall, wenn $a = 0$ ist. Damit ist [mm] $\overline{\log_2 n} [/mm] - 1 = [mm] \begin{cases} t - 1 & \text{falls } a = 0, \\ t & \text{falls } a > 0 \end{cases}$.
[/mm]
Jetzt ist [mm] $\frac{n}{2} [/mm] = [mm] 2^{t - 1} [/mm] + a/2$. Beachte, dass $t - 1 [mm] \le \log_2 \frac{n}{2} [/mm] < t$ gilt da [mm] $2^{t - 1} \le \frac{n}{2} [/mm] < [mm] 2^t$ [/mm] ist. Was passiert, wenn du $n/2$ auf- oder abrundest? (Mach's aehnlich wie ich mit [mm] $\overline{\log_2 n}$.) [/mm] Denk da doch mal ein wenig drueber nach, in welchen Faellen was passiert. Damit kannst du alles loesen.
LG Felix
|
|
|
|
