Complexidade de Algoritmos Recursivos

Alex F. V. Machado

2

Recursividade

Implementação recursiva

int fatorial (int N)

{

if (N<= 1)

return(1);

else

return( N * fatorial(N-1));

}

3

Recursividade X= fatorial (4)

return( 4* fatorial(3) ) return( 3* fatorial(2) ) return( 2* fatorial(1) ) return( 1 )

4

Análise de Recursividade• T(n)

tempo de processar o algoritmo para entrada n número de passos ou operações dominantes

– Fatorial– T(n) = 1, se n = 0– = T(n-1) + 1, se n > 0

mas quanto é T(n-1) ?

5

T(n) - Fatorial• = (T(n-1)) + 1• = (T(n-2) + 1) + 1• = T(n-2) + 2• = (T(n-3) + 1) + 2• = T(n-3) + 3• ..... forma geral, T(n) = T(n-k) + k, 1 k n fazendo n = k, reduzimos a T(n) = n

void mergeSort(int vec[], int vecSize) { int mid; if (vecSize > 1) { mid = vecSize / 2; mergeSort(vec, mid); mergeSort(vec + mid, vecSize - mid); merge(vec, vecSize); }}

void merge(int vec[], int vecSize) {

int mid; int i, j, k; int* tmp;

mid = vecSize / 2;

i = 0; j = mid; k = 0;

while (i < mid && j < vecSize) {

if (vec[i] > vec[j]) {

tmp[k] = vec[i];

++i;

}

else {

tmp[k] = vec[j];

++j;

}

++k;

}

if (i == mid) {

while (j < vecSize) {

tmp[k] = vec[j];

++j; ++k;

}

}

else {

while (i < mid) {

tmp[k] = vec[i];

++i; ++k;

}

}

for (i = 0; i < vecSize; ++i) {

vec[i] = tmp[i];

}

}