Du tror to løkker inni hverandre tar dobbelt så lang tid

Handler om: Algoritme

Det er lett å tenke at to løkker etter hverandre og to løkker inni hverandre koster det samme — «det er jo to løkker». Men plasseringen avgjør alt. To løkker ETTER hverandre over n elementer gjør n + n = 2n arbeid (dobbelt). En løkke INNI en annen kjører den indre løkka på nytt for HVERT element i den ytre — n · n = n² arbeid. For n = 1000 er det forskjellen på 2000 og 1 000 000 operasjoner. Veksten er ikke dobbelt, men kvadratisk: dobler du n, firedobles arbeidet i den nøstede løkka.

Eksempel

Du skal finne duplikater i en liste med 1000 navn. Med en nøstet løkke (sammenlign hvert navn med alle andre) blir det rundt 1 000 000 sammenligninger; du tror det «bare er litt tregere» enn å gå gjennom lista én gang, men det er tusen ganger så mye arbeid.

Slik tenker du riktig om det

Si veksten høyt: «for HVER ytre runde gjør jeg ALLE de indre rundene på nytt.» Plasser løkkene etter hverandre (n + n) når du kan, og bruk et ordbok- eller mengde-oppslag i stedet for en indre løkke når du leter etter noe — da går arbeidet fra n² ned til n.