Engenheiro

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

Rela¸˜es de Recorrˆncia∗ co e 1 Introdu¸˜o ca

Intuitivamente, a partir de uma demonstra¸ao por indu¸ao pode-se extrair c˜ c˜ um algoritmo recursivo e, da descri¸ao deste assim obtida, pode-se facilmente c˜ imaginar que nasce imediatamente uma express˜o recursiva para a fun¸ao de a c˜ complexidade do algoritmo. O objeto de estudo dentro do corrente t´pico ´ o e justamente tais fun¸oes. c˜ Chamamos de rela¸˜o de recorrˆncia a uma express˜o recursiva para ca e a defini¸ao uma fun¸ao. Estaremos especialmente estudando formas de se c˜ c˜ encontrarem solu¸oes (i.´., f´rmulas fechadas) para rela¸oes de recorrˆncia. c˜ e o c˜ e O exemplo cl´ssico de rela¸ao de recorrˆncia, que aprendemos desde o a c˜ e segundo grau, ´ a f´rmula de Fibonacci: e o 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˜o, o a valor da fun¸ao F (n). Por exemplo, F (3) = F (2) + F (1) = (F (1) + F (0)) + c˜ 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¸ao de recorrˆncia tem uma ou c˜ e mais condi¸oes de parada (da recorrˆncia) sem as quais n˜o ´ poss´ c˜ e a e ıvel calcular seus valores. Para a f´rmula de Fibonacci, as condi¸oes de parada o c˜ s˜o F (1) = 1, F (0) = 0. a Uma f´rmula que pode ser usada para definir uma rela¸ao de recorrˆncia o c˜ e T (n) qualquer ´ a seguinte: e T (n) = f ((T (1), T (2), . . ., T (n − 1), n), onde f ´ uma fun¸ao de n parˆmetros onde, para calcular T (n), ´ necess´rio e c˜ a e a conhecer o valor de T (n′ ) para todos os n′ < n. Daqui por diante, denotaremos por T , com freq¨ˆncia, a fun¸ao que descreve o tempo despendido por um ue c˜ algoritmo.

2

Revis˜o de Somat´rios a o

Quando um algoritmo apresenta constru¸oes iterativas (como la¸os) ou c˜ c chamadas recursivas, sua complexidade pode ser expressa como a soma dos
∗ Escriba: