/ Algorithmen & Komplexität

Rekursionstiefe Binärraum

Maximale Rekursionstiefe bei halbierender Teilung des Problems: Tiefe = ⌊log₂(n)⌋. Begrenzt den benötigten Stack.

01 · Eingabe

Rekursionstiefe Binärraum berechnen

Maximale Rekursionstiefe bei halbierender Teilung des Problems: Tiefe = ⌊log₂(n)⌋. Begrenzt den benötigten Stack.

Lösen für

Tiefe = ⌊log₂(n)⌋

n Problemgröße

Worum geht es?

Bei Algorithmen, die ein Problem in halbierenden Schritten zerlegen (binäre Suche, Merge Sort, Quick Sort, Tree-Traversals), ergibt sich die Rekursionstiefe zu ⌊log₂(n)⌋. Sie bestimmt, wie viele Stack-Frames im Speicher verschachtelt liegen.

Die Abrundung beschreibt die maximale Anzahl voller Halbierungen, bevor der Restbereich auf ein Element zusammenfällt. Mehr Tiefe wäre nicht möglich, weil ein Bereich der Größe 1 nicht weiter halbiert werden kann.

Die Formel

Formel Rekursionstiefe

Tiefe = ⌊log₂(n)⌋

Umstellung:
    n = 2^Tiefe

Die Variablen

Symbol	Bedeutung	Einheit	Erklärung
n	Problemgröße	—	Größe des zu teilenden Bereichs.
Tiefe	Rekursionstiefe	—	Maximale Rekursionstiefe.

Minimal-Beispiel

n = 1024:

Rechnung Stack-Tiefe

Tiefe = ⌊log₂(1024)⌋
      = 10

Praxis-Beispiele

Beispiel 1 — Merge Sort auf 1 Mio. Elementen

Rechnung Stack-Frames

Tiefe = ⌊log₂(1 000 000)⌋
      = ⌊19,93⌋
      = 19

→ maximal 19 Stack-Frames gleichzeitig aktiv.

Beispiel 2 — Stack-Limit ausreizen

Ein Embedded-System erlaubt maximal 12 Stack-Frames pro Aufruf-Kette. Wie groß darf n werden?

Rechnung Maximalgröße

n = 2^12
  = 4096

Beispiel 3 — Tail-Recursion ersparen

Halbierende Rekursion mit n = 10⁹:

Rechnung Großer Bereich

Tiefe = ⌊log₂(10⁹)⌋
      = 29 Frames

Linear-rekursiv wären es 10⁹ Frames — Stack-Overflow.
Halbierung macht den Unterschied.