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.
-
Antalet instruktioner för att sortera n tal med
insättningssortering kan approximeras med formeln
c1n2, där c1
är en konstant som inte beror på n.
-
Mergesort kräver ungefär
c2n log n instruktioner, där
c2 är en konstant som inte beror på n
och log n är logaritmen av n i basen 2.
Storleken på konstanterna är plattformsberoende,
men i allmänhet är c1 < c2.
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.
- Låt A vara en snabb dator som kör insättningssortering.
Vi antar också att programmet är skrivet av en skicklig
programmerare så att konstanten c1 är liten,
låt oss anta att c1 = 5.
Denna dator kan exekvera 109 instruktioner per sekund.
- Låt B vara en mycket långsammare dator som kör en implementation
av mergesort som är korrekt men väldigt dåligt optimerad:
c2 = 100.
Den här datorn kan bara exekvera 107 instruktioner per sekund.
För små instanser av sorteringsproblem vinner den snabba datorn.
Om n är tusen så tar det ungefär 5 millisekundsekund
att sortera med alternativ A, medan B tar 100 millisekunder.
För större instanser ändras bilden dramatiskt. Om n är en miljon
så kör alternativ A på 5000 sekunder, medan alternativ B
bara tar 200 sekunder. För större instanser blir skillnaderna
ännu större och valet av en bra algoritm därmed ännu viktigare.