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-15 17:33] stefan |
se:algorithmendatenstrukturen [2009-01-17 17:23] stefan |
||
---|---|---|---|
Zeile 95: | Zeile 95: | ||
* Binomialkoeffizient: ''n über k = 1, wenn n oder k = 0, sonst (n - 1 über k) + (n - 1 über k - 1)'' | * Binomialkoeffizient: ''n über k = 1, wenn n oder k = 0, sonst (n - 1 über k) + (n - 1 über k - 1)'' | ||
* 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))'' | ||
===== ToDo ===== | ===== ToDo ===== | ||
* Wichtige Bereiche im Skript mit Klebi kennzeichnen | * Wichtige Bereiche im Skript mit Klebi kennzeichnen | ||
- | * Traversierung von Binärbäumen implementieren | + | * <del>Umwandlung Postfix/Infix</del> |
+ | * <del>Lineare Rekursion</del> | ||
+ | * <del>Binärbäume</del> | ||
+ | * <del>Traversierung von Binärbäumen implementieren </del> | ||
+ | * <del>Komplexität von Algorithmen bestimmen, Laufzeitanalyse (quadratisch, kubisch etc.)</del> | ||
+ | * <del>Codeoptimierung</del> | ||
+ | * <del>Arrays mit Quicksort sortieren (C: qsort)</del> | ||
+ | * Heapsort, Countingsort, Radixsort | ||
+ | * Backtracking (Was gibt vorgegebenes Programm aus?) | ||
+ | * Beispiele für Ermittlung der benötigten Zeit nachrechnen | ||
+ | * Codeoptimierungen ins Wiki eintragen |