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 k₁ s� �r T(1) = k₁.
Om n > 1 s� kommer metoden att g�ra ett fixt antal ber�kningssteg k₂ 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) = k₂ + T(n-1).

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 k₁ och k₂ utan l�ter k₁ = k₂ = 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/2^k) = ... log n + T(n/2^log 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) = Θ(n^d), d�r d ≥ 0, s� g�ller

T(n) = Θ(n^d) om a < b^d,
T(n) = Θ(n^dlog n) om a = b^d,
T(n) = Θ(n^log_ba) om a > b^d.

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) = Θ(n⁰), det vill s�ga d = 0. Vi ser att a = b^d och kan d�rf�r anv�nda punkt tv� i m�starsatsen som s�ger att

T(n) = Θ(n⁰log n).

Vilket st�mmer.