Klausur: O-Notation Landau-Symbole

Was beschreibt die O-Notation?

Die O-Notation beschreibt das asymptotische Verhalten einer Funktion, insbesondere das Wachstum ihrer Laufzeit oder ihres Speicherbedarfs in Abhängigkeit von der Eingangsgröße.

O(n) versus O(n²)

O(n) wächst linear, während O(n²) quadratisch wächst. Das bedeutet, dass O(n²) schneller ansteigt und bei großen n wesentlich mehr Zeit benötigt.

Fülle die Lücke: O(1) bedeutet __________.

O(1) bedeutet konstante Zeit unabhängig von der Eingangsgröße. Die Laufzeit bleibt gleich, egal wie groß die Eingabe ist.

Was ist der Unterschied zwischen O(n) und Θ(n)?

O(n) ist eine obere Schranke, während Θ(n) sowohl eine obere als auch eine untere Schranke beschreibt. Θ(n) ist präziser für das tatsächliche Wachstum.

Wahr oder Falsch: O(n log n) ist schneller als O(n²).

Wahr. O(n log n) wächst langsamer als O(n²), besonders für große n, was es effizienter macht für viele Algorithmen.

Was bedeutet O(log n)?

O(log n) beschreibt logarithmisches Wachstum, was bedeutet, dass die Laufzeit nur langsam ansteigt, wenn n wächst. Beispiel: Binäre Suche.

Was sind die Hauptanwendungen der O-Notation?

- Vergleichen von Algorithmen - Abschätzen von Laufzeiten - Optimierung von Code - Analyse von Datenstrukturen

Was ist O(n!)?

O(n!) beschreibt die Zeitkomplexität von Algorithmen, die alle Permutationen von n Elementen durchlaufen. Sehr ineffizient für große n.

Was bedeutet O(x^k)?

O(x^k) bezeichnet Polynome, deren Komplexität durch die Potenz k bestimmt wird. Höhere k-Werte führen zu schnellerem Wachstum.

Gib ein Beispiel für O(n) an.

Ein Beispiel für O(n) ist eine Schleife, die jeden Wert in einem Array einmal durchläuft, um eine Summe zu berechnen.

Was ist die Bedeutung von O(n²)?

O(n²) bedeutet, dass die Laufzeit proportional zum Quadrat der Eingangsgröße n wächst. Typisch für doppelte Schleifen.

Wahr oder Falsch: O(2^n) ist effizienter als O(n log n).

Falsch. O(2^n) wächst exponentiell und ist bei großen n deutlich ineffizienter als O(n log n).

Was beschreibt das Landau-Symbol O?

Das Landau-Symbol O beschreibt die obere Schranke einer Funktion, d.h. die maximale Wachstumsrate im Vergleich zu einer anderen Funktion.

Unterschied zwischen O-Notation und o-Notation?

Die O-Notation beschreibt eine asymptotische obere Grenze, während die o-Notation eine strikte obere Grenze beschreibt, die nicht erreicht wird.

Was bedeutet Θ-Notation?

Die Θ-Notation beschreibt eine Funktion, die sowohl obere als auch untere Schranken hat. Sie ist genau asymptotisch gleich einer anderen Funktion, z.B. $\displaystyle f(n) = Θ(g(n))$.

Fülle die Lücke: O(1) bezeichnet ________.

O(1) bezeichnet eine konstante Laufzeit, unabhängig von der Eingabegröße.

Funktion f(n) = 3n² + 2n + 1 → O-Notation?

f(n) = O(n²), da der quadratische Term die dominierende Wachstumsgeschwindigkeit ist.

Ist O(n log n) langsamer als O(n²)?

Wahr, weil n log n für große n langsamer wächst als n².

Was beschreibt die o-Notation?

Die o-Notation beschreibt eine Funktion, die asymptotisch kleiner ist als eine andere, z.B. $\displaystyle f(n) = o(g(n))$.

Vergleich: O(n) vs Θ(n).

O(n) gibt nur eine obere Grenze an, während Θ(n) sowohl obere als auch untere Grenzen bietet.

Wann verwendet man die Ω-Notation?

Die Ω-Notation wird verwendet, um die asymptotische untere Schranke einer Funktion zu beschreiben, also die minimalen Ressourcen, die notwendig sind.

Funktion f(n) = 5n³ + 2 → O-Notation?

f(n) = O(n³), da der kubische Term dominierend ist, wenn n groß wird.

Was bedeutet O(log n)?

O(log n) beschreibt ein Wachstum, das logarithmisch ist. Typisch für Algorithmen, die halbieren, wie die binäre Suche.

O(n²) ist ________ als O(n).

O(n²) ist asymptotisch langsamer, da n² schneller wächst als n für große n.

O-Notation für lineare Suchalgorithmen?

Ein linearer Suchalgorithmus hat die Zeitkomplexität $\displaystyle O(n)$, da er jedes Element einmal prüft.

Was beschreibt $\displaystyle O(1)$?

Die Zeitkomplexität ist konstant, unabhängig von der Eingabemenge. Beispiel: Zugriff auf ein Array-Element.

Wahr oder Falsch: $\displaystyle O(n^2)$ ist schneller als $\displaystyle O(n)$?

Falsch. $\displaystyle O(n)$ wächst langsamer als $\displaystyle O(n^2)$ bei großen $\displaystyle n$.

O-Notation für binäre Suche?

Die binäre Suche hat die Zeitkomplexität $\displaystyle O( ext{log} n)$, da sie die Eingabedaten halbiert.

Was ist die O-Notation von Mergesort?

Mergesort hat eine Zeitkomplexität von $\displaystyle O(n ext{ log } n)$, da es rekursiv das Array in zwei Hälften teilt.

Vergleiche $\displaystyle O(n)$ und $\displaystyle O(n ext{ log } n)$.

Bei großen $\displaystyle n$ ist $\displaystyle O(n ext{ log } n)$ langsamer als $\displaystyle O(n)$. Beispiel: Sortieren vs. Suchen.

Fülle die Lücke: Die Zeitkomplexität eines einfachen Zählens ist \displaystyle O(____) .

$\displaystyle O(n)$

Was beschreibt $\displaystyle O(n!)$?

Die Zeitkomplexität für das Problem des Handlungsreisenden im Worst-Case. Extrem ineffizient.

Ursache → Wirkung: Was passiert, wenn man einen Algorithmus mit $\displaystyle O(n^3)$ verwendet?

Die Laufzeit wird exponentiell langsamer mit zunehmender Eingabemenge, was ineffizient ist.

Beispiel für $\displaystyle O(n^2)$?

Einfaches Sortieren mit einem Blasensort: Jeder Vergleich für jedes Element.

Was ist die O-Notation für Insertion Sort?

Die Zeitkomplexität von Insertion Sort ist $\displaystyle O(n^2)$ im Worst-Case, $\displaystyle O(n)$ im Best-Case.

Vergleiche $\displaystyle O(1)$ und $\displaystyle O(n)$.

$\displaystyle O(1)$ bleibt konstant, während $\displaystyle O(n)$ linear wächst. Beispiel: Datenzugriff vs. Datenverarbeitung.