Informatik Grundlagen – Big-O-Notation und Laufzeitanalyse
Karteikarten zum Thema „Informatik“ · 14 Karten · von atrio. Beispiele: Was beschreibt die Big-O-Notation in der Informatik? · Was ist der Unterschied zwisch…
Karten
14 KartenWas beschreibt die Big-O-Notation in der Informatik?
Rückseite
Sie gibt eine asymptotische obere Schranke für das Wachstum der Laufzeit eines Algorithmus in Abhängigkeit von der Eingabegröße an.
Was ist der Unterschied zwischen Big-O, Big-Theta und Big-Omega?
Rückseite
Big-O beschreibt eine obere, Big-Omega eine untere und Big-Theta eine asymptotisch enge Schranke für das Laufzeitwachstum.
Welche Laufzeitklasse hat ein Algorithmus mit konstanter Zeit?
Rückseite
Ein Algorithmus mit konstanter Laufzeit liegt in O(1), seine Ausführungszeit ist unabhängig von der Eingabegröße.
Wie lautet die Laufzeitklasse von binärer Suche in einem sortierten Array?
Rückseite
Binäre Suche benötigt O(log n) Zeit, da der Suchraum bei jedem Schritt halbiert wird und somit logarithmisch wächst.
Welche Komplexität hat eine einfache for-Schleife über n Elemente?
Rückseite
Eine einzelne Schleife mit n Iterationen und konstanter Arbeit pro Durchlauf hat lineare Laufzeit O(n).
Was ist die Laufzeit von zwei aufeinanderfolgenden Schleifen mit jeweils n Iterationen?
Rückseite
Aufeinanderfolgende Schleifen addieren ihre Laufzeiten: O(n) + O(n) = O(n), da Konstantenfaktoren in der O-Notation vernachlässigt werden.
Wie berechnet man die Laufzeit zweier verschachtelter Schleifen mit n und m Iterationen?
Rückseite
Verschachtelte Schleifen multiplizieren ihre Iterationszahlen: die Gesamtlaufzeit beträgt O(n·m), bei n=m also O(n²) und wächst quadratisch mit der Eingabegröße.
Nenne die typische Laufzeitklasse von Bubble Sort im Worst Case.
Rückseite
Bubble Sort hat im schlimmsten Fall quadratische Laufzeit O(n²), da jede Paarvergleichsschleife alle Elemente durchläuft.
Welche Laufzeitklasse erreicht Merge Sort im Average und Worst Case?
Rückseite
Merge Sort garantiert O(n log n) sowohl im durchschnittlichen als auch im schlimmsten Fall durch Teile-und-Herrsche-Strategie.
Was bedeutet amortisierte Laufzeit am Beispiel dynamischer Arrays?
Rückseite
Amortisiert kostet das Einfügen in ein dynamisches Array O(1), da teure Vergrößerungen selten sind und sich über viele Operationen verteilen.
Wie lautet die Master-Theorem-Formel für Rekursionen der Form T(n)=a·T(n/b)+f(n)?
Rückseite
Das Master-Theorem vergleicht f(n) mit n^{log_b a}: ist f(n) polynomiell kleiner, dominiert die Rekursion; ist es größer, dominiert f(n).
Was beschreibt die Speicherkomplexität (Space Complexity) eines Algorithmus?
Rückseite
Sie gibt an, wie viel zusätzlicher Speicherplatz ein Algorithmus in Abhängigkeit von der Eingabegröße benötigt, oft ebenfalls in O-Notation.
Wann ist ein Algorithmus als effizient in Bezug auf Laufzeit einzustufen?
Rückseite
Ein Algorithmus gilt als effizient, wenn seine Laufzeit polynomiell begrenzt ist, also O(n^k) für eine Konstante k.
Wie unterscheidet man Best-Case, Average-Case und Worst-Case bei der Laufzeitanalyse?
Rückseite
Best-Case ist minimaler Aufwand, Worst-Case maximaler Aufwand, Average-Case erwarteter Aufwand unter Annahme einer Eingabeverteilung und wird oft für realistische Einschätzungen verwendet.