Algoritmer

En algoritm är en metodisk och exakt beskrivning av hur man löser ett problem. En algoritm är i mångt och mycket samma sak som ett program; skillnaden är att vi kan beskriva algoritmer oberoende av programspråk. En algoritm som någon hittar på idag kan därför vara lika aktuell och användbar långt efter att den sista Javaprogrammeraren har loggat ut.

Definition: En algoritm är en stegvis procedur av väldefinerade exekverbara instruktioner avsedda att utföra en uppgift eller lösa ett problem, ofta med kravet att proceduren ska ha ett slut.

Programmering går ut på att beskriva algoritmer så att de kan exekveras av maskiner och dessutom förstås av människor.

Observera att det finns många algoritmer för att lösa ett visst problem, algoritmer som kan ha mycket olika egenskaper. Målet är att konstruera algoritmer som är korrekta, enkla och effektiva.

Vi kommer bland annat att studera hur rekursiva metodanrop kan användas för att designa kraftfulla algoritmer och hur man använder datastrukturer som vektorer, länkade listor, hashtabeller, träd och grafer för att uppnå bra prestanda. Vi kommer också att lära oss en kraftfull och plattformsoberoende teknik, asymptotisk tidskomplexitet, för att analysera effektiviteten hos en algoritm.

Problem

Algoritmer kan användas för att lösa vissa typer av beräkningsproblem. Vi kan ofta beskriva sådana problem genom att ange hur indata och utdata förhåller sig till varandra. Sorteringsproblemet kan vi till exempel beskriva så här.

• Indata: en talföljd a₁, a₂, ..., a_n som består av n tal.
• Utdata: en permutation (omkastning av ordningen) a'₁, a'₂, ..., a'_n av indataföljden med egenskapen a'₁ ≤ a'₂ ≤ ... ≤ a'_n.

Ett exempel: för indataföljden 12, 24, 13, 12, 8 så ska en sorteringsalgoritm returnera följden 8, 12, 12, 13, 24. Ett sådant här specifikt exempel på indata till ett problem kallas för en instans av problemet.

Vi säger att en algoritm är korrekt om den för varje instans av problemet stannar och returnerar rätt utdata. En korrekt algoritm löser det givna beräkningsproblemet.

Pseudokod

När vi beskriver algoritmer så kommer vi att använda både exekverbar Javakod och pseudokod.

Definition: Pseudokod är en kompakt och informell högnivåbeskrivning av en algoritm avsedd för människor snarare än för maskiner.

I pseudokod utelämnar man ofta detaljer som inte är kritiska för förståelsen, till exempel variabeldeklarationer och systemspecifika metodanrop, och använder vid behov naturligt språk eller matematisk notation. Pseudokod används ofta för att beskriva algoritmer i texter eller för att diskutera algoritmer innan man kodar dem.

Observera att pseudokod inte är en ursäkt för att slarva när man beskriver en algoritm. Korrekthet är minst lika viktigt för pseudokod som för exekverbar kod.

Det finns, av naturliga skäl, ingen standard för hur man skriver pseudokod. Ett exempel får demonstrera den typ av pseudokod som vi kommer att använda. Här är en metod skriven i Java.

/**
 * Returnerar summan 1 + 2 + ... + n, där n >= 1.
 */
public long sum(int n) {
    long sum = 0;
    int i = 1;
    while (i <= n) {
        sum += i;
        i++;
    }    
    return sum;
}

Samma metod i pseudokod skulle kunna se ut så här.

// Returnerar summan 1 + 2 + ... + n, där n >= 1.
Algorithm sum(n):
    sum = 0
    for i = 1 to n
        sum += i
    return sum

Effektivitet

Olika algoritmer som löser samma problem kan ha dramatiskt olika prestanda. Här är ett typiskt exempel.

• Antalet instruktioner för att sortera n tal med insättningssortering kan approximeras med formeln c₁n², där c₁ är en konstant som beror på hur algoritmen är implementerad.
• Mergesort kräver ungefär c₂n log n instruktioner, där c₂ är en konstant som beror på implementationen. Logaritmen är i bas 2.

En van matematiker tolkar snabbt dessa formler: mergesort är mycket snabbare än insättningssortering när n är stort, dvs för stora instanser av sorteringsproblemet. För att bättre förstå detta så sätter vi in specifika värden i formlerna.

1. Vi kör insättningssortering på en snabb dator som kan exekvera 10⁹ instruktioner per sekund. Algoritmen är implementerad av en skicklig programmerare och konstanten c₁ = 5.
2. Mergesort kör vi på en mycket långsammare dator som bara kan exekvera 10⁷ instruktioner per sekund. Implementationen av mergesort är dessutom mycket dåligt optimerad: c₂ = 100.

För små instanser av sorteringsproblem vinner den snabba datorn. För n = 1000 tar det ungefär 5 ms att sortera med alternativ 1, medan alternativ 2 tar 100 ms.

För större instanser ändras bilden dramatiskt. Om n = 1,000,000 så tar alternativ 1 mer än en timme (5000 s), medan alternativ 2 tar mindre än fem minuter (200 s). För större instanser blir skillnaderna ännu större och valet av en bra algoritm därmed ännu viktigare.