bild
Skolan för
elektroteknik
och datavetenskap

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!

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