bild
Skolan för
datavetenskap
och kommunikation
KTH / CSC / Kurser / DD1341 / inda10 / Algoritmer / Algoritmer

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 a1a2, ..., an som består av n tal.
  • Utdata: en permutation (omkastning av ordningen) a'1a'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.

Copyright © Sidansvarig: Stefan Nilsson <snilsson@nada.kth.se>
Uppdaterad 2009-10-16