Einschränkungen lesen und Komplexität wählen

Jede Aufgabe enthält Grenzen für n und die Werte. Diese Constraints verraten Ihnen oft unauffällig, welche Komplexität die Aufgabensteller erwarten. 🔍

Bevor Sie etwas entwerfen, suchen Sie das größte n in den Constraints. Die Größe von n entscheidet, ob eine quadratische, lineare oder logarithmische Lösung erforderlich ist.

Wenn n höchstens 20 ist, passt selbst eine exponentielle Brute-Force-Lösung. Kleine Grenzen laden dazu ein, jede Kombination ohne Bedenken auszuprobieren.

Wenn n einige Hundert erreicht, besteht eine Lösung mit O(n^3) noch. Dreifach verschachtelte Schleifen oder eine einfache DP über Paare sind hier möglich.

Bei ungefähr n = 5000 sollten Sie O(n^2) anstreben. Verschachtelte Schleifen über das Array benötigen etwa 2,5 mal 10^7 Schritte und passen damit noch in das Budget.

Wenn n 10^5 oder 10^6 erreicht, benötigen Sie O(n log n) oder O(n). Sortieren, Präfixsummen und Two Pointers werden zu Ihren wichtigsten Werkzeugen.

Wenn n eine Milliarde beträgt, hält keine Schleife über n durch. Sie müssen O(log n) oder O(1) erreichen, etwa mit Mathematik oder einer binären Suche nach der Lösung.

Auch die Grenzen der Werte sind wichtig. Große Zahlen warnen in anderen Sprachen vor einem Überlauf und können auf modulare Arithmetik hindeuten.

Bei Aufgaben mit mehreren Tests ist oft die Summe von n begrenzt, nicht jedes einzelne n. Lesen Sie dies sorgfältig, denn dadurch ändert sich, wie groß Ihre Schleifen gefahrlos sein dürfen.

Wählen Sie anhand von n die Zielkomplexität und anschließend einen passenden Algorithmus. Wenn Sie n als Leitfaden für den Entwurf verwenden, müssen Sie später weniger raten und umarbeiten.

Behalten Sie diese Tabelle im Kopf. Die Zuordnung von Constraints zu Komplexitäten macht aus einem kurzen Blick auf die Grenzen während eines Wettbewerbs sofort einen Plan.

Lassen Sie sich von n zur richtigen Komplexität führen.

Sie lesen Constraints jetzt als Zielvorgabe: Kleines n erlaubt Brute Force, 10^5 erfordert n log n und 10^9 verlangt Logarithmen oder Mathematik. Lassen Sie n den Ansatz bestimmen. 🗺️