Benutzer-Werkzeuge
se:algorithmendatenstrukturen
Unterschiede
Hier werden die Unterschiede zwischen zwei Versionen angezeigt.
| Beide Seiten der vorigen Revision Vorhergehende Überarbeitung Nächste Überarbeitung | Vorhergehende Überarbeitung Nächste Überarbeitung Beide Seiten der Revision | ||
|
se:algorithmendatenstrukturen [2009-01-17 14:33] stefan |
se:algorithmendatenstrukturen [2009-01-17 20:32] stefan |
||
|---|---|---|---|
| Zeile 75: | Zeile 75: | ||
| * in balancierten Binärbäumen haben alle Knoten in etwa die gleiche Tiefe: bei n Knoten ist die Höhe log<sub>2</sub>(n+1) | * in balancierten Binärbäumen haben alle Knoten in etwa die gleiche Tiefe: bei n Knoten ist die Höhe log<sub>2</sub>(n+1) | ||
| * bei einem balancierten Binärbaum sind somit maximal log<sub>2</sub>(n+1) Vergleiche (=Höhe des Binärbaums) notwendig, um ein Element in einem solchen balancierten Binärbaum zu finden | * bei einem balancierten Binärbaum sind somit maximal log<sub>2</sub>(n+1) Vergleiche (=Höhe des Binärbaums) notwendig, um ein Element in einem solchen balancierten Binärbaum zu finden | ||
| + | |||
| + | ==== Heap ==== | ||
| + | * ein Heap ist ein Binärbaum, in dem alle Knoten Werte besitzen, die größer (oder gleich) sind als alle Werte ihrer Kindknoten | ||
| + | * der größte Wert befindet sich somit im Wurzelknoten | ||
| + | * Darstellung als Array: [0] = Wurzel, [1] und [2] 1. Ebene, [3], [4], [5], [6] 2. Ebene etc. | ||
| + | * Vorgänger des i. Knotens: i/2 (i >> 1) | ||
| + | * linker Nachfolger des i. Knotens: 2i (i << 1) | ||
| + | * rechter Nachfolger des i. Knotens: 2i + 1 ((i << 1) + 1) | ||
| + | * Heap (= Binärbaum) mit n Knoten hat Höhe lg n, also können alle Operationen auf einem Heap mit O(lg n) durchgeführt werden | ||
| + | * Max-Heap: Nachfolger-Knoten haben kleinere Werte, Min-Heap: Nachfolger-Knoten haben größere Werte | ||
| + | * Wiederherstellen der Heap-Eigenschaft mittels ''maxHeapify'' | ||
| ==== Traversierung ==== | ==== Traversierung ==== | ||
| Zeile 96: | Zeile 107: | ||
| * Pascal'sches Dreieck | * Pascal'sches Dreieck | ||
| + | ===== Analyse von Algorithmen ===== | ||
| + | * generell sollte darauf geachtet werden, performante Algorithmen zu verwenden, also z.B. lineare und nicht kubische | ||
| + | * die einzelnen Operationen werden bei der Laufzeitanalyse nicht berücksichtigt, obwohl sie sich eigentlich in ihrer Laufzeit unterscheiden (z.B. Bitverschiebung und Potenz) | ||
| + | * Laufzeit einiger Sortieralgorithmen | ||
| + | * Bubble-Sort: n<sup>2</sup> | ||
| + | * Select-Sort: n<sup>2</sup> | ||
| + | * Insert-Sort: WorstCase n<sup>2</sup>, BestCase linear | ||
| + | * bei der Ermittlung des Zeitbedarfs sollte immer vom WorstCase ausgegangen werden, da diese Grenze niemals überschritten werden kann und meist der AverageCase sich diesem annähert | ||
| + | * für die Analyse der Laufzeit ist eigentlich nur der Wachstumsgrad entscheidend, konstante Faktoren und Potenzen geringerer Ordnung werden bei großen n irrelevant | ||
| + | * ein Algorithmus ist effizienter als ein anderer, wenn er im ungünstigsten Fall einen geringeren Wachstumsgrad hat | ||
| + | * Überlegungen bei der Wahl eines Algorithmus | ||
| + | * Kosten-/Nutzenanalyse: effizientere Algorithmen benötigen vielleicht eine längere Entwicklungszeit, die bei seltener Nutzung des Algorithmus nicht gerechtfertigt ist | ||
| + | * bessere Algorithmen sind nicht immer deutlich komplizierter: vor der Entscheidung also erstmal schauen, wie einfach die Implementierung wirklich ist | ||
| + | * Flaschenhälse: bei langsamen Programmen muss evtl. nicht der komplette Algorithmus neu geschrieben werden, sondern evtl. nur die Flaschenhälse, die es hierfür natürlich zu identifizieren gilt | ||
| + | * Messung mit typischen Eingabedaten: die Entscheidung für einen Algorithmus sollte auf Basis von Messungen mit echten Daten erfolgen, da diese evtl. erheblich vom WorstCase abweichen | ||
| + | |||
| + | ===== Codeoptimierungen ===== | ||
| + | * wo es geht Konstanten anstatt von Variablen verwenden (constant propagation) | ||
| + | * einmalige Berechnung gleicher Ausdrücke (common subexpression elimination) | ||
| + | * keine überflüssigen Funktionsaufrufe (Operatoren sind meist schneller) | ||
| + | * Bitshifts beim Rechnen mit Zweierpotenzen verwenden (operator strength reducing) | ||
| + | * keine überflüssigen oder doppelten Berechnungen (copy propagation) | ||
| + | * Vermeiden überflüssiger Schleifendurchläufe durch Verwenden des passenden Inkrements (z.B. ''i += 10'' anstatt ''i++'') (loop strength reduction) | ||
| + | * Entfernen invarianter Ausdrücke (Berechnungen mit immer gleichem Ergebnis in der Schleife oder dem Schleifenkopf) aus Schleifen (invariant code motion) | ||
| + | * Zusammenfassen mehrerer Schleifen zu einer (loop jamming) und Vermeidung unnötiger Indexzugriffe auf Arrays | ||
| + | |||
| + | ===== Sortieralgorithmen ===== | ||
| + | * Unterscheidung | ||
| + | * Speicherstelle der Daten | ||
| + | * Intern: Daten im Arbeitsspeicher | ||
| + | * Extern: Daten auf Peripheriegerät | ||
| + | * Index-sequentiell: Daten mit Schlüssel, nach dem sie sortiert werden sollen | ||
| + | * Laufzeit (liegt zwischen n lg n und n<sup>2</sup>) | ||
| + | * Speicherplatz | ||
| + | * in-place: kein zusätzlicher Speicherplatz (außer vielleicht kleines Array oder Stack) | ||
| + | * zusätzlicher Speicher für n Zeiger | ||
| + | * doppelter Speicherplatz für Kopie der Daten | ||
| + | * Stabilität: stabile Sortieralgorithmen behalten die relative Reihenfolge der Elemente bei, wenn das Sortierkriterium gleich ist | ||
| + | * Quicksort | ||
| + | * Komplexität O(n lg n), WorstCase n<sup>2</sup> | ||
| + | * in-place mit kleinem Hilfsarray | ||
| + | * rekursiv | ||
| + | * WorstCase ist bereits sortiertes Array, kann mit Tricks optimiert werden | ||
| + | * zufällige Auswahl des Pivotelements | ||
| + | * Insertsort für kleine Teilarrays verwenden | ||
| + | * Entrekursivierung: zweiten rekursiven Aufruf durch while ersetzen | ||
| + | * Median-of-Three-Methode | ||
| + | * Drei-Wege-Partitionierung | ||
| + | * Quicksort in C (''stdlib.h''): ''void qsort(void *array, size_t n, size_t length, int (*compare)(const void *val1, const void *val2))'' | ||
| + | * Heapsort | ||
| + | * Komplexität O(n lg n) | ||
| + | * in-place mittels Heap | ||
| + | * Counting-Sort | ||
| + | * Komplexität O(n) | ||
| + | * verwendet ein Ausgabearray und ein Hilfsarray für die Häufigkeitsverteilung der Werte | ||
| + | * Sortierung über Häufigkeitsverteilung der Werte (z.B. 5 Werte kleiner als "g", also muss "g" Index 5 im neuen Array bekommen) | ||
| + | * Radix-Sort | ||
| + | * Partitionierung der Daten z.B. anhand von Anfangsbuchstaben und rekursives Sortieren | ||
| + | * Sortierung anhand des Bitmusters von Zahlen | ||
| + | * Radix Exchange Sort: Bitmuster von links nach rechts durchgehen, 0 vor 1 einsortieren | ||
| + | * Straight Radix Sort: quasi ein Counting-Sort für Bitmuster von rechts nach links | ||
| + | |||
| + | ===== Backtracking ===== | ||
| + | * Backtracking ist ein Lösungsverfahren nach dem Trial-and-Error-Verfahren | ||
| + | * über Teillösungen soll zu einer Lösung des Gesamtproblems gefunden werden | ||
| + | * wenn ein Teilproblem nicht mehr weiter lösbar ist ("Sackgasse"), werden die vorherigen Teilschritte soweit rückgängig gemacht, dass ein anderer Weg ausprobiert werden kann | ||
| + | * Beispiele | ||
| + | * Wegfindung im Labyrinth (Maus sucht Käse) | ||
| + | * Teilsummenermittlung | ||
| + | * Acht-Damen-Problem | ||
| + | * Sudoku | ||
| + | |||
| ===== ToDo ===== | ===== ToDo ===== | ||
| * Wichtige Bereiche im Skript mit Klebi kennzeichnen | * Wichtige Bereiche im Skript mit Klebi kennzeichnen | ||
| Zeile 102: | Zeile 185: | ||
| * <del>Binärbäume</del> | * <del>Binärbäume</del> | ||
| * <del>Traversierung von Binärbäumen implementieren </del> | * <del>Traversierung von Binärbäumen implementieren </del> | ||
| - | * Komplexität von Algorithmen bestimmen, Laufzeitanalyse (quadratisch, kubisch etc.) | + | * <del>Komplexität von Algorithmen bestimmen, Laufzeitanalyse (quadratisch, kubisch etc.)</del> |
| - | * Codeoptimierung | + | * <del>Codeoptimierung</del> |
| - | * Arrays mit Quicksort sortieren (C: qsort) | + | * <del>Arrays mit Quicksort sortieren (C: qsort)</del> |
| - | * Heapsort, Countingsort, Radixsort | + | * <del>Heapsort, Countingsort, Radixsort</del> |
| - | * Backtracking (Was gibt vorgegebenes Programm aus?) | + | * <del>Backtracking (Was gibt vorgegebenes Programm aus?)</del> |
| + | * Beispiele für Ermittlung der benötigten Zeit nachrechnen | ||
| + | * Codeoptimierungen ins Wiki eintragen | ||
se/algorithmendatenstrukturen.txt · Zuletzt geändert: 2014-04-05 11:42 (Externe Bearbeitung)
Seiten-Werkzeuge
Falls nicht anders bezeichnet, ist der Inhalt dieses Wikis unter der folgenden Lizenz veröffentlicht: CC Attribution-Noncommercial-Share Alike 4.0 International
