Du tror to løkker inni hverandre tar dobbelt så lang tid
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
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.
Slik ser det ut i kode
Slik gikk det galt
# nostet lokke: n * n = n-i-andre arbeid
for a in navn:
for b in navn:
if a == b:
...Slik fikser du det
# en lokke + oppslag i mengde: n arbeid
sett = set()
for a in navn:
if a in sett: # oppslag er ~konstant, ikke ny lokke
...
sett.add(a)