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.

// Sum returns the sum 1 + 2 + ... + n, where n >= 1.
func Sum(n int) int64 {
    if n == 1 {
        return 1
    }
    return int64(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).

Om vi nöjer oss med en asymptotisk 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

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.

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

    // Subarray with more than one element
    int mid = first + (last-first)/2; // written like this to avoid overflow
    // Note: first <= mid < last
    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:

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

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.

Stefan Nilsson