Tidskomplexitet
Paradoxalt nog så ökar behovet av effektiva algoritmer när processorer blir
allt snabbare och minnen allt större. Skälet till detta är ganska subtilt.
Tiden som krävs för att exekvera många algoritmer växer som en superlinjär
funktion av storleken på indata.
Betrakta till exempel en sorteringsalgoritm
som utför n2 jämförelser för att sortera n tal.
Antag att beräkningskapaciteten hos en dator ökar med en
faktor 100 på ett par år. På den tid det förut tog att exekvera
n2 jämförelser kan man nu exekvera
100n2 = (10n)2 jämförelser.
Man kan alltså bara sortera 10 gånger så många tal. Det mesta av vinsten med
den nya hårdvaran har ätits upp av en ineffektiv algoritm.
Hur snabb är följande algoritm?
Algorithm max(A):
Input: an array A storing n integers.
Output: the largest element in A.
max = A[0]
for i = 1 to n-1
if max < A[i]
max = A[i]
return max
Svaret beror inte bara på vilket programmeringsspråk vi använder och
på vilken plattform vi kör programmet, utan också på indata till algoritmen.
Eftersom vi primärt är intresserade av algoritmen så är vårt mål att mäta
effektiviteten på ett sätt som bara beror på algoritmen själv och dess indata.
Det gör vi genom att välja någon eller några karakteristiska operationer
som algoritmen utför upprepade gånger och definiera tidskomplexiteten
T(n) för algoritmen som antalet operationer som algoritmen
utför när den får indata av storlek n.
I exemplet ovan kan vi välja den jämförelse som
utförs i if-satsen som karakteristiskt operation. Antalet jämförelser
bör ge en god bild av algoritmens effektivitet eftersom
antalet sådana operationer dominerar över övriga operationer i algoritmen.
Dessutom är kostnaden för en jämförelseoperation konstant:
oberoende av hur stor vektorn är så tar det samma tid att läsa elementet
på plats i och jämföra det med max.
Tidskomplexitet, mätt i antalet jämförelser, blir då
T(n) = n - 1.
En karakteristisk operation bör alltid ha följande egenskaper.
- Tiden för att exekvera en karakteristisk operation ska vara konstant,
det vill säga tiden för en operation får inte växa när storleken
på indata växer.
- Det får inte finnas andra operationer som utförs fler gånger
än de karakteristiska operationerna när storleken på indata växer.
Värstafall
Betrakta följande algoritm.
Algorithm find(x, A):
Input: an integer x, an array A storing n integers.
Output: true if x is in A, false otherwise.
for i = 0 to n-1
if x equals A[i]
return true
return false
Här kan vi också använda antalet jämförelser som karakteristisk operation.
Storleken på indata låter vi vara n, antalet element i vektorn.
I det här fallet beror antalet jämförelser inte bara på n,
utan också på x och de värden som lagras i vektorn.
Om x inte finns i vektorn så gör algoritmen n jämförelser,
men om x = A[0] så blir det bara en jämförelse.
Vi väljer därför ofta att studera tidskomplexiteten i värstafall.
Mer formellt kan vi definiera värstafallstiden på följande sätt.
Låt T1(n), T2(n), ... vara tiden att
exekvera algoritmen för de olika instanserna av storlek n.
Värstafallstiden är då
W(n) = max T1(n), T2(n), ...
Tidskomplexiteten i värstafall för find-algoritmen blir alltså
W(n) = n.
Värstafallstiden ger en garanti på att algoritmen
alltid är minst så här effektiv. Den är dessutom oftast förhållandevis
enkel att räkna ut. Nackdelen är att värstafallstiden ibland kan vara
onödigt pessimistisk.
Medelfall
Ibland vill man istället studera tidskomplexiteten i medelfall
som definieras på följande sätt.
Låt T1(n), T2(n), ... vara tiden att
exekvera instanserna av storlek n.
Låt P1(n), P2(n), ... vara sannolikheten
för en viss instans. Tidskomplexiteten i medelfall definieras då som summan
P1(n)T1(n) +
(n)P2(n)T2(n) + ...
Medelfallet är ofta svårare att räkna ut och kräver dessutom att
man vet sannolikheten för olika typer av indata, något som ofta inte är fallet.
Därför kommer vi oftast att använda värstafallsanalys.
Kvadratisk tidskomplexitet
Vi avslutar med ett exempel på en algoritm som skalar dåligt när storleken
på probleminstanserna växer.
Algorithm reverse(A):
Input: an array A storing n elements.
Output: the same array with the elements in reversed order.
for i = 1 to n-1
x = A[i]
for j = i downto 1
A[j] = A[j-1]
A[0] = x
Storleken på en instans av problemet är helt enkelt längden n
av vektorn A. Som karakteristisk operation väljer vi
tilldelningssatsen i den inre for-loopen. Både läsning och skrivning
i en vektor tar konstant tid och tilldelningssatsen är den dominerande
kostnaden i den här algoritmen.
Antalet karakteristiska operationer beror i det här fallet endast
på n och tidskomplexiteten i värstafall blir W(n) =
1 + 2 + ... + n - 1 =
n(n - 1)/2 =
n2/2 - n/2.
Den kvadratiska termen i polynomet dominerar när n växer och vi
säger därför att algoritmen har kvadratisk tidskomplexitet.
Det innebär att algoritmen
skalar dåligt och endast är användbar för små vektorer:
för att kasta om ordningen på elementen i en vektor med tiotusen element
så kommer den här algoritmen att utföra ungefär 50 miljoner
tilldelningssatser.
W8
I det här fallet är det ganska enkelt att hitta på en algoritm med
linjär tidskomplexitet, dvs W(n) = O(n). Gör det!