bild
Skolan för
elektroteknik
och datavetenskap

Tidskomplexitet för rekursiva funktioner

Man kan ofta räkna ut tidskomplexiteten för rekursiva funktioner genom att ställa upp och lösa en rekursionsekvation. Här kommer några exempel och en formel, ”mästarsatsen”, som ger lösningen för ett antal rekursionsekvationer som ofta dyker upp när man analyser rekursiva funktioner.

Exempel 1: summa

Som uppvärmning visar vi att följande rekursiva metod har linjär tidskomplexitet.

/**
 * Returnerar summan 1 + 2 + ... + n, där n >= 1.
 */
public long sum(int n) {
    if (n == 1)
	return 1;
    return n + sum(n-1);
}

Vi börjar med att införa funktionen T(n) som är antalet grundläggande beräkningssteg som utförs vid metodanropet sum(n). Vi hittar genast två egenskaper hos T(n).

  • Eftersom sum(1) beräknas i ett fixt antal beräkningssteg k1 så är T(1) = k1.
  • Om n > 1 så kommer metoden att göra ett fixt antal beräkningssteg k2 och dessutom ett rekursivt anrop till sum(n-1). Detta rekursiva anrop kommer att utföra T(n-1) beräkningssteg. Vi får alltså T(n) = k2 + T(n-1).
Om vi nöjer oss med en assymptotisk uppskattning av tidskomplexiteten så behöver vi inte känna till de exakta värdena på konstanterna k1 och k2 utan låter k1 = k2 = 1. Vi har då reducerat problemet att hitta tidskomplexiteten för metoden sum till att lösa följande rekurssionsekvation
  • T(1) = 1, (*)
  • T(n) = 1 + T(n-1), när n > 1. (**)

Genom att använda dessa två ekvationer kan vi beräkna T(n) för ett godtyckligt positivt heltal n. Räkningen ser ut så här.

T(n) = (**) 
1 + T(n-1) = (**) 
1 + (1 + T(n-2)) = 2 + T(n-2) = (**) 
2 + (1 + T(n-3)) = 3 + T(n-3) = ... 
k + T(n-k) = ... 
n - 1 + T(1) = (*) 
n - 1 + 1= Θ(n).

Exempel 2: binärsökning

Precis samma metod kan användas även för mera komplicerade rekursiva algoritmer. Det är fortfarande lika enkelt att ställa upp rekursionsekvationen även om det kan vara mera komplicerat att lösa den. Vi provar att räkna ut tidskomplexiteten för binärsökning.

private static final int NOT_FOUND = -1;

/**
 * Returns index of the first occurence of key in the sorted
 * subarray v[first..last], or -1 if key is not found.
 * Precondition: first <= last.
 */
private int binSearch(int[] v, int first, int last, int key) {
    if (first == last) {
        return key == v[first] ? first : NOT_FOUND;
    }

    // subarray with more than one element
    int mid = first + (last - first)/2;
    if (key <= v[mid]) {
        return binSearch(v, first, mid, key);
    } else {
        return binSearch(v, mid + 1, last, key);
    }
}

Vi inför beteckningen T(n) för antalet beräkningssteg som algoritmen utför i värsta fall vid ett anrop med en subvektor som innehåller n element.

För att göra problemt lite enklare nöjer vi oss med att beräkna den asymptotiska tidskomplexiteten. Vi kan då tillåta oss att sätta samtliga konstanter till 1. Rekursionsekvationen blir:

  • T(1) = 1, (*)
  • T(n) = 1 + T(n/2), när n > 1. (**)
Ekvation (**) följer av att metoden gör ett konstant arbete (det är 1:an) och ett rekursivt anrop med en subvektor av storlek n/2. (Subvektorn kommer i vissa fall att ha storlek n/2 + 1 vid det rekursiva anropet. Men det struntar vi i eftersom vi endast söker ett asymptotiskt svar.)

Om man inte kan någon teori för rekursionsekvationer så får man göra som i exemplet ovan och räkna ut en lösning genom upprepad substitution. Räkningen ser ut så här:

T(n) = (**)
1 + T(n/2) = (**)
1 + (1 + T(n/4)) = 2 + T(n/4) = (**)
2 + (1 + T(n/8)) = 3 + T(n/8) = ...
k + T(n/2k) = ...
log n + T(n/2log n) = log n + T(1) = (*)
log n + 1 = Θ(log n).

Mästarsatsen

Mästarsatsen är ett recept som ger asymptotiska uppskattningar för en klass av rekursionsekvationer som ofta dyker upp när man analyserar rekursiva algoritmer.

Mästarsatsen

Låt a ≥ 1 och b > 1 vara konstanter, låt f(n) vara en funktion och låt T(n) vara en funktion över de positiva talen definierad av rekursionen

T(n) = aT(n/b) + f(n).
Om f(n) = Θ(nd), där d ≥ 0, så gäller
  • T(n) = Θ(nd) om a < bd,
  • T(n) = Θ(ndlog n) om a = bd,
  • T(n) = Θ(nlogba) om a > bd.

Vi hoppar över beviset. Det är inte svårt, men långt. Man kan använda upprepad substitution på samma sätt som i de föregående exemplen.

Låt oss kontrollera att mästarsatsen ger rätt lösning för rekursionsekvationen i exemplet med binärsökning. I detta fall är a = 1,  b = 2 och funktionen f(n) = 1. Det innebär att f(n) = Θ(n0), det vill säga d = 0. Vi ser att a = bd och kan därför använda punkt två i mästarsatsen som säger att

T(n) = Θ(n0log n).
Vilket stämmer.

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