Beperkingen lezen en complexiteit kiezen

Elke opgave vermeldt limieten voor n en de waarden. Die randvoorwaarden vertellen je vaak stilletjes welke complexiteit de opsteller verwacht. 🔍

Zoek voordat je iets ontwerpt de grootste n in de randvoorwaarden. De grootte van n bepaalt of je kwadratische, lineaire of logaritmische tijd nodig hebt.

Wanneer n hoogstens 20 is, past zelfs uitputtend zoeken met exponentiële tijd. Kleine limieten nodigen je uit om elke combinatie zonder zorgen te proberen.

Als n een paar honderd bereikt, slaagt een oplossing met O(n^3) nog steeds. Driedubbele lussen of eenvoudige dynamische programmering over paren zijn hier prima.

Rond n = 5000 mik je op O(n^2). Geneste lussen over de array kosten ongeveer 2,5 keer 10^7 stappen, wat nog binnen het budget past.

Wanneer n 10^5 of 10^6 bereikt, heb je O(n log n) of O(n) nodig. Sorteren, prefixsommen en twee aanwijzers worden dan je standaardgereedschap.

Als n een miljard is, houdt geen lus over n het vol. Je moet O(log n) of O(1) gebruiken, met wiskunde of binair zoeken naar het antwoord.

Randvoorwaarden voor waarden zijn ook belangrijk. Grote getallen waarschuwen in andere talen voor overloop en kunnen wijzen op rekenen modulo een getal.

Opgaven met meerdere testgevallen begrenzen vaak de som van n en niet elke n afzonderlijk. Lees dit zorgvuldig, want het bepaalt hoe groot je lussen veilig mogen zijn.

Kies op basis van n de gewenste complexiteit en kies daarna een algoritme dat die haalt. n het ontwerp laten sturen is beter dan gokken en later herschrijven.

Houd deze tabel in je hoofd. De koppeling van randvoorwaarden aan complexiteit verandert een snelle blik op de limieten tijdens wedstrijden in een direct plan.

Je leest randvoorwaarden nu als doel: kleine n staat uitputtend zoeken toe, 10^5 vereist n log n en 10^9 vraagt om logaritmische tijd of wiskunde. Laat n de aanpak kiezen. 🗺️