0Pricing
Coding Interview Prep · Lektion

Big-O-Notation von Grund auf

Verstehen Sie, warum asymptotisches Wachstum wichtig ist, wie Konstanten und Terme niedrigerer Ordnung entfallen und wie Sie Big-O auf einen Blick lesen.

Big-O-Notation von Grund auf ist eine kostenlose Coding Interview Prep-Lektion auf CoddyKit. Dies ist Lektion 1 von 4. Du kannst die komplette Lektion unten kostenlos lesen – dann übst du sie direkt im Browser mit einem integrierten Code-Editor und einem KI-Tutor rund um die Uhr. Sie ist Teil des Coding Interview Prep-Lernpfads, und dein Fortschritt wird über Web und CoddyKit-App synchronisiert. Der Coding Interview Prep-Kurs umfasst insgesamt 4 Lektionen.

Warum die Effizienz von Algorithmen messen?

Zwei Programme können beide korrekt sein, aber eines ist im Handumdrehen fertig, während das andere stundenlang läuft. Die Zeitkomplexität beschreibt, wie die Laufzeit mit wachsender Eingabegröße zunimmt.

# O(n) approach
def find_max_linear(nums):
    m = nums[0]
    for n in nums:
        if n > m: m = n
    return m

# O(n^2) approach (unnecessary double loop)
def find_max_quadratic(nums):
    for i in range(len(nums)):
        is_max = all(nums[i] >= nums[j] for j in range(len(nums)))
        if is_max: return nums[i]

print(find_max_linear([3, 1, 4, 1, 5, 9]))  # 9

Big-O: Asymptotische obere Schranke

Big-O beschreibt die obere Schranke dafür, wie stark die Kosten im schlechtesten Fall wachsen. Der entscheidende Trick: Lassen Sie Konstanten und kleinere Terme weg, denn bei großen Eingaben zählt nur der dominante Term. Sehen Sie sich den Code an.

# T(n) = 3n^2 + 5n + 100 is O(n^2)
# because the n^2 term dominates for large n

# T(n) = 2n + 1000 is O(n)
# the constant 1000 becomes negligible

# Rule: drop constants and lower-order terms
# 5n^3 + 2n^2 + n + 1  =>  O(n^3)
# 100 * log(n) + n      =>  O(n)
print('O(n^2) example: counting iterations')
n = 1000
count = sum(1 for i in range(n) for j in range(n))
print(count)  # 1_000_000 = n^2

Häufige Komplexitätsklassen

Von der schnellsten zur langsamsten: O(1), O(log n), O(n), O(n log n), O(n^2), O(2^n), O(n!). Wenn Sie diese kennen, können Sie schon vor dem Schreiben einer einzigen Zeile den passenden Ansatz wählen.

import math

n = 1000
print(f'O(1):       {1}')
print(f'O(log n):   {int(math.log2(n))}')
print(f'O(n):       {n}')
print(f'O(n log n): {int(n * math.log2(n))}')
print(f'O(n^2):     {n**2}')
# O(2^n) for n=1000 is astronomically large
# O(n!) even larger

Konstanten weglassen: Warum das wichtig ist

Ob Sie 5n oder 2n Schritte ausführen: Beides ist O(n) — Konstanten hängen von der Hardware ab, nicht vom Algorithmus. Big-O lässt sie weg, damit Sie die Skalierung auf derselben Grundlage vergleichen.

# Both are O(n) — different constants
def count_a(n):
    total = 0
    for i in range(n):   # n ops
        total += 1
    for i in range(n):   # n ops
        total += 1
    return total  # T(n) = 2n  =>  O(n)

def count_b(n):
    total = 0
    for i in range(5 * n):  # 5n ops
        total += 1
    return total  # T(n) = 5n  =>  O(n)

print(count_a(10), count_b(10))  # 20 50

Best-, Average- und Worst-Case

Big-O beschreibt den Worst-Case; Omega den Best-Case; Theta ist eine enge Schranke für beide. Wenn ein Interviewer nach der „Komplexität“ fragt, ist damit fast immer der Worst-Case gemeint.

def linear_search(nums, target):
    for i, n in enumerate(nums):
        if n == target:
            return i  # best case: target at index 0 => O(1)
    return -1         # worst case: not found => O(n)

# Best case O(1): target is first element
print(linear_search([5,1,2,3], 5))   # 0

# Worst case O(n): target not in list
print(linear_search([1,2,3,4], 9))   # -1

O(log n): Den Suchraum halbieren

Ein Algorithmus ist O(log n), wenn er die Eingabe in jedem Schritt halbiert, wie bei der binären Suche. Selbst bei einer Milliarde Elementen sind das nur etwa 30 Schritte — unglaublich schnell. Sehen Sie sich den Code an.

def binary_search(arr, target):
    lo, hi = 0, len(arr) - 1
    steps = 0
    while lo <= hi:
        steps += 1
        mid = (lo + hi) // 2
        if arr[mid] == target:
            return mid, steps
        elif arr[mid] < target:
            lo = mid + 1
        else:
            hi = mid - 1
    return -1, steps

import math
arr = list(range(1000))
idx, s = binary_search(arr, 999)
print(f'Found at {idx} in {s} steps (log2(1000)~={math.log2(1000):.1f})')

O(n log n): Untere Schranke beim Sortieren

Jedes vergleichsbasierte Sortierverfahren benötigt im Worst-Case mindestens O(n log n) — eine echte mathematische untere Schranke. Sortieren und anschließendes Durchlaufen ergibt also insgesamt O(n log n), nicht O(n^2). Der Code zeigt Merge Sort.

# Merge sort: O(n log n)
def merge_sort(arr):
    if len(arr) <= 1:
        return arr
    mid = len(arr) // 2
    left  = merge_sort(arr[:mid])
    right = merge_sort(arr[mid:])
    return merge(left, right)

def merge(a, b):
    res, i, j = [], 0, 0
    while i < len(a) and j < len(b):
        if a[i] <= b[j]: res.append(a[i]); i+=1
        else:             res.append(b[j]); j+=1
    return res + a[i:] + b[j:]

print(merge_sort([5,2,8,1,9,3]))  # [1,2,3,5,8,9]

Amortisierte Komplexität

Die amortisierte Analyse mittelt die Kosten über viele Operationen. Pythons append ist amortisiert O(1): normalerweise sofort erledigt, während die seltene Größenänderung mit O(n) auf alle append-Aufrufe verteilt wird.

# Dynamic array append is O(1) amortised
import sys

lst = []
capacities = []
for i in range(16):
    lst.append(i)
    capacities.append(sys.getsizeof(lst))

# Size jumps show reallocation events
for i, c in enumerate(capacities):
    if i > 0 and capacities[i] != capacities[i-1]:
        print(f'Realloc at i={i}, new size={c} bytes')

Komplexität im Code erkennen

Eine schnelle Faustregel: Zählen Sie die Schleifen. Eine Schleife ist O(n), zwei verschachtelte Schleifen sind O(n^2), eine Schleife, die halbiert, ist O(log n). Unabhängige Durchläufe werden addiert; nur verschachtelte Schleifen werden multipliziert. Sehen Sie sich den Code an.

# Two independent passes: O(n) + O(n) = O(n)
def two_passes(nums):
    total = sum(nums)           # O(n)
    mean = total / len(nums)
    diffs = [abs(n - mean) for n in nums]  # O(n)
    return max(diffs)           # O(n)
# Overall: O(n) -- NOT O(n^2)

# Nested loops: O(n) * O(n) = O(n^2)
def all_pairs(nums):
    pairs = []
    for i in range(len(nums)):       # O(n)
        for j in range(i+1, len(nums)): # O(n)
            pairs.append((nums[i], nums[j]))
    return pairs  # O(n^2)

Grundlagen der Speicherkomplexität

Die Speicherkomplexität erfasst den zusätzlichen Speicher, den Sie über die Eingabe hinaus verwenden. Eine In-Place-Umkehrung benötigt O(1); eine Hash-Map O(n). Wenn Sie Zeit gegen Speicher tauschen, geben Sie immer beides an.

# O(1) space: reverse in-place
def reverse_inplace(arr):
    l, r = 0, len(arr) - 1
    while l < r:
        arr[l], arr[r] = arr[r], arr[l]
        l += 1; r -= 1

# O(n) space: create reversed copy
def reverse_copy(arr):
    return arr[::-1]

a = [1, 2, 3, 4, 5]
reverse_inplace(a)
print(a)  # [5, 4, 3, 2, 1]

Im Interview über Komplexität sprechen

Nennen Sie die Komplexität immer von sich aus: „Zeitkomplexität O(n log n), Speicherkomplexität O(n).“ Bieten Sie anschließend eine schnellere Option an. Diese Gewohnheit signalisiert echte Seniorität.

# Example of explaining complexity step by step
def two_sum(nums, target):
    # O(n) time: one pass through nums
    # O(n) space: hash map stores up to n elements
    seen = {}  # value -> index
    for i, n in enumerate(nums):
        complement = target - n
        if complement in seen:   # O(1) lookup
            return [seen[complement], i]
        seen[n] = i
    return []

print(two_sum([2, 7, 11, 15], 9))  # [0, 1]

Schnelltest

Schnelltest — zeigen Sie, was Sie über Big-O und Komplexitätsklassen aufgenommen haben. Eine Frage, Sie schaffen das. 🎯

Zusammenfassung der Lektion

Zusammenfassung: Big-O beschreibt das Wachstum im Worst-Case, wobei Konstanten weggelassen werden. Sie kennen die Klassen von O(1) bis O(n!), und unabhängige Schleifen werden addiert, während verschachtelte Schleifen multipliziert werden.

Häufig gestellte Fragen

Ist die Lektion „Big-O-Notation von Grund auf“ kostenlos?

Ja — der vollständige Text von „Big-O-Notation von Grund auf“ ist hier im Web kostenlos zu lesen. Um sie interaktiv zu üben (integrierter Code-Editor und 24/7 KI-Tutor) und den Rest des Coding Interview Prep-Kurses freizuschalten, upgrade auf CoddyKit PRO. Der Coding Interview Prep-Kurs umfasst insgesamt 4 Lektionen.

Was lerne ich in „Big-O-Notation von Grund auf“?

Verstehen Sie, warum asymptotisches Wachstum wichtig ist, wie Konstanten und Terme niedrigerer Ordnung entfallen und wie Sie Big-O auf einen Blick lesen. Du übst Coding Interview Prep mit praktischem Code, den du direkt im Browser ausführst, und ein 24/7 KI-Tutor beantwortet deine Fragen während du die Lektion bearbeitest.

Brauche ich Erfahrung, um Coding Interview Prep zu starten?

Keine Vorkenntnisse erforderlich. Coding Interview Prep auf CoddyKit ist für Anfänger bis fortgeschrittene Lernende strukturiert, sodass du hier starten oder von Anfang an beginnen und in deinem eigenen Tempo voranschreiten kannst. Dies ist Lektion 1 von 4.

Wie lange dauert die Lektion „Big-O-Notation von Grund auf“?

Die meisten CoddyKit-Lektionen dauern etwa 5–10 Minuten. Jede ist kompakt und interaktiv, sodass du stetig Fortschritte machst und genau dort weitermachst, wo du aufgehört hast – im Web und in der App.

Kann ich in dieser Coding Interview Prep-Lektion Code schreiben und ausführen?

Ja. Jede Coding Interview Prep-Lektion enthält einen integrierten Code-Editor, sodass du echten Code direkt in deinem Browser schreibst und ausführst und sofort KI-Feedback erhältst — ohne lokale Einrichtung erforderlich.

Alle Lektionen in diesem Kurs

  1. Big-O-Notation von Grund auf
  2. Schleifen und verschachtelte Schleifen analysieren
  3. Rekursion und die Rekursionsbaum-Methode
  4. Platzkomplexität und Abwägungen
← Zurück zu Coding Interview Prep