Worum geht es bei der Komplexität von Algorithmen?
Mit der Analyse von Komplexität eines Algorithmus können wir folgendes messen:- Kosten - Effizienz- Korrektheit- Verständlichkeit Betrachtet werden best-case, avg-case oder worst-case. Mit dem erhaltenen Wert können wir z.B. zwei Algorithmus vergleichen und den effizienteren / besseren wählen.Anwendungsbsp.: Program Operationen1. sum = 0; 02. i = 0; 03. while (i < n) { n+14. sum += a[i]; n5. i++; n6. }7. return sum / n 1Summe 3n + 2Komplexitätsklasse: 3n + 2 Є O(3n)
Besonderheit Schleifen bei Komplexität von Algorithmen, was ist zu beachten?
Jede Schleife welche n mal aufgerufen wird, erhält den Wert n. Der Schleifenkopf erhält die Komplexität n+1, da es immer eine finale Prüfung gibt Der Schleifenkörper erhält die Komplexität n Sind mehrere Schleifen miteinander verschachtelt multipliziert sich der Wert um n Program Operationen1. sum = 0; 02. i = 0; 03. while (i < n) { n+14. sum += a[i]; n5. i++; n6. }7. return sum / n 1
Wann ist ein Algorithmus optimal?
Wenn es keinen anderen Algorithmus für das gleiche Problem mit einer besseren Komplexitätsklasse gibt.
Welche Sonderfälle gibt es bei der Komplexitätsberechnung?
Vergleichsbasiertes SortierenJeder vergleichsbasierte Algorithmus braucht Ω(n log n) Vergleiche im schlimmsten Fall. Rekursiver AlgorithmenEin rekursiver Algorithmus ohne Schleifen hat die Komplexität f(x) wenn f(x) die Anzahl der rekursiven Aufrufe in Abhängigkeit von der Eingabe x beschreibt.
