Flbkwikiadmin: Die Seite wurde neu angelegt: „== Einführung == Die '''Laufzeit''' eines Algorithmus beschreibt das Wachstum der Ausführungszeit in Abhängigkeit von der Eingabegröße. Die grundlegende Zuordnungsfunktion lautet dabei: > ''Laufzeit $\rightarrow$ Eingabegröße (siehe Grafik)'' In der Informatik interessiert man sich bei der Analyse von Algorithmen meist nicht für die exakte Funktionsvorschrift (inklusive aller Konstanten und kleineren Terme), sondern primär für die '''„Grö…“

2026-03-05T13:24:27Z

Die Seite wurde neu angelegt: „== Einführung == Die '''Laufzeit''' eines Algorithmus beschreibt das Wachstum der Ausführungszeit in Abhängigkeit von der Eingabegröße. Die grundlegende Zuordnungsfunktion lautet dabei: > ''Laufzeit $\rightarrow$ Eingabegröße (siehe Grafik)'' In der Informatik interessiert man sich bei der Analyse von Algorithmen meist nicht für die exakte Funktionsvorschrift (inklusive aller Konstanten und kleineren Terme), sondern primär für die '''„Grö…“

Neue Seite

== Einführung ==

Die '''Laufzeit''' eines Algorithmus beschreibt das Wachstum der Ausführungszeit in Abhängigkeit von der Eingabegröße. Die grundlegende Zuordnungsfunktion lautet dabei:
> ''Laufzeit $\rightarrow$ Eingabegröße (siehe Grafik)''

In der Informatik interessiert man sich bei der Analyse von Algorithmen meist nicht für die exakte Funktionsvorschrift (inklusive aller Konstanten und kleineren Terme), sondern primär für die '''„Größenordnung“''' in Form des dominantesten Terms (der höchsten Potenz). Die formale Notation hierfür nennt sich '''O-Notation''' (oft auch ''Landau-Notation'' oder ''Big-O-Notation'' genannt).

Das Laufzeitverhalten von Algorithmen erschließt sich über die Anzahl der '''Kernoperationen'''. Kernoperationen sind elementare Arbeitsschritte, die maßgeblich charakteristisch für die Gesamtlaufzeit des Algorithmus sind.

== Beispiele für Komplexitätsklassen ==

Die folgende Tabelle zeigt verschiedene mathematische Funktionen, deren Wachstumsverhalten und die daraus resultierende Komplexitätsklasse in der O-Notation. Bei der Bildung der O-Notation fallen konstante Vorfaktoren sowie unbedeutendere Summanden weg.

{| class="wikitable"
! Funktion !! Wachstum !! O-Notation
|-
| <math>32 + 5 \cdot 45</math> || konstant || <math>\mathcal{O}(1)</math>
|-
| <math>2 \cdot \log_4(n) + 4</math> || logarithmisch || <math>\mathcal{O}(\log n)</math>
|-
| <math>0{,}6 \cdot n + 3{,}4</math> || linear || <math>\mathcal{O}(n)</math>
|-
| <math>5 \cdot n^2 + 4 \cdot n</math> || quadratisch || <math>\mathcal{O}(n^2)</math>
|-
| <math>9 \cdot n^7 + 6 \cdot n^5</math> || polynomial || <math>\mathcal{O}(n^7)</math>
|-
| <math>15 \cdot 8^n + 3 \cdot n^2</math> || exponentiell || <math>\mathcal{O}(8^n)</math>
|}

== Grafische Darstellung der Laufzeiten ==

Das folgende Diagramm veranschaulicht, wie sich die benötigte Zeit (Laufzeit) bei steigender Eingabemenge (Space/n) in den unterschiedlichen Komplexitätsklassen verhält.

<html>
<svg width="700" height="500" viewBox="0 0 700 500" xmlns="http://www.w3.org/2000/svg">
<rect x="0" y="0" width="700" height="500" fill="#ffffff" />

<line x1="80" y1="420" x2="650" y2="420" stroke="#333" stroke-width="2" />
<line x1="80" y1="420" x2="80" y2="50" stroke="#333" stroke-width="2" />

<text x="365" y="450" text-anchor="middle" font-family="sans-serif" font-weight="bold" fill="#555">Eingabegröße (n) / Data Input</text>
<text x="50" y="235" text-anchor="middle" transform="rotate(-90 50 235)" font-family="sans-serif" font-weight="bold" fill="#555">Laufzeit / Time</text>

<path d="M 80 350 L 650 350" fill="transparent" stroke="#7f8c8d" stroke-width="3" />
<text x="610" y="340" fill="#7f8c8d" font-family="sans-serif" font-weight="bold" font-size="16">O(1)</text>

<path d="M 80 420 Q 200 280 650 250" fill="transparent" stroke="#c0392b" stroke-width="3" />
<text x="600" y="240" fill="#c0392b" font-family="sans-serif" font-weight="bold" font-size="16">O(log n)</text>

<path d="M 80 420 Q 300 250 650 150" fill="transparent" stroke="#27ae60" stroke-width="3" />
<text x="610" y="140" fill="#27ae60" font-family="sans-serif" font-weight="bold" font-size="16">O(√n)</text>

<path d="M 80 420 L 550 50" fill="transparent" stroke="#2980b9" stroke-width="3" />
<text x="510" y="45" fill="#2980b9" font-family="sans-serif" font-weight="bold" font-size="16">O(n)</text>

<path d="M 80 420 Q 350 350 420 50" fill="transparent" stroke="#8e44ad" stroke-width="3" />
<text x="430" y="60" fill="#8e44ad" font-family="sans-serif" font-weight="bold" font-size="16">O(n²)</text>

<path d="M 80 420 Q 250 350 280 50" fill="transparent" stroke="#f1c40f" stroke-width="3" />
<text x="290" y="60" fill="#f39c12" font-family="sans-serif" font-weight="bold" font-size="16">O(n³)</text>

<path d="M 80 420 Q 180 350 190 50" fill="transparent" stroke="#5dade2" stroke-width="3" />
<text x="200" y="60" fill="#3498db" font-family="sans-serif" font-weight="bold" font-size="16">O(n!)</text>

</svg>
</html>
[[Kategorie:Programmierung]]
[[Kategorie:AHR_I_Informatik_LK]]

O-Notation - Versionsgeschichte