De vuistregel van 10^8

Een typische onlinebeoordelaar voert ongeveer 10^8 eenvoudige bewerkingen per seconde uit. Dat getal is je budget voor het hele programma. 💡

Vermenigvuldig je aantal bewerkingen met het werk per stap en vergelijk dat met de tijdslimiet. Als het aantal stappen binnen het budget blijft, slaag je waarschijnlijk.

Een O(n)-scan over n = 10^6 bestaat uit slechts een miljoen stappen, ruim onder het budget. Lineaire oplossingen slagen bijna altijd met gemak.

Voor n = 10^6 bestaat een sortering met O(n log n) uit ongeveer 2 keer 10^7 stappen. Dat past nog ruim binnen het budget van één seconde, dus sorteren is zelden het knelpunt.

Een aanpak met O(n^2) bereikt het budget rond n = 10^4, wanneer die 10^8 stappen kost. Daarna begint een kwadratische aanpak de tijdslimiet te overschrijden.

Een oplossing met O(n^3) houdt het slechts vol tot ongeveer n = 500. Als je dat tot de derde macht verheft, krijg je ongeveer 10^8 stappen: precies de grens van het budget.

O(2^n) verdubbelt bij elke stap en werkt daarom alleen voor heel kleine n van ongeveer 20 tot 25. Daarna explodeert het aantal bewerkingen voorbij 10^8.

Python is per stap trager, dus beschouw het budget bij krappe lussen als ongeveer 10^7. Wees voorzichtig wanneer de grenzen twijfelachtig aanvoelen.

De regel van 10^8 telt eenvoudige stappen. Zwaar werk binnen een lus, zoals tekenreeksen opbouwen, voegt een constante factor toe die je werkelijke budget kleiner maakt.

De tijdslimiet is vaak 1 of 2 seconden. Een limiet van 2 seconden verdubbelt je budget ongeveer, waardoor je iets meer ruimte krijgt.

Vul n altijd eerst in je complexiteit in en vergelijk die met 10^8. Deze snelle redelijkheidscontrole voorkomt dat je een gedoemde oplossing codeert.

Je koppelt bewerkingen nu aan tijd: ongeveer 10^8 per seconde. Lineair en n log n zijn veilig, kwadratisch heeft een bovengrens rond 10^4 en je controleert dit voordat je gaat coderen. ✅