Hvad er en algoritme?

En algoritme er en trinvis process der skal medføre et bestemt resultat, og som ofte beregnes af en computer. Algoritmen tager noget vilkårlig data, følger en proces for behandling af dataen, og omdanner det til et vilkårligt resultat. En algoritme skal være entydig – dvs. at den kun skal kunne forstås og udføres på én måde. Man kan derfor betragte en algoritme som en opskrift til løsningen af et bestemt problem.

Historien bag

Ordet “algoritme” stammer fra matematikeren, Muḥammad ibn Mūsā al-Khwārizmī, som levede i Bagdad i 800-tallet. Det mest velkendte eksempel på en algoritme, er Euklids algoritme, som er en metode til at beregne den største fælles divisor, dvs. det største tal der går op i to vilkårlige tal. Klik her for at læse mere om Euklids algoritme.

Hvordan laver man en algoritme?

Algoritmer forekommer flere steder i vores hverdag, end man skulle tro, såsom i madopskrifter og brugsanvisninger. Disse eksempler kan dog kun nogenlunde betragtes som algoritmer, da de ofte indeholder instruktioner, som ikke er helt entydige, da det er forventet, at nogle opgaver er et selvfølge, og derfor kan udføres på flere end én måde, f.eks. instrukser som “Tø maden op” eller “Skru bordbenene fast”.

En algoritme skabes ud fra et problem, som man ønsker et resultat på. Derved skal man specificere sit problem før man kan skabe en algoritme. Dette kunne f.eks. være “Hvor mange gange forekommer ordet ‘Gud’ i biblen?” eller “Hvor mange tal går op i 440?”, men algoritmer kan også sagtens være mere komplekse. Man kan f.eks. også skabe algoritmer til at udregne ansattes løn eller udprinte karaktererne for en elev. En algoritme kan betragtes som værende “effektiv”, hvis den kan løse et problem inden for en specifik tidsperiode.

Man kan udtrykke og visualisere en algoritme på mange forskellige brugbare måder for at give andre mennesker et indblik i, hvordan den skal virke. Den simpleste metode er at beskrive den ved hjælp af naturligt sprog, men man kan også visualisere den ved hjælp af bl.a. rute- eller DRAKON-diagrammer.

Computeralgoritmer

Algoritmer bliver hyppigst brugt i forbindelse med programmering, og disse algoritmer kan betragtes som computeralgoritmer. Computeralgoritmer kan skabes ved hjælp af programmeringssprog, som f.eks. Python, JavaScript og PHP. Der findes rigtig mange forskellige programmeringssprog, og mange af dem benytter lignende syntakser og erklæringer til at udtrykke algoritmer.

Lad os sige, at vi har et problem, som er, at vores lampe ikke virker, og vi skal finde en løsning på, hvordan vi får den til at virke. Før at algoritmen bliver programmeret, så er det en god ide, at visualisere problemet. Dette er gjort ved hjælp af et rutediagram, som er vist i nedenstående illustration:

Rutediagrammet illustrerer, hvordan programmet skal reagere på forskellige mulige begivenheder, f.eks. hvis lampens pære ikke virker, så skal pæren udskiftes, men hvis den virker, så skal lampen repareres. Dette kan programmeres i et programmeringssprog ved hjælp af if–else-erklæringer. I nedenstående kodestykke er programmeringssproget, Python, blevet benyttet til at vise, hvordan sådan en algoritme kunne se ud på et helt lavpraktisk niveau:

if 'Tilsluttet Strøm' == False:
    print('Tilslut lampen')
else:
    if 'Virker strømmen' == False:
        print('Udskift pæren')
    else:
        print('Reparer lampe')

Kodestykket er ikke et nøjagtigt vejledende eksempel og behøves ikke at forstås i dybden. Det er blot for at vise, hvordan man går fra et problem, til en visualisering og til sidst til en programmering af algoritmen.

