|
|
| (28 intermediate revisions by 12 users not shown) |
| Line 1: |
Line 1: |
| | Formel: |
| | <math> |
| | \Delta L_{sum} = \frac{\sqrt{L_R^4 \cdot \Delta L_B^2 + L_B^4 \cdot \Delta L_R^2}}{(L_B + L_R)^2} |
| | </math> |
| | --- |
| <math>f(x)=\sqrt[4]{x}</math> | | <math>f(x)=\sqrt[4]{x}</math> |
|
| |
|
| Line 5: |
Line 10: |
| hallo''' | | hallo''' |
|
| |
|
| | <math>L_{iij}</math> |
| | |
| | <math> |
| | X_{ij} = x_i x_j |
| | </math> |
|
| |
|
| There was a young lady from Riga, | | There was a young lady from Riga, |
| Line 17: |
Line 27: |
|
| |
|
| {| border="1" cellspacing="0" cellpadding="9" align="center" | | {| border="1" cellspacing="0" cellpadding="9" align="center" |
| ! hello | | ! hello |
| ! is | | ! is |
| |- | | |- |
| Line 24: |
Line 34: |
| |- | | |- |
| |} | | |} |
| | 5 |
|
| |
|
| | / \ |
|
| |
|
| ----
| | 2 8 |
| 4. Stunde, am 17.04.2008
| |
| <br/>
| |
| (Fortsetzung der Stunde vom 16.04.2008)
| |
| <br/>
| |
|
| |
|
| === Mergesort ===
| | / \ / \ |
| ==== Algorithmus ====
| |
| # <tt>c ← merge(a,b)</tt> (Siehe Mitschrift der Stunde am 16.04.2008)
| |
| # '''rekursiver Mergesort''':
| |
|
| |
|
| mergesort(m) ← { #m ist ein Array | | 1 4 7 9 |
| if |m| > 1 #True, wenn m mehr als 1 Element hat. | |
| a ← mergesort(m[1:<|m|/2])
| |
| b ← mergesort(m[|m|/2-1:|m|])
| |
| c ← merge(a,b)
| |
| return(c)
| |
| else
| |
| return(m)
| |
| }
| |
|
| |
|
| Bei der Sortierung mit Mergesort wird das Array immer in zwei Teile geteilt. → Es
| | This is a sentence. |
| | |
| entsteht ein Binärbaum der Tiefe <math>lgN</math>.
| |
| | |
| [[Bild fehlt noch]]
| |
| | |
| Zeitkomplexität: <math>C(N) - N \cdot lgN</math>
| |
| | |
| ==== Komplexität ====
| |
| Komplexität: <math>C(N) = 2 \cdot \left( \frac{N}{2} \right) + N = N \cdot log_2 N
| |
| | |
| \cdot N</math> (für N = <math>2^n</math> )
| |
| | |
| Erklärungen zur Formel:
| |
| * <math> C \left(\frac{N}{2}\right) </math>: für jede Hälfte des Arrays
| |
| * <math> + N </math>: für das Zusammenführen
| |
| | |
| ==== weitere Eigenschaften von MergeSort ====
| |
| * Mergesort ist '''stabil''', weil die Position gleicher Schlüssel im Algorithmus
| |
| | |
| <tt>merge(a,b)</tt> nicht verändert wird - wegen <tt>„<”</tt> hat das linke
| |
| | |
| Element Vorrang.
| |
| * Mergesort ist '''unempfindlich gegenüber der Reihenfolge der Eingabedaten'''.
| |
| | |
| Grund dafür ist die vollständige Aufteilung des Ausgangsarrays in Arrays der Länge
| |
| | |
| 1.
| |
| * Diese Eigenschaft ist dann unerwünscht, wenn ein Teil des Arrays oder gar das
| |
| | |
| ganze Array schon sortiert ist. Es wird nämlich in jedem Fall das ganze Array neu
| |
| | |
| sortiert.
| |
| | |
| === Quicksort ===
| |
| | |
| * Quicksort wurde in den 60er Jahren von Charles Antony Richard Hoare [http://de.wikipedia.org/wiki/C._A._R._Hoare] entwickelt. Es gibt viele Implementierungen von Quicksort, siehe vgl. [http://de.wikipedia.org/wiki/Quicksort].
| |
| * Dieser Algorithmus gehört zu den "Teile und herrsche"-Algorithmen (divide-and-conquer) und ist der Standardalgorithmus für Sortieren.
| |
| | |
| ==== grundlegender Algorithmus ====
| |
| | |
| quicksort(l,r) ← { #l: linke Grenze, r: rechte Grenze des Arrays
| |
| #Das Array läuft also von l bis r (a[l:r])
| |
| if r > l
| |
| i ← partition(l,r) #i ist das Pivot-Element
| |
| quicksort(l,i-1) #quicksort auf beide Hälfte des Arrays anwenden
| |
| quicksort(i+1,r)
| |
| }
| |
| Dieser Algorithmus wird rekursiv für zwei Teilstücke links und rechts des Pivot-Elements aufgerufen. Das Pivot-Element ist nach diesem Schritt an der richtigen Position (d.h. links von der Stelle i stehen nur kleinere, rechts von i nur größere Elemente als das Pivot-Element).
| |
| Die Methode partition sorgt dafür, dass diese Bedingung erfüllt ist.
| |
| | |
| ==== Algorithmus für <tt>partition</tt> ====
| |
| Aufgabe: Ordne <tt>a</tt> so um, dass nach der Wahl von <tt>i</tt> (Pivot-Element)
| |
| | |
| gilt:
| |
| # <math>a[i]</math> ist sortiert, d.h. dieses Element ist am endgültigen Platz.
| |
| # <math>\forall x \in \left\{ a \left[ l \right] , ... a \left[ i-1 \right]
| |
| | |
| \right\} : x \leq a \left[ i \right]</math>
| |
| # <math>\forall x \in \left\{ a \left[ i+1 \right], ... a \left[ r \right]
| |
| | |
| \right\} : x \geq a \left[ i \right]</math>
| |
| | |
| [[Abbildung fehlt noch]] a[i] heißt Pivot-Element (p)
| |
| | |
| i ← partition(l,r) ← {
| |
| p ← a[r] #p: Pivot-Element. Hier wird willkürlich das rechteste Element
| |
| # als Pivot-Element genommen.
| |
| i ← l-1 #i und j sind Laufvariablen
| |
| j ← r
| |
|
| |
| repeat
| |
| repeat
| |
| i ← i+1 #Finde von links den ersten Eintrag >= p
| |
| until a[i] >= p
| |
|
| |
| repeat
| |
| j ← j+1 #Finde von rechts den ersten Eintrag <= p
| |
| until a[j] <= p
| |
| swap(a[i], a[j])
| |
| until j <= i #Nachteile: p steht noch rechts
| |
| swap(a[i], a[j]) #Letzter Austausch zwischen i und j muss
| |
| #zurückgenommen werden
| |
| swap(a[i], a[r])
| |
| return(i)
| |
| }
| |
| | |
| [[Abbildung fehlt noch]]
| |
| | |
| [[Beispiel fehlt noch]]
| |
| | |
| Bemerkungen zur gegebenen Implementierung:
| |
| # Sie benötigt ein Dummy-Minimalelement.
| |
| #* Dieses Element ist durch zusätzliche <tt>if</tt>-Abfrage vermeidbar, aber die
| |
| | |
| <tt>if</tt>-Abfrage erhöht die Komplexität des Algorithmus (schlechte Performanz).
| |
| # Sie ist ineffizient für (weitgehend) sortierte Arrays, da sich folgende
| |
| | |
| Aufteilung für die Partitionen ergibt:
| |
| # Erste Partition: <tt>[l,i-1]</tt>, zweite Partition: <tt>[i+1,r]</tt>
| |
| # Die erste Partition umfasst <tt>N-1</tt> Elemente
| |
| # Die zweite Partition ist leer (bzw. sie existiert nicht), weil das Pivot-Element <tt>p = r</tt> gewählt wurde. Das Array wird also elementweise abgearbeitet.
| |
| # → <tt>N</tt> einzelne Aufrufe ⇒ Zeitkomplexität: <math>\approx
| |
| | |
| \frac{N^2}{2}</math> (siehe Berechnung vom 16.04.2008)
| |
| # Für identische Schlüssel sollten beide Laufvariablen stehen bleiben.
| |
| # Bei der gegebenen Implementierung tauscht auch gleiche Elemente aus.
| |
| # Für identische Schlüssel können die Abbruchbedingungen verbessert werden (siehe
| |
| | |
| Sedgewick).
| |
| | |
| ==== Komplexität ====
| |
| | |
| <math>C(N) = (N+1) + \frac{1}{N} \sum_{m=1}^{N} \left[ C(k-1) + C(N-k)
| |
| | |
| \right]</math> für <math> N>1;\, C_1 = C_0 =0 </math>
| |
| | |
| Anmerkungen zur Formel:
| |
| # <math>(N+1)</math>: Vergleiche für jeden Aufruf
| |
| # <math>k</math>: Teilungspunkt
| |
| <br/><br/><br/>
| |
| <math>
| |
| \frac{1}{N} \sum_{m=1}^{N} \left[ C(k-1) + C(N-k) \right] = 2 \frac{1}{N}
| |
| | |
| \sum_{k=1}^{N} C(k-1)
| |
| </math>
| |
| <br/><br/>
| |
| | |
| <math>
| |
| C(N) = (N+1) + \frac{1}{N} \sum_{m=1}^{N} \left[ C(k-1) + C(N-k) \right]
| |
| \overset{\cdot N}{\longleftrightarrow} </math>
| |
| <br/><br/>
| |
| | |
| <math>
| |
| N \cdot C(N) = N \left[ (N+1) + \frac{2}{N} \sum_{k=1}^{N} C(k-1) \right]
| |
| \overset{-\, (N-1) \cdot C(N-1)}{\longleftrightarrow} </math>
| |
| <br/><br/>
| |
| | |
| <math>
| |
| N \cdot C(N) - (N-1) \cdot C(N-1) = N(N+1) - (N-1) \cdot N + 2 \sum_{k=1}^{N}
| |
| | |
| C(k-1) - 2 \sum_{k=1}^{N} C(k-1) </math>
| |
| <br/><br/>
| |
| | |
| <math>
| |
| = N(N+1) - (N-1) \cdot N + 2 \cdot C(N-1) \longleftrightarrow </math>
| |
| <br/><br/>
| |
| | |
| <math>
| |
| N \cdot C(N) = N(N+1) - (N-1) \cdot N + 2 \cdot C(N-1) + (N-1) + (N-1) \cdot
| |
| | |
| C(N-1) = 2N + (N+1) \cdot C(N-1) \overset{/N(N+1)}{\longleftrightarrow} </math>
| |
| <br/><br/>
| |
| | |
| <math>
| |
| \frac{C(N)}{N+1} = \frac{C(N-1)}{N} + \frac{2}{N+1} </math>
| |
| <br/><br/>
| |
| | |
| <math>
| |
| = \frac{C(N-2)}{N-1} + \frac{2}{N} + \frac{2}{N+1} </math>
| |
| <br/><br/>
| |
| | |
| <math>
| |
| = \frac{C(N-3)}{N-2} + \frac{2}{N-1} + \frac{2}{N} + \frac{2}{N+1} </math>
| |
| <br/><br/>
| |
| | |
| <math>
| |
| = ... = </math>
| |
| <br/><br/>
| |
| | |
| <math>
| |
| = \frac{C(2)}{3} + 2 \sum_{k=3}^{N} \frac{1}{k+1} \approx 2 \sum_{k=3}^{N}
| |
| | |
| \frac{1}{k+1} \approx 2 \int_1^N \frac{1}{k} dk = 2 \cdot ln N
| |
| </math>
| |
| <br/><br/><br/>
| |
| Für sehr große N gilt:
| |
| <math>\approx 2 \sum_{k=1}^{N} \frac{1}{k}</math> beziehungsweise <math> \geq 2
| |
|
| |
|
| \sum_{k=1}^{N} \frac{1}{k}</math>
| | This sentence is false. |
| <br/><br/>
| | And this one is unprovable! |
| Mittlere Komplexität:
| |
| <math>C(N) = 2(N+1) \cdot lnN \approx 2N \cdot lnN </math>
| |
| <br/><br/><br/>
| |
| ==== Verbesserungen des Algorithmus ====
| |
| # Eine Verbesserung beseitigt die Rekursion durch Verwendung eines Stacks.
| |
| # "r" wird immer kleiner → Der rekursive Aufruf lohnt sich nicht mehr. → Explizites Sortieren einsetzen.
| |
| # Das Pivot-Element könnte geschickter gewählt werden: Median.
| |
| <br/>
| |
| [[Special:Contributions/147.142.207.188|147.142.207.188]] 19:31, 23 April 2008 (UTC)
| |
