Komplexität Sortieren < Komplex. & Berechnb. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 12:21 Fr 16.09.2011 | | Autor: | Harris |
Hi!
Angenommen, ich habe ein int[] mit paarweise verschiedenen Einträgen mittels verschiedener Sortieralgorithmen zu sortieren und soll die Komplexität angeben.
Ich weiß, dass man Quicksort $nlogn$, Mergesort $nlogn$, Bubblesort [mm] $n^2$ [/mm] usw... hören will. Aber ist folgende Argumentation tragbar:
Da der Wertebereich von ints endlich ist [mm] ($2^{32}$), [/mm] ist die Anzahl der Arrays mit paarweise verschiedenen ints endlich. (Konstruktion aller Teilmengen und Anordnung hat die Obere Schranke [mm] $2^{2^{32}}\cdot (2^{32})!$)
[/mm]
Verwende nun für jedes mögliche Array einen beliebigen Sortieralgorithmus und zähle die Anzahl der Schritte und wähle das Maximum $M$ aller Schritte.
Da nun jedes mit dem gleichen Sortieralgorithmus sortierte Array $M$ nicht überschreitet, ist die Sortierung für jeden Sortieralgorithmus betrachtet in [mm] $\mathcal{O}(1)$.
[/mm]
Gruß,
Harris
|
|
| |
|
moin Harris,
Das klingt an sich nicht ganz falsch....^^
Allerdings musst du bedenken, dass man immer versucht eine möglichst gute Schranke anzugeben.
Du könntest auch sagen Quicksort hat [mm] $\mathcal{O}(n!)$
[/mm]
Das wäre (so lange du nicht gerade n=1 wählst oder so^^) natürlich richtig, denn n! ist auf jeden Fall eine obere Schranke.
Ich behaupte aber einfach mal du würdest einsehen wenn du einen Fehler kriegst für die Behauptung Quicksort sei [mm] $\mathcal{O}(n!)$.
[/mm]
Also deine Argumentation ist vollkommen richtig, du kannst das ganze durch eine verdammt große Zahl nach oben beschränken, da der Wertebereich für Integer endlich ist.
Allerdings musst du bedenken, dass natürlich auch das n in $n*log(n)$ endlich ist und ins besondere $n [mm] \leq 2^{32}$
[/mm]
Deshalb ist [mm] $\mathcal{O}(n*log(n))$ [/mm] eine bessere obere Schranke als deine.
Also rein mathematisch hast du, so lange der Sortieralgorithmus definitiv nach eindlicher Zeit terminiert (also du so etwas wie Randomsort ausschließt^^) vollkommen recht mit deiner Argumentation.
Allerdings ist das nicht ganz im Sinne des Erfinders, denn diese Komplexität der einzelnen Algorithmen soll ja ein Mittel sein sie zu vergleichen; wenn sie alle [mm] $\mathcal{O}(1)$ [/mm] wären wäre das ganze also sinnlos.^^
MfG
Schadowmaster
|
|
|
|
