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.