Recorrencias

Recorrências

Recorrências e Tempo de Execução
•

Uma equação ou inequação que descreve uma função em termos de seu valor sobre pequenas entradas
T(n) = T(n-1) + n

•

Recorrências aparecem quando um algoritimo contém chamadas recursivas para ele mesmo

•

Qual é de fato o tempo de execução de um algoritmo?

•

É preciso resolver a recorrência
– Encontrar um fórmula explícita de uma expressão
– Limitar a recorrência por uma expressão que envolve n

Exemplos de Recorrências
• T(n) = T(n-1) + n
Θ(n2)
– Algoritmo recursivo que a cada loop examina a entrada e elimina um item
• T(n) = T(n/2) + c
Θ(lgn)
– Algoritmo recursivo que divide a entrada em cada passo
• T(n) = T(n/2) + n
Θ(n)
– Algoritmo recursivo que divide a entrada, mas precisa examinar cada item na entrada
• T(n) = 2T(n/2) + 1
Θ(n)
– Algoritmo recursivo que divide a entrada em duas metades e executa uma quantidade constante de operações Algoritmos Recursivos
BINARY-SEARCH
•

Para um vetor ordenado A, verifique se x está no vetor A[lo…hi]

Alg.: BINARY-SEARCH (A, lo, hi, x)
1

2

3

4

2 3 5 if (lo > hi) return FALSE mid  (lo+hi)/2 lo if x = A[mid] return TRUE if ( x < A[mid] )
BINARY-SEARCH (A, lo, mid-1, x) if ( x > A[mid] )
BINARY-SEARCH (A, mid+1, hi, x)

7

5

6

7

8

9 10 11 12 mid hi

Exemplo
• A[8] = {1, 2, 3, 4, 5, 7, 9, 11}
– lo = 1 hi = 8 x = 7
1

2

3

4

5

6

7

8

1

2

3

4

5

7

9 11

1

2

3

4

5

7

9 11

mid = 4, lo = 5, hi = 8

mid = 6, A[mid] = x
Encontrado!!!

Outro exemplo
• A[8] = {1, 2, 3, 4, 5, 7, 9, 11}

– lo = 1

hi = 8

x=6

1

2

3

4

5

6

7

8

1

2

3

4

5

7

9 11

mid = 4, lo = 5, hi = 8

1

2

3

4

5

7

9 11

mid = 6, A[6] = 7, lo = 5, hi = 5

1

2

3

4

5

7

9 11

mid = 5, A[5] = 5, lo = 6, hi = 5
NÃO ENCONTRADO!

Análise do BINARY-SEARCH
Alg.: BINARY-SEARCH (A, lo, hi, x) tempo contante: c1 if (lo > hi) return FALSE tempo contante: c2 mid  (lo+hi)/2 if x = A[mid] tempo contante: c3 return TRUE if ( x < A[mid] ) mesmo problema de
BINARY-SEARCH (A,