# Portabilitaet: UNIVERSAL
# Zuletzt validiert: 2026-01-28 (Gemini)
# Naechste Pruefung: 2027-01-28
# Quellen: [informatik/algorithmen/README.txt]

ALGORITHMISCHE KOMPLEXITAET (BIG-O)
===================================

Stand: 2026-01-28

WAS IST KOMPLEXITAET?
---------------------
Die Komplexitaetsanalyse beschreibt, wie Speicherbedarf (Space Complexity) oder Laufzeit (Time Complexity) eines Algorithmus mit wachsender Eingabegroesse (n) ansteigen. Es geht nicht um Sekunden, sondern um Wachstumsraten.

DIE BIG-O NOTATION (LANDAU-SYMBOLE)
-----------------------------------
Die "O-Notation" beschreibt das "Worst Case"-Szenario (Obergrenze).

### O(1) - Konstant
Die Laufzeit bleibt gleich, egal wie gross n ist.
- Beispiel: Zugriff auf ein Array-Element `arr[5]`.

### O(log n) - Logarithmisch
Die Laufzeit waechst sehr langsam. Bei Verdopplung von n kommt nur ein Schritt dazu.
- Typisch fuer: Binaere Suche, Divide & Conquer.
- Beispiel: Suche im Telefonbuch (in der Mitte aufschlagen).

### O(n) - Linear
Die Laufzeit waechst proportional zu n.
- Beispiel: Iteration durch eine Liste. "Finde Max-Wert in unsortierter Liste".

### O(n log n) - Linearithmisch
Standard fuer effiziente Sortierverfahren.
- Beispiel: Merge Sort, Quick Sort, Heap Sort.

### O(n^2) - Quadratisch
Laufzeit waechst im Quadrat. Bei doppelter Eingabe vierfache Zeit.
- Typisch fuer: Verschachtelte Schleifen (`for x in arr: for y in arr:`).
- Beispiel: Bubble Sort.

### O(2^n) - Exponentiell
Laufzeit explodiert. Schon bei kleinen n unbrauchbar.
- Beispiel: Brute-Force Loesung des Traveling Salesman Problems, rekursive Fibonacci ohne Memoisation.

PRAXIS-BEISPIELE (PYTHON)
-------------------------

```python
# O(1)
def get_first(arr):
    return arr[0]

# O(n)
def sum_list(arr):
    total = 0
    for x in arr:
        total += x
    return total

# O(n^2)
def print_pairs(arr):
    for i in arr:
        for j in arr:
            print(i, j)
```

WARUM IST DAS WICHTIG?
----------------------
Fuer n=10 ist der Unterschied egal.
Fuer n=1.000.000:
- O(n): 1 Sekunde
- O(n^2): 11 Tage
- O(2^n): Universum endet vorher.

SIEHE AUCH
----------
wiki/informatik/algorithmen/README.txt
wiki/informatik/datenstrukturen/README.txt
