⏱️

Big-O-Notation

44 cards · 🇺🇸 English → 🇩🇪 Deutsch

Zeit- und Speicherkomplexitätsanalyse für gängige Algorithmen und Operationen.

Study all 44 cards for free

Flashcards, quizzes, pixel-art games and a daily review that remembers for you.

Study this deck free

Try the first 10 cards

1 / 10

Question

Big O notation

Knew itLearning

Tap the card for the answer · swipe right if you knew it, left if not

Already have an account? Sign in

Cards

1Big O notation
Eine mathematische Notation, die das Grenzverhalten einer Funktion beschreibt, wenn das Argument gegen unendlich strebt; sie wird verwendet, um Algorithmen danach zu klassifizieren, wie ihr Zeit- oder Speicherbedarf mit wachsender Eingabegröße zunimmt
2Letter 'O'
Kurz für „Ordnung“ – die Größenordnung der Annäherung
3F(n) = O(g(n))
Die Funktion f ist asymptotisch durch g nach oben beschränkt (bis auf einen konstanten Faktor)
4O(1) complexity
Konstante Zeit – der Algorithmus benötigt unabhängig von der Eingabegröße immer gleich viel Zeit
5O(log n) complexity
Logarithmische Zeit – typisch für Algorithmen, die das Problem bei jedem Schritt halbieren (z. B. binäre Suche)
6O(n) complexity
Lineare Zeit – die Laufzeit des Algorithmus wächst linear mit der Eingabegröße
7O(n log n) complexity
Linearithmische bzw. quasilineare Zeit – typisch für effiziente vergleichsbasierte Sortieralgorithmen wie Mergesort und Heapsort
8O(2ⁿ) complexity
Exponentielle Zeit – die Laufzeit verdoppelt sich mit jedem zusätzlichen Eingabeelement
9Little-o notation
Eine Notation, bei der f(n) = o(g(n)) bedeutet, dass f asymptotisch wesentlich langsamer wächst als g
10Big Omega (Ω) notation
Eine Notation, die eine untere Schranke für das Wachstum einer Funktion angibt (f ist nach unten durch g beschränkt)
11Big Theta (Θ) notation
Eine Notation, bei der f sowohl nach oben als auch nach unten durch g beschränkt ist (scharfe Schranke) – f und g haben dieselbe Wachstumsordnung
12F(n) ~ g(n)
Asymptotische Äquivalenz – f entspricht asymptotisch g (das Verhältnis f/g nähert sich 1)
13Complexity of finding an item in a sorted array with binary search
O(log n)
14Complexity of finding an item in an unsorted list with linear search
O(n)
15Best possible time complexity for comparison-based sorting
O(n log n) im Durchschnittsfall
16Time complexity of quicksort in the average case
O(n log n)
17Worst-case time complexity of quicksort
O(n²)
18Time complexity of merge sort
O(n log n) in allen Fällen (bester, durchschnittlicher und schlechtester Fall)
19Time complexity of bubble sort
O(n²) im schlechtesten und durchschnittlichen Fall, O(n) im besten Fall (bereits sortiert)
20Time complexity of insertion sort
O(n²) im schlechtesten und durchschnittlichen Fall, O(n) im besten Fall
21Space complexity of an algorithm
Die Menge an zusätzlichem Speicherplatz, den ein Algorithmus in Abhängigkeit von der Eingabegröße benötigt
22'in-place'
Ein Algorithmus, der über die Eingabe hinaus nur O(1) oder O(log n) zusätzlichen Speicherplatz benötigt
23Amortized time complexity
Die durchschnittliche Zeit pro Operation über eine Worst-Case-Folge von Operationen hinweg
24Inverse Ackermann function's complexity
O(α(n)) – wächst extrem langsam und ist für praktische Zwecke faktisch konstant (wird bei Union-Find-Operationen verwendet)
25Polylogarithmic time
O((log n)^k) für eine Konstante k – langsamer als logarithmisch, aber schneller als jedes Polynom
26Superpolynomial function
Eine Funktion, die schneller wächst als n^c für jede Konstante c
27Subexponential function
Eine Funktion, die langsamer wächst als c^n für jede Konstante c > 1
28Can you ignore constant factors in Big O notation?
Ja, Konstanten werden weggelassen: O(5n) = O(n), O(3n²) = O(n²)
29Can you drop lower-order terms in Big O notation?
Ja: O(n² + n) = O(n²), O(n³ + n² + n) = O(n³)
30Is Big O notation an equality or an inequality?
Trotz des Gleichheitszeichens ist es eigentlich eine Ungleichung (obere Schranke) und bedeutet „ist Element einer Menge“