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
a1, a2, ..., an
som består av n tal.
- Utdata: en permutation (omkastning av ordningen)
a'1, a'2, ..., a'n
av indataföljden med egenskapen
a'1 ≤ a'2 ≤ ... ≤ 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
c1n2, där c1
är en konstant som beror på hur algoritmen är implementerad.
-
Mergesort kräver ungefär
c2n log n instruktioner, där
c2 ä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.
- Vi kör insättningssortering på en snabb dator som kan
exekvera 109 instruktioner per sekund.
Algoritmen är implementerad av en skicklig
programmerare och konstanten c1 = 5.
- Mergesort kör vi på en mycket långsammare dator som bara kan
exekvera 107 instruktioner per sekund.
Implementationen av mergesort är dessutom mycket dåligt optimerad:
c2 = 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.