Operationen mit Big-O zählen
Von konstant bis quadratisch, verständlich erklärt
Operationen mit Big-O zählen ist eine kostenlose Competitive Programming Academy-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 Competitive Programming Academy-Lernpfads, und dein Fortschritt wird über Web und CoddyKit-App synchronisiert. Der Competitive Programming Academy-Kurs umfasst insgesamt 4 Lektionen.
Warum man Operationen zählt
Bei Wettbewerben zählt Geschwindigkeit. Statt die Laufzeit Ihres Codes zu messen, schätzen Sie, wie viele Schritte er benötigt. Diese Schätzung ist seine Zeitkomplexität. 🚀
Big-O kennenlernen
Big-O beschreibt, wie die Anzahl der Operationen wächst, wenn die Eingabegröße n zunimmt. Kleine Details werden ignoriert; im Mittelpunkt steht der vorherrschende Trend.
Konstante Zeit O(1)
Wenn der Aufwand unabhängig von n ist, beträgt die Komplexität O(1). Das Lesen eines Listenelements oder eine Addition dauert immer gleich lange.
x = arr[0]
y = a + bLineare Zeit O(n)
Eine einfache Schleife über n Elemente hat die Komplexität O(n). Verdoppeln Sie die Eingabe, verdoppelt sich ungefähr auch der Aufwand. Das ist der alltägliche Arbeitstyp.
for x in arr:
total += xQuadratische Zeit O(n squared)
Eine Schleife innerhalb einer Schleife über n Elemente hat die Komplexität O(n^2). Für n = 1000 sind das eine Million Schritte, und danach wächst der Aufwand schnell weiter.
for i in range(n):
for j in range(n):
check(i, j)Logarithmische Zeit O(log n)
Wenn jeder Schritt das Problem halbiert, erhalten Sie O(log n). Die binäre Suche erreicht eine Milliarde Elemente mit nur etwa 30 Schritten. ✨
Die Wachstumsskala
Von schnell nach langsam lautet die übliche Reihenfolge: O(1), O(log n), O(n), O(n log n), O(n^2). Je weiter oben, desto besser skaliert die Komplexität.
Konstanten weglassen
Big-O ignoriert konstante Faktoren, daher ist O(2n) einfach O(n). Zwei Durchläufe wachsen weiterhin linear, deshalb ändert der Multiplikator die Komplexitätsklasse nicht.
Nur den größten Term behalten
Wenn sich Terme addieren, zählt nur der am schnellsten wachsende. O(n^2 + n) wird zu O(n^2) vereinfacht, weil n^2 bei wachsendem n deutlich größer als n ist.
Sequentiell oder verschachtelt
Zwei aufeinanderfolgende Schleifen addieren sich zu O(n + n) = O(n). Zwei verschachtelte Schleifen multiplizieren sich zu O(n^2). An der Struktur der Schleifen erkennen Sie den Unterschied.
Mit dem Worst Case beginnen
Bei Wettbewerben wird anhand des schwierigsten Tests bewertet, daher betrachten Sie den Worst Case. Gehen Sie davon aus, dass die Schleife vollständig durchläuft und nicht vorzeitig zurückkehrt.
Schnelltest
Testen Sie jetzt Ihr Gespür für Big-O.
Rückblick
Sie lesen Code jetzt unter dem Gesichtspunkt des Wachstums: O(1), O(n), O(n^2) und O(log n). Lassen Sie Konstanten weg, behalten Sie den größten Term und denken Sie an den Worst Case. 🎯
Häufig gestellte Fragen
Ist die Lektion „Operationen mit Big-O zählen“ kostenlos?
Ja — der vollständige Text von „Operationen mit Big-O zählen“ ist hier im Web kostenlos zu lesen. Um sie interaktiv zu üben (integrierter Code-Editor und 24/7 KI-Tutor) und den Rest des Competitive Programming Academy-Kurses freizuschalten, upgrade auf CoddyKit PRO. Der Competitive Programming Academy-Kurs umfasst insgesamt 4 Lektionen.
Was lerne ich in „Operationen mit Big-O zählen“?
Von konstant bis quadratisch, verständlich erklärt Du übst Competitive Programming Academy 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 Competitive Programming Academy zu starten?
Keine Vorkenntnisse erforderlich. Competitive Programming Academy 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 „Operationen mit Big-O zählen“?
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 Competitive Programming Academy-Lektion Code schreiben und ausführen?
Ja. Jede Competitive Programming Academy-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
- Operationen mit Big-O zählen
- Die 10^8-Faustregel
- Einschränkungen lesen und Komplexität wählen
- Warum TLE auftritt und wie Sie es erkennen