En computeralgoritme siges generelt at være bedre jo mindre trin den bruger på at finde det rigtige resultat, men hertil gælder også andre faktorer, såsom hvor meget computerkraft den bruger. For nogle typer af problemer findes der, så vidt man ved, ikke effektive algoritmer, da de ikke vil være i stand til at give et resultat inden for rimelig tid. Det gælder bl.a. algoritmer til beregning af den korteste rute fra én lokation til en anden.

Sorteringsalgoritmer

En af de mest omtalte problemer inden for computervidenskab er, hvordan en algoritme bedst muligt kan sortere en række elementer i en kronologisk rækkefølge, f.eks. navne eller numre. Mange computerprogrammer benytter sorteringsalgoritmer til en masse forskellige funktioner, som f.eks. når din email skal sorteres fra ældste til nyeste mails, når en hjemmeside sorterer priser på et produkt fra billigste til dyreste, eller når et socialt medie sorterer dit feed med de mest relevante opslag.

Selvom sorteringer godt kan virke meget lette fra et menneskeligt perspektiv, så er det meget anderledes for maskiner, som skal have helt præcise instrukser for, hvordan sorteringen skal foregå. Jo hurtigere sorteringen finder sted, jo mere effektiv er sorteringsalgoritmen. Igennem flere årtier har computerprogrammører forsøgt at skabe bedre metoder for sortering, hvilket er endt i, at der i dag findes mange forskellige sorteringsalgoritmer, med navne som f.eks. indsættelsessortering, boblesortering og udtagelsessortering.

I denne artikel vil vi ikke gå i detaljer med præcist hvordan de forskellige sorteringsalgoritmer udføres, men i nedenstående video kan man se hvordan 15 forskellige sorteringsalgoritmer bliver visualiseret, hvilket giver et indblik i, hvordan de fungerer:

Bemærk, at blandt de forskellige sorteringsalgoritmer, som er vist i videoen, er der nogle som er hurtigere, og dermed mere effektive, end andre. Dog afhænger hastigheden også af, hvilken slags sortering der er tale om, og derfor kan nogle algoritmer være mere effektive i nogle tilfælde, mens nogle andre algoritmer er mere effektive i andre tilfælde.

Tidskompleksiteten

I forbindelse med programmeringen af algoritmer er tidskompleksiteten et essentielt redskab til at udregne hvordan algoritmens tidsforbrug stiger i takt med at dataen, som den bliver givet, øges.

Man kunne umiddelbart tro, at den bedste måde at udregne algoritmens tidsforbrug, er ved at tage tid på, hvor lang tid det tager den, at give et resultat. Dette vil dog være meget misvisende, da tidsforbruget kan variere meget i forhold til computerkraften, samt mængden af data som algoritmen skal behandle.

For at beregne tiden benytter man sig i stedet af O-notationen til at give et mere misvisende indblik i algoritmens tidskompleksitet. O-notationen tager udgangspunkt i, hvordan tidsforbruget stiger i takt med at algoritmen skal arbejde med mere data. Denne udvikling kan f.eks. være lineær (O(N)), kvadratisk (O(N²)), eller logaritmisk (O(log₂ N)), hvor N er mængden af data, som algoritmen skal arbejde med.

For en kvadratisk udvikling, så vil algoritmens beregning derfor tage ca. 4 gange så lang tid hver gang mængden af data fordobles. Denne metode for beregning af tidsforbrug er meget variabel, da den ikke giver et specifikt tidsforløb for, hvor lang tid det tager en algoritme at blive færdig, men i stedet fortæller om, hvordan tidsforbruget udvikler sig i takt med mængden af data.

Nedenstående tabel giver en oversigt over de vigtigste O-notationer:

En algoritme vil derfor være mere effektiv, hvis den f.eks. følger en lineær udvikling frem for en eksponentiel udvikling, da tidsforbruget vil stige med mindre i takt med forøgelsen af data.