Forestil dig det her: Det er lørdag. Klokken er 22.13. Du ligger i sofaen, børnene er puttet oven på fredagstamtam ("Disney sjov" for dig med voksne børn). Du er kun halvt vågen, og et sted bag din pande dukker en tanke op: Speltboller. For dem har du jo lovet hele familien til morgenbordet i morgen. Du griber telefonen, åbner Google og skriver: "Nemme og hurtige speltboller".
Et par sekunder senere har du en liste af anbefalinger, opskrifter og anmeldelser. Men midt i din scrolling ned af listen, stopper du op og spørger: "Hvordan i alverden ved Google, hvad jeg leder efter? Og hvordan finder den det så hurtigt?". Okay, det kan godt være, du ikke tænker præcis sådan, men følg lige med alligevel. Det kan jo være du bliver klogere.

Her begynder min rejse. Ikke mod speltboller, desværre – men mod noget, de færreste har hørt om, og som for mange, måske kan lyde som lidt støvet matematik: Store O-notationen. Exciting, yes men hæng på. Det her er ikke kun for matematiknørder og tech bros. Det handler også om dig, dit strømforbrug, og din hverdag – og ja, klimaet.

Ikke de fucking algoritmer igen... Vi hører det hele tiden. Algoritmerne styrer, hvad vi ser på TikTok, hvem vi matcher med på Tinder, og hvornår vores pakker bliver leveret. Men hvad er en algoritme egentlig? Det er trin-for-trin-instruktioner, som computeren følger for at løse en opgave. Det kan være at finde en patient i en journalsamling. Eller at matche dig med en potentiel partner, du alligevel aldrig hører tilbage fra. Men ikke alle instruktioner (læs algoritmer) er lige gode. Nogle er hurtige og effektive. Andre er det digitale svar på at tage bussen i myldretiden, hvor chaufføren også lige skal ud og slå en streg midtvejs. Det er her, Store O kommer ind i billedet.

Store O-notationen er matematikens måde at spørge: "Okay, men hvad sker der, når mængden af data bliver rigtig, rigtig stor?"

I fagsproget siger man, at store O beskriver asymptotisk adfærd. Du husker asymptoten fra matematik på gym, som den linje en graf vil nærme sig, når x går mod uendelig. Store O beskriver altså, hvordan en algoritmes ydeevne f.eks. tid udvikler sig, når datamængden går mod at blive uendelig stor. Når man netop taler om tid, så kaldes dette for en algoritmes tidskompleksitet.

Og nej, vi når sjældent helt derud i praksis. Men idéen er, at man vil forstå, hvordan en algoritme opfører sig under pres, og i worst-case. For det er let nok at være effektiv, når datamængden er lille, men straks værre når den vokser.

Så spørger du sikkert, "ja men, hvordan ser de her algoritmer så ud?", og nu skal du bare høre. Fordi jeg er en kæmpe nørd, og har en baggrund i webudvikling, så har jeg lavet et lille spil, som du kan prøve. Her får du visualiseret tre forskellige søgealgoritmer, med hver sin tidskompleksitet.
Prøv at vælge en søgealgoritme og et tal du gerne vil finde og tryk start.

Når mængden af data er lille, er forskellen mellem de tre algoritmer minimal. Men når denne vokser – til millioner eller milliarder – så bliver det pludselig vigtigt, hvilken algoritme du vælger.

På den anden side, så kan man også komme til at vælge en algoritme, som er alt for avanceret til behovet. Altså lidt som at tage metroen til Kastrup, gå i gennem security, bande over at flyet er forsinket, og så endelig tage flyet bare for at komme til Netto, fremfor at gå de sølle 450 meter… Det er det, man kalder for overhead, og beskriver de trin som er nødvendige for algoritmen for f.eks. at kunne finde det rigtige tal, men som ikke er en del af selve søgningen.

For at undersøge dette lidt nærmere, har jeg foretaget et lille eksperiment, for at finde ud af hvor meget det egentligt betyder. Her sammenlignede jeg de tre ovennævnte søgealgoritmer på forskellige mængder data, og under forskellige omstændigheder. Det første jeg undersøgte, var for et usorteret datasæt. Så tænker du nok "men hvordan det? Sagde du ikke at binær og Jump-Søgning ikke virkede for usorteret data?" (Spoiler til dig, der endnu ikke har spillet, spillet... Du kan nå det endnu). Jo du har helt ret, men for at komme dette til livs, sorterede jeg først datamængden med to forskellige sorteringsalgoritmer, hhv. Insertion Sort og TimSort. Lad os lige starte med at se på resultaterne.

Sammenligning af søgealgoritmer på usorteret datasæt
Eksperimentet er gentaget 100 gange for at sikre konsistente resultaterKilde: Resultatafsnittet som du kan læse nedenfor

Tallene taler deres tydelige sprog: Når vi forsøger at finde en nål i en digital høstak, kan den tilsyneladende mest primitive metode – nemlig lineær søgning – faktisk være det hurtigste valg. Det lyder måske kontraintuitivt. For hvorfor skulle den strategi, hvor man tålmodigt kigger på hvert eneste element ét ad gangen, slå de mere sofistikerede metoder som binær- eller jump-søgning?

Forklaringen ligger i forarbejdet. Både binær og jump-søgning kræver, at datasættet først sorteres, før man kan udnytte algoritmernes smarte metoder. Sorteringen gør dog en verden til forskel, for sorteringen tager også tid. Lad os for et øjeblik se nærmere på den:

• Insertion Sort: er hvor man kigger på ét element i datasættet ad gangen, og vurderer om det er større eller mindre end det tidligere element. Det er præcis det samme som hvis man sorterer spillekort. Her trækker man også ét kort ad gangen, og tjekker om det skal være før eller efter det tidligere kort. Insertion Sort har en tidskompleksitet, der kaldes kvadratisk tid, og betyder at antallet af skridt vokser med kvadratet af inputmængden, hvis du altså kan huske lidt fra gymnasiematematik.
• TimSort: er en optimeret version af Insertion Sort. Den holder øje med om dele af datasættet allerede er sorteret – sådan nogle kalder man for runs. I stedet for bare at sortere ét element ad gangen, som i klassisk Insertion Sort, så finder TimSort disse allerede sorterede bidder og bygger videre på dem. Det svarer lidt til, hvis du opdager, at nogle af dine spillekort allerede ligger i rækkefølge, og i stedet for at starte helt forfra, bruger du det til din fordel. Det gør TimSort langt hurtigere, især hvis datasættet i forvejen er næsten sorteret. På fagsprog kalder man dette logaritmisk-lineær tidskompleksitet.

Helt afgørende er, at sorteringen – især med en simpel algoritme som Insertion Sort – tager langt mere tid end selve søgningen. I forsøget her ses det tydeligt: Ved 10.000 elementer tager en binær søgning blot 0,002 millisekunder. Men sorteringen med Insertion Sort sluger hele 0,86 sekunder. Det virker måske ikke som så meget, men det gør hele operationen næsten 5.000 gange langsommere end den gode gamle lineære metode, som bare tygger sig igennem listen uden at kræve nogen forberedelse overhovedet.

Det bliver dog mere interessant, når vi skifter til en mere effektiv sorteringsalgoritme. TimSort, der bruges i mange moderne programmeringssprog (bl.a. Python), sorterer data med væsentligt lavere tidsforbrug, og pludselig begynder de mere avancerede søgestrategier at give mening. Allerede ved 5.000 elementer bliver det tydeligt: Her overhaler binær søgning med TimSort lineær søgning – også når sorteringstiden medregnes.
Men pointen står tilbage: I det praktiske arbejde med algoritmer er det sjældent kun selve søgningen, der tæller – det er hele pakken, inklusive forarbejdet. Og her kan teoriens elegante kompleksiteter hurtigt blive overhalet af virkelighedens støj.

Forestil dig, at du allerede har styr på dine data – alt er pænt og sorteret. Nu kan dine søgealgoritmer springe direkte til opgaven. Og her sker der noget interessant: Når mængden af data er meget lille, er det stadig den simple lineære søgning, der løber med sejren.

Sammenligning af søgealgoritmer på sorteret datasæt
Eksperimentet er gentaget 100 gange for at sikre konsistente resultaterKilde: Resultatafsnittet som du kan læse nedenfor

Forklaringen? Den er overraskende logisk. Lineær søgning er ekstremt enkel: Gå fra start til slut, kig ét sted ad gangen. Ingen spring, ingen struktur – bare fuld fart frem. Det gør, at den er lynhurtig ved små datasæt. Så selv om den vokser lineært med antallet af elementer, så mærker vi det slet ikke, før datamængden bliver større end cirka 10.

De mere avancerede algoritmer – som binær og jump-søgning – er bygget til det lange løb. Binær søgning er noget mere effektiv, men skal bruge lidt ekstra opsætning, der først rigtig giver gevinst ved større datasæt. Jump-søgning klarer sig endnu dårligere i starten. Den hopper igennem datasættet i blokke, og det er smart, men kun når der er noget at hoppe hen over. Den har en lidt tungere start og lider under sit høje overhead.

Men billedet ændrer sig hurtigt, når vi kigger på større datasæt – f.eks. når elementerne er over 120 – begynder jump-søgning faktisk at slå den lineære søgning, som det kan ses på grafen. Men det er først, når vi når de helt store datasæt, at binær søgning virkelig viser muskler. Når datamængden er på 100.000 elementer, er den ikke bare hurtigere – den er vanvittigt hurtig. Vi taler næsten 2.000 gange hurtigere end lineær søgning og 48 gange hurtigere end jump-søgning. Det sker, fordi binær søgning udnytter strukturen i datasættet optimalt og minimerer antallet af operationer, der skal udføres. Den "tænker sig om" og halverer mængden af data, den skal tjekke, igen og igen.

Og så er vi tilbage ved pointen: Når din Google-søgning efter opskrifter på speltboller går så hurtigt, så hænger det sammen med den søgealgoritme, der er i funktion. Valget af algoritme handler ikke bare om, hvad der ser smartest ud på papiret. Det handler om at kende konteksten. Hvor meget data har du? Er det sorteret? Og hvor hurtigt skal det gå? Det korte svar? For små mængder data: hold det simpelt. For store mængder: brug hjernen – eller i det her tilfælde, binær søgning.

Og nu til noget, vi ikke taler nok om, som nogle vil mene: klimaet. Vi forbinder ikke nødvendigvis software med klimabelastning. Koden virker jo usynlig. Den larmer ikke. Den ryger ikke. Men det gør datacentre. Hver gang en algoritme bliver kørt, bruges der elektricitet. Og selvom det kun er en mikroskopisk mængde strøm for én enkelt søgning, så løber det op, når det sker milliarder af gange i sekundet – globalt. Ineffektive algoritmer betyder, at computeren skal arbejde mere. Mere arbejde betyder mere strøm. Og mere strøm betyder – i mange tilfælde – mere CO₂. Et studie publiceret i Oxford Open Energy (2023) fremhæver, at ineffektivt softwaredesign er en væsentlig driver for den stigende klimabelastning fra IT-sektoren, som i dag står for mere end 3 % af de globale CO₂-udledninger, og dermed overstiger udledningerne fra civil luftfart. Og her snakker vi ikke kun om strømslugende kryptomining – men også helt almindelige applikationer, som vi alle bruger. Et eksempel: Google foretager over 150.000 søgninger – i sekundet. Hvis hver af de søgninger bare tager én mikroskopisk brøkdel af et sekund længere end nødvendigt, fordi man bruger en dårlig algoritme, så betyder det i skala, flere tusinde tons CO₂ om året. Derfor er Store O ikke bare nørdet teori. Store O fortæller os, hvor meget data en algoritme effektivt kan bearbejde, og hvornår man bør skifte til en anden algoritme. Derfor er Store O en rettesnor for, hvordan vi bygger bæredygtig software.

… så husk, at nogen har truffet et valg. Et valg om, hvordan noget skulle søges, sorteres eller matches. Og det valg har en konsekvens – ikke bare for din tålmodighed, men måske også for klimaet. Store O-notationen hjælper programmører, ingeniører og matematikere med at tage de valg på en mere oplyst måde. Den er som den lille stemme i baghovedet, der siger: “Er det her virkelig den smarteste måde at gøre det på?” Og selvom du aldrig selv kommer til at skrive en algoritme, er det alligevel værd at vide, hvordan den arbejder bag kulisserne – både for og imod dig. Også når du bare skal noget så simpelt som at finde en opskrift på speltboller.