recorrencias

Complexidade de Algoritmos I
Prof. Pedro J. de Rezende
2o¯ Semestre de 2002

Rela¸ c˜ oes de Recorrˆ encia∗ 1

Introdu¸c˜ ao Intuitivamente, a partir de uma demonstra¸c˜ao por indu¸c˜ao pode-se extrair um algoritmo recursivo e, da descri¸c˜ao deste assim obtida, pode-se facilmente imaginar que nasce imediatamente uma express˜ao recursiva para a fun¸c˜ao de complexidade do algoritmo. O objeto de estudo dentro do corrente t´opico ´e justamente tais fun¸c˜oes.
Chamamos de rela¸c˜ ao de recorrˆencia a uma express˜ao recursiva para defini¸c˜ao uma fun¸c˜ao. Estaremos especialmente estudando formas de se encontrarem solu¸c˜oes (i.´e., f´ormulas fechadas) para rela¸c˜oes de recorrˆencia.
O exemplo cl´assico de rela¸c˜ao de recorrˆencia, que aprendemos desde o segundo grau, ´e a f´ormula de Fibonacci:
F (n) = F (n − 1) + F (n − 2), F (1) = 1, F (0) = 0.
Para qualquer valor de n ≥ 1, podemos calcular a partir desta express˜ao, o valor da fun¸c˜ao F (n). Por exemplo, F (3) = F (2) + F (1) = (F (1) + F (0)) +
F (1) = (1 + 0) + 1 = 2, F (4) = F (3) + F (2) = 2 + 1 = 3 e assim por diante.
Dada sua natureza recursiva, toda rela¸c˜ao de recorrˆencia tem uma ou mais condi¸ c˜ oes de parada (da recorrˆencia) sem as quais n˜ao ´e poss´ıvel calcular seus valores. Para a f´ormula de Fibonacci, as condi¸c˜oes de parada s˜ao F (1) = 1, F (0) = 0.
Uma f´ormula que pode ser usada para definir uma rela¸c˜ao de recorrˆencia
T (n) qualquer ´e a seguinte:
T (n) = f ((T (1), T (2), . . ., T (n − 1), n), onde f ´e uma fun¸c˜ao de n parˆametros onde, para calcular T (n), ´e necess´ario conhecer o valor de T (n ) para todos os n < n. Daqui por diante, denotaremos por T , com freq¨ uˆencia, a fun¸c˜ao que descreve o tempo despendido por um algoritmo. 2

Revis˜ ao de Somat´ orios Quando um algoritmo apresenta constru¸c˜oes iterativas (como la¸cos) ou chamadas recursivas, sua complexidade pode ser expressa como a soma dos
∗ Escriba:

Fernando Jos´ e Castor de Lima Filho.

1

tempos gastos em