Die 10^8-Faustregel

Ein typischer Online Judge verarbeitet etwa 10^8 einfache Operationen pro Sekunde. Diese Zahl ist Ihr Budget für das gesamte Programm. 💡

Multiplizieren Sie die Anzahl der Operationen mit dem Aufwand pro Schritt und vergleichen Sie das Ergebnis mit dem Zeitlimit. Wenn die Anzahl der Schritte in das Budget passt, bestehen Sie den Test wahrscheinlich.

Ein O(n)-Durchlauf über n = 10^6 umfasst nur eine Million Schritte und liegt damit weit unter dem Budget. Lineare Lösungen bestehen fast immer problemlos.

Für n = 10^6 umfasst eine Sortierung mit O(n log n) etwa 2 mal 10^7 Schritte. Das liegt noch deutlich innerhalb des Budgets für eine Sekunde, daher ist das Sortieren selten der Engpass.

Ein Ansatz mit O(n^2) erreicht das Budget ungefähr bei n = 10^4, wo er 10^8 Schritte benötigt. Darüber beginnt die quadratische Komplexität das Zeitlimit zu überschreiten.

Eine Lösung mit O(n^3) ist nur bis etwa n = 500 praktikabel. Die dritte Potenz davon ergibt ungefähr 10^8 Schritte und liegt damit an der Grenze des Budgets.

O(2^n) verdoppelt sich mit jedem Schritt und funktioniert daher nur für sehr kleine n zwischen etwa 20 und 25. Danach explodiert die Anzahl der Operationen über 10^8 hinaus.

Python ist pro Schritt langsamer. Betrachten Sie das Budget bei engen Schleifen daher eher als 10^7. Seien Sie vorsichtig, wenn die Grenzen knapp erscheinen.

Die Faustregel 10^8 zählt einfache Schritte. Aufwendige Arbeit innerhalb einer Schleife, etwa das Erstellen von Strings, fügt einen konstanten Faktor hinzu, der Ihr tatsächliches Budget verringert.

Das Zeitlimit beträgt häufig 1 oder 2 Sekunden. Ein Limit von 2 Sekunden verdoppelt Ihr Budget ungefähr und verschafft Ihnen etwas mehr Spielraum.

Setzen Sie n immer zuerst in Ihre Komplexität ein und vergleichen Sie das Ergebnis mit 10^8. Dieser kurze Plausibilitätstest bewahrt Sie davor, eine zum Scheitern verurteilte Lösung zu programmieren.

Sie können Operationen jetzt einer Laufzeit zuordnen: ungefähr 10^8 pro Sekunde. Lineare und n-log-n-Lösungen sind sicher, quadratische Lösungen reichen bis etwa 10^4, und Sie prüfen dies vor dem Programmieren. ✅