Algoritmos e Estrutura de Dados (Fundamentos) - Marcos Cesar C Carrard

Prévia do material em texto

Universidade Regional do Noroeste do RS 
Departamento de Tecnologia 
 
 
 
 
 
 Algoritmos 
e 
Estruturas de Dados 
 
Parte I  Fundamentos 
 
 
 
 
 
 
Marcos César C. Carrard 
 2
Apresentação 
 
 
 
 
 
 
 
 
 Este trabalho tem o objetivo de introduzir os conceitos básicos de 
algoritmos e suas formas de análise. A razão disto vem da necessidade de 
tratarmos estruturas de dados  que é a continuidade do mesmo, sob a ótica do 
trabalho eficiente e eficaz de cada uma delas. 
 Isto representa uma certa novidade em materiais que tratam do assunto 
“Estruturas de Dados”, pois a maioria deles o faz sob o ponto de vista dos 
algoritmos e princípios de funcionamento de cada uma das estruturas 
apresentadas. 
Sabemos, entretanto, que existem várias organizações de dados possíveis 
para os mais variados casos. Assim sendo, qual é a melhor delas? Qual eu vou 
escolher para solucionar o meu problema? Como ela faz esta solução? 
Desta forma e para tentar solucionar estas questões postas é que 
necessitamos entender melhor o que é, como funciona e se comporta um 
algoritmo. Este é o escopo e o objetivo deste material. 
Finalmente, por ser um material em constante atenção e experimentação, 
caso o leitor localize algum incorreção, melhoria ou tenha qualquer comentário, 
entre em contato comigo pelo e-mail abaixo. 
 
 
 
 
 
Marcos Carrard 
carrard@detec.unijui.tche.br 
 
 
 
 
 
 
 3
Índice 
 
 
 
Capítulo 1 − Algoritmos 
1.1 Definição 4 
1.2 Características 5 
1.3 Formas de Apresentação 7 
1.3.1 Iteração vs. Recursão 8 
1.4 Exercícios 11 
 
Capítulo 2 − Análise de Eficiência 
2.1 Introdução 13 
2.2 Analisando algoritmos 15 
2.2.1 Algoritmos vs. Problemas 16 
2.2.2 Estudo de casos 17 
2.3 Comportamento Assintótico 19 
2.3.1 Introdução 19 
2.3.2 Crescimento de funções 19 
2.3.3 Complexidade assintótica 22 
2.4 Técnicas de Análise 25 
2.4.1 Introdução 25 
2.4.2 Análise de algoritmos iterativos 25 
2.4.3 Processo de análise 26 
2.4.4 Considerações gerais 32 
2.5 Exercícios 33 
 
Capítulo 3 − Relações de Recorrência 
3.1 Introdução 37 
3.2 Definição 37 
3.3 Métodos de Solução 40 
3.3.1 Introdução 40 
3.3.2 Método de história completa 41 
3.3.3 Método mestre 48 
3.3.4 Considerações gerais 51 
3.4 Exercícios 51 
 
Anexo I - Descrição da Linguagem 53 
Bibliografia 59 
 4
1 
 
Algoritmos 
 
 
 
 
 
 
 
1.1 Definição 
 
 O termo algoritmo tem uma origem interessante. Algumas vezes 
pensamos que alguém tentou escrever a palavra logaritmo e trocou as letras 
iniciais. Podemos, também, encontrar alguma afinidade com a palavra 
“algarismo” em seu significado original, ou seja, um processo para fazer 
operações aritméticas utilizando numerais arábicos. Mesmo assim, a origem 
ainda é dúbia. 
 Talvez a versão mais coerente para a origem desta palavra, advinda da 
história remota da matemática, é atribuída ao nome de um famoso matemático 
persa, Abu Ja’far Mohammed ibn Mûsâ al-Khowârizmî, a aproximadamente 800 
anos antes da era Cristã. Al-Khowârizmî escreveu um célebre livro chamado 
“Kitab al jabr w’al-muqabala” (Regras de Restauração e Redução). Embora esta 
obra não possua o cunho algébrico, a matemática moderna atribuí também a ela a 
origem do termo “álgebra”. 
 Com o passar dos anos, várias conotações do termo algoritmo, algumas 
bastante errôneas, foram surgindo e sendo atribuídas a vários métodos e 
procedimentos. Na década de 50, neste século, ele foi associado, com freqüência, 
ao Algoritmo de Euclides que descrevia um processo para encontrar o máximo 
divisor comum entre dois números e se encontrava em sua obra Os Elementos, 
livro 7, proposições 1 e 2. Esta obra constituiu o principal texto no estudo de 
geometria por cerca de 20 séculos. 
 Segundo definições atuais, encontradas em dicionários, e advindas das 
definições anteriores unidas a outras, podemos definir algoritmo da seguinte 
forma: 
 5
Algoritmo é uma seqüência finita de passos bem definidos 
que, partindo de informações fornecidas previamente, 
produz um resultado que é a solução de um determinado 
problema. 
 
 Hoje em dia, dizer que um problema tem solução algorítmica significa, 
mesmo que informalmente, que um programa de computador pode ser escrito em 
alguma linguagem e irá produzir a resposta correta para qualquer entrada válida 
fornecida se lhe for dado o tempo de máquina e a memória que vier a necessitar. 
 
1.2 Características 
 Determinar que um problema pode ser transcrito para um algoritmo e 
posteriormente para um programa e quais são os requisitos necessários a sua 
operação compõem uma área relativamente recente na computação denominada 
de Computabilidade. Fundamentalmente, podemos determinar dois grandes 
grupos de estudo dentro desta área. Em primeiro lugar, temos aquele que trata de 
determinar se o problema tem ou não uma solução algorítmica. Sua denominação 
é teoria dos algoritmos. Depois vamos encontrar o estudo do comportamento e 
requisitos do algoritmo para chegar a solução correta do problema. A esta dá-se o 
nome de análise de algoritmos. 
 Embora a teoria que acompanha a computabilidade tenha implicações 
óbvias na ciência da computação, o simples conhecimento de que um problema 
pode vir a ter solução algorítmica não implica que esta seja de uso prático, fácil 
ou útil. Considere, por exemplo, um jogo de xadrez, mesmo em situação inicial, e 
um algoritmo que deve propor um movimento. Se este último foi estritamente 
correto ele deverá analisar todas as situação, de acordo com as regras do jogo, 
que podem vir a responder cada possível movimento. À cada uma destas, a 
análise deve ser repetida, e assim por diante. Com o tabuleiro completo  todas 
as peças  e no princípio da partida, existem cerca de 1050 possíveis estimativas 
a serem analisadas. Com a ajuda de um computador extremamente rápido, esta 
tarefa pode demorar dias, meses ou até anos. 
 Desta forma, um algoritmo deve seguir alguns critérios gerais que 
permitirão, em uma fase inicial e de forma um tanto quanto inocente, estabelecer 
características importantes sobre ele. Segundo Horowitz e Sahni ( [HS82] ), as 
presenças mais marcantes neste grupo são: limitação, definição, entradas, saídas e 
eficiência. Observe, mesmo antes de maiores detalhes, que os membros deste 
grupo podem gerar maiores e mais precisas subdivisões. 
 Em primeiro lugar, um algoritmo deve, necessariamente, possuir um 
número finito de passos. Não existe, pelo menos a primeira vista, muita lógica em 
produzirmos um algoritmo que não tenha um final previsto. Serve como regra 
 6
geral no projeto de algoritmos deixarmos o mais explícito possível e de forma 
certificada a maneira pela qual ele alcança o resultado esperado, mesmo que o 
número de passos a serem executados para isto seja infinitamente grande. 
 Por outro lado, todos os passos ou operações a serem utilizados na 
descrição do algoritmo devem ser claramente definidas e, em hipótese alguma, 
devem dar margem para dupla interpretação. Neste ponto, quando transcrevemos 
um algoritmo para o seu respectivo programa, encontramos o serviço facilitado 
pelas linguagens de programação que, em sua proposição formal, não permitem 
que uma mesma instrução seja executada diferentemente. Esta característica 
garante um ponto fundamental da análise de algoritmos que diz que um 
algoritmo, quando executado várias vezes para uma mesma composição de dados 
de entrada, deve produzir sempre o mesmo resultado como saída. 
 Todo algoritmo deve produzir algum resultado para o problema ao qual 
ele se destina. Mas para queisto aconteça, deve ser fornecidos a ele uma certa 
quantidade de dados de entrada. Estas podem ser determinadas a cada nova 
“execução” do algoritmo ou estarem explicitamente determinadas em seu interior, 
mas em ambos os casos, devem ser claramente definidas. Por exemplo, o 
algoritmo de Euclides é capaz de encontrar o máximo divisor comum de dois 
números inteiros positivos dados. Observe as palavras grifadas. Elas formalizam, 
sem margem de dúvidas, com que tipo de entrada estamos lidando. Em geral, ao 
definirmos um algoritmo devemos informar o conjunto ou subconjunto de dados 
que ele é capaz de processar. 
 Finalmente, como pode ser claramente observado no exemplo citado 
anteriormente de um jogo de xadrez, um algoritmo deve ser eficiente, ou seja, 
deve atender a certos critérios que tornem o seu uso prático em situações reais. 
Resumindo, o que procuramos encontrar não são apenas algoritmos, mas sim 
bons algoritmos. O problema é quantificar este “bom”. 
 Observe que existe uma distinção clara entre um algoritmo e um 
programa de computador para um certo problema. O programa não está obrigado 
formalmente a atender a característica da limitação de passos, o que já não ocorre 
com o algoritmo. Como exemplo desta situação encontramos os programas que 
compõem o sistema operacional de uma determinada máquina. Estes programas, 
depois de postos em execução, continuam ou esperam indefinidamente por uma 
determinada condição ou ocorrência para realizarem o seu trabalho. Uma vez 
terminado este, eles retornam a situação de espera. Neste grupo está um 
escalonador de processos (schedulling) que periodicamente fica substituindo o 
processo (programa) que esta ocupando a unidade central de processamento da 
máquina. Ele pára o seu trabalho somente quando o equipamento é desligado. Um 
gerenciador de memória do sistema operacional também se enquadra em um caso 
equivalente a este. 
 
 7
1.3 Formas de apresentação 
 Os algoritmos são geralmente expressos em uma linguagem algorítmica. 
Estas podem possuir tão alto-nível quanto venha a ser necessário. Saliente-se que, 
embora um algoritmo possa ser projetado para uma grande variedade de 
aplicações, eles são universalmente representados em forma aproximada a um 
programa. Vários autores tem projetado suas próprias “linguagens” ou “pseudo-
linguagens” tais que estas venham a atender suas necessidades. Observe a figura 
1.1 para um exemplo destas em um algoritmo que faz o produto de duas matrizes 
n x n. 
 Neste livro não vamos ser diferentes. Você encontrará uma descrição da 
linguagem a ser utilizada no mesmo  muito próxima do Pascal e Modula  
no Apêndice A. 
 
para i := 1,...., n faça 
 para j := 1,...., n faça 
 cij := 0 
 para k := 1,...., n faça 
 cij := cij + aik ⋅ bkj 
 
 (a) Szwarcfiter e Markenzon ( [SM94] ) 
para i ← 1 até n faça 
 para j ← 1 até n faça 
 cij ← 0 
 para k ← 1 até n faça 
 cij ← cij + aik ⋅ bkj 
 
 (b) Terada ( [Ter91] ) 
for i ← 1 to n by 1 do 
 for j ← 1 to n by 1 do 
 c(i,j) ← 0 
 for k ← 1 to n by 1 do 
 c(i,j) ← c(i,j) + a(i,k) ⋅ b(k,j) 
 
 
 
 
 (c) Horowitz e Sahni ( [HS82] ) 
1 set i ← 1 
2 set j ← 1 
 set c[i,j] ← 0 
3 set k ← 1 
 c[i,j] ← c[i,j] + a[i,k] ⋅ b[k,j] 
 if k <= n then go to 3 
 if j <= n then go to 2 
 if i <= n then go to 1 
 
 (d) Knuth ( [Knu73] ) 
Figura 1.1: Algoritmos para o produto de duas matrizes n x n em várias 
linguagens algorítmicas. 
 
 O uso de uma linguagem de alto-nível para expressar um algoritmo torna 
facilitada a tarefa de obtenção de características desejáveis como simplicidade, 
legibilidade e exatidão. Entretanto, certas avaliações quanto a eficiência podem 
não ser tão apuradas quanto em uma linguagem de nível mais baixo. Alguns 
detalhes importantes podem ficar escondidas por processos de abstração de 
dados. Por exemplo, em algumas situações desejamos contar quantas 
multiplicações um algoritmo realizou para avaliar o produto de duas matrizes 
 8
n x n. Se este algoritmo expressa este produto elemento à elemento, como na 
figura 1.1, é relativamente fácil contá-las. Agora suponha que estamos utilizando 
uma linguagem que fornece um operador que faz a multiplicação diretamente. 
Evidentemente, as operações unitárias ainda ocorrem, em um nível mais baixo da 
linguagem, mas estão mascaradas pela abstração de dados. 
 A partir do momento em que venhamos a formalizar a expressão dos 
algoritmos pela nossa linguagem local (embora isto aconteça nos demais casos), 
existem duas formas padronizadas para realizar esta tarefa: projeto de algoritmos 
iterativos e projeto de algoritmos recursivos. 
 
1.3.1 Iteração vs. recursão 
 Um pequena quantidade de algoritmos são executados do seu início ao 
final em um único passo, sem que partes do programa sejam reutilizadas. Uma 
parte deste programa é frequentemente representada na forma de uma iteração ou 
laço  de onde origina o nome, tal que algumas declarações podem ser 
repetidas. Veja o algoritmo 1.1 para encontrar o fatorial de um número n (n!). 
 É fácil verificar que o algoritmo 1.1 executa n operações de 
multiplicação (descritas no laço para). Este mesmo algoritmo pode ser agora 
descrito em outro que chama a ele mesmo direta ou indiretamente. 
 Procedimentos ou funções podem incluir chamadas a elas 
mesmo, caracterizando uma recursão. Um algoritmo nesta forma é dito recursivo. 
Quando procedimentos ou funções chamam outros procedimentos ou funções que 
por sua vez invocam os originais, ocorre uma recursão indireta. Caso a chamada 
recursiva seja do procedimento ou função para ela própria, sem passar por outros 
intermediários, ocorre uma recursão direta. A literatura mostra que para 
qualquer algoritmo descrito na forma interativa existe um algoritmo de idêntica 
conduta na sua forma recursiva e vice-versa ( [Baa86] ). Como exemplo veja o 
algoritmo 1.2 que expressa o cálculo do fatorial de forma recursiva direta. 
 
procedimento fatorial( n: inteiro ): inteiro; 
var 
 i : inteiro; 
início 
 fatorial := 1; 
 if n > 1 then 
 para i := 1 até n faça 
 fatorial := fatorial * i; 
fim 
Algoritmo 1.1 - Forma iterativa para cálculo do fatorial. 
 
 9
 
procedimento fatorial( n: inteiro ): inteiro; 
início 
 se n <= 1 então fatorial := 1; 
 senão fatorial := n * fatorial( n-1 ); 
fim 
Algoritmo 1.2 - Forma recursiva para cálculo do fatorial. 
 
 Mesmo que, de modo geral, todos os algoritmos possam ser 
expressados em ambas as formas, a recursividade apresenta algumas vantagens 
claras. Os algoritmos recursivos são mais concisos que os seus correspondentes 
interativos. Da mesma forma, existe uma ligação direta entre um algoritmo 
recursivo e uma prova por indução matemática o que facilita de sobremaneira o 
projeto e verificação de algumas de suas propriedades na análise de algoritmos 
( [Knu73], [Man88], [Man89], [CLR91] e [AV92] ). 
 Vamos observar outro exemplo clássico de algoritmo recursivo, 
se bem que a sua implementação interativa não seja tão trivial. Este é o problema 
da Torre de Hanói e consiste de três pinos A, B e C, conhecidos como origem, 
destino e temporário, e n discos de tamanhos diferentes empilhados na torre A. 
Estes discos estão dispostos de tal forma que não existe um disco maior sobre um 
menor. Se numerarmos os discos tal que o menor receba o valor 1, o seguinte 2 e 
assim por diante até que o maior recebe n, existe uma restrição dizendo que para 
cada dois discos consecutivos, o número daquele que estiver em cima é sempre 
menor que o que está em baixo. 
 A tarefa pedida pelo problema é realizar um certo número de 
movimentos, um de cada vez e respeitando a restriçãodada acima, que levem 
todos os discos da torre A (origem) para a torre B (destino). Neste processo a 
torre C pode ser utilizada para o armazenamento temporário dos discos. 
 Vamos considerar o problema por partes. Inicialmente, vejamos 
o caso onde temos apenas um disco a ser movido, ou seja, n = 1. Aqui a solução é 
simples, basta levá-lo da sua posição (origem) ao destino desejado e nenhuma das 
regras vai ser infringida. 
 Retornando ao problema inicial, com n discos, sabemos que se 
nós conseguirmos deixar apenas um disco na torre A, ele poderá ser movido sem 
problemas. Mas o que faremos com os demais? Considere o problema na ordem 
inversa. Suponha que nós sabemos (não interessa como) retirar os n-1 discos 
empilhados sobre o maior deles e levá-los para a torre temporária, conforme a 
figura 1.2a. Neste caso, resta-nos duas operações finais: mover o n-éssimo disco 
da origem para o destino (figura 1.2b) e mover os n-1 discos que agora estão no 
temporário para sobre o n-éssimo na torre destino (figura 1.2c). Feito isto o 
problema terá encontrado uma solução. 
 10
 
Figura 1.2 - Evolução dos movimentos da Torre de Hanói. 
 
 Ficou apenas uma dúvida: como mover os n-1 discos que estão 
sobre o maior para a torre temporária e depois para a torre destino? Observe que o 
mesmo processo descrito acima pode ser aplicado a este grupo de disco, basta 
considerá-los como um novo problema onde o número total de discos é n-1 e a 
nomenclatura das torres é trocada: C é a origem, B o destino e A é a temporária 
do novo problema. Nenhuma das regras, principalmente a do tamanho dos discos, 
vai ser violada, pois o disco que está na torre A ou B, dependendo do caso, é o 
maior de todos. 
 
procedimento hanoi( a, b, c: caracter; n: inteiro ) 
início 
 se n = 1 então 
 escrever( “Mover disco da torre ”, a, “ para a torre ”, b ); 
 senão 
 hanoi( a, c, b, n-1 ); 
 escrever( “Mover disco da torre ”, a, “ para a torre ”, b ); 
 hanoi( c, b, a, n-1 ); 
 fim 
fim 
Algoritmo 1.3 - Solução para o problema da Torre de Hanói. 
 
 11
 Isto nos permite construir um algoritmo recursivo (algoritmo 
1.3) que soluciona do problema. E, mesmo sem termos maiores conhecimentos, 
acabamos de realizar uma prova por indução matemática. Veja abaixo o resultado 
para a chamada ao algoritmo 1.3 de hanoi( ‘A’, ‘B’, ‘C’, 3): 
 
Mover disco da torre A para a torre B 
Mover disco da torre A para a torre C 
Mover disco da torre B para a torre C 
Mover disco da torre A para a torre B 
Mover disco da torre C para a torre A 
Mover disco da torre C para a torre B 
Mover disco da torre A para a torre B 
O.k. 
 
1.4 Exercícios 
 
1. Encontre a formulação proposta e codifique o algoritmo de Euclides para 
encontrar o máximo divisor comum de dois números inteiros positivos. 
2. Escreva os números de 1 a 100 em diferentes cartões, misture-os e torne a 
recolocá-los em ordem crescente. Repita o processo para a ordem decrescente. 
Tente agora formalizar o algoritmo que foi utilizado para realizar estas tarefas. 
3. O texto descreve uma diferença básica entre algoritmos e programas. Cite 
outros programas que estão nesta mesma situação. 
4. Considere a lista de número abaixo. Sua tarefa é apagar a menor quantidade 
deles de maneira que os demais fiquem em ordem crescente. Repita depois o 
processo para a ordem decrescente. 
09 44 32 12 07 42 34 92 35 
37 41 08 20 27 83 64 61 28 
39 93 29 17 13 15 55 21 66 
72 23 73 99 01 02 88 77 03 
65 82 84 62 05 11 74 68 76 
78 67 75 69 70 04 19 57 49 
5. Escreva um algoritmo que encontre uma combinação para pagar uma quantia 
solicitada com os valores (podem ser suas moedas) de R$15,00, R$23,00, 
R$29,00, R$41,00 e R$67,00. A combinação deve ser a menor possível. 
6. Considere uma matriz quadrada de n elementos, com os valores dos elementos 
ordenados crescentemente em suas linhas e colunas. Proponha uma algoritmo 
para encontrar um determinado elemento nesta estrutura da forma mais rápida 
possível. 
 12
7. Descreva um algoritmo interativo que seja capaz de realizar a busca por um 
determinado nome em um catálogo telefônico. 
8. Para o mesmo problema descrito no exercício anterior, projete um algoritmo 
recursivo que encontre a solução desejada. 
9. Escreva um algoritmo capaz de expressar o Triângulo de Pascal abaixo: 
1 
1 1 
1 2 1 
1 3 3 1 
1 4 6 4 1 
1 5 10 10 5 1 
: : : : : : 
10. Como você armazenaria o Triângulo de Pascal acima em um computador? 
Caso você obtenha mais do que uma solução, ordene-as de acordo com a 
quantidade de espaço utilizado e a rapidez de acesso. 
 13
2 
 
Análise de Eficiência 
 
 
 
 
 
 
 
2.1 Introdução 
 
 Tendo uma idéia mais clara sobre a forma e a função de um algoritmo, 
precisamos obter maiores detalhes sobre ele, ou seja, vamos analisá-lo melhor. 
 Se nós desejamos escrever um algoritmo (ou programa) que será 
utilizado uma única vez e com uma quantidade pequena de dados, obviamente 
vamos optar por aquela maneira que parece ser mais fácil de ser concretizada. De 
maneira geral, os algoritmos simples são sempre desejáveis, pois além de serem 
de implementação mais fácil, estão menos sujeitos a erros do que outros mais 
complexos. 
 A verdade é que, no dia-a-dia da ciência da computação, a realidade é 
diversa desta. Seja pelo crescente nível de exigência ou por outras razões, os 
nossos problemas são cada vez mais complexos e devem trabalhar com uma 
quantidade de dados muito grande. Isto, obviamente, exige algoritmos (ou 
programas) mais complexos. 
 Uma outra característica desejável para nossos algoritmos é a sua 
clareza. Sempre que possível, nós deveríamos ser capazes de olhá-los e entendê-
los com facilidade. Por outro lado, a prática e a experiência nos mostram que, 
quanto mais complexo um algoritmo é, também é menos claro na mesma 
proporção. Esta relação também existe quando falamos de eficiência de 
algoritmos. 
 Em geral, existem algumas regras, também ditadas pela experiência, 
para minimizar os efeitos citados acima. A primeira delas é possuir sempre uma 
boa documentação do seu algoritmo, envolvendo descrições, provas e 
observações que forem necessárias. Em segundo lugar, comente todas aquelas 
linhas do seu algoritmo e/ou programa que não tenham significado claro. 
 14
Finalmente, utilize nomes de variáveis, funções e procedimentos que tenham 
ligação com a tarefa a ser desempenhada pelo mesmo. Isto facilita a leitura do seu 
código. 
 Quando um algoritmo tem uso extensivo ou trabalha com uma grande 
quantidade de dados, entra em cena uma terceira característica desejável: a 
eficiência. Em geral, programadores associam eficiência com o tempo que um 
algoritmo gasta para executar a sua tarefa. Na realidade, dependendo da sua 
aplicação, a eficiência pode e deve levar em consideração outros detalhes além do 
tempo, como a quantidade de memória gasta durante a execução ou, sendo mais 
geral, o espaço de armazenamento gasto; em um sistema distribuído, o tráfego de 
dados gerado é importante. Em geral, vários outros exemplos podem ser citados, 
todos eles ligados ao consumo de algum tipo de recurso do sistema em uso. 
 De qualquer forma, vamos aplicar técnicas de análise de algoritmos para 
medir estes níveis de eficiência. Em outras palavra, analisar um algoritmo ou 
programa significa determinar quais são os recursos necessários à sua execução. 
E, por recursos entendemos todos os itens que devem ser postos a disposição do 
algoritmo para a conclusão da tarefa. Como exemplo, então, citamos o tempo de 
CPU, espaço de armazenamento, dados transmitidos pela rede e outros. 
 Da mesma forma que as demais bibliografias sobre o assunto, vamos nos 
referir ao tempo de execução do algoritmo daqui para a frente com unidade base 
de avaliação,a menos que seja mencionado o contrário. Entretanto, vale salientar 
que as técnicas aplicadas para tal análise são válidas e úteis para avaliar qualquer 
outro recurso, seja dentre aqueles citados ou não. 
 Antes de mais nada, vamos responder a uma questão: por que analisar 
algoritmos? Existe uma razão principal para esta tarefa: a partir dela vamos poder 
estabelecer quantidade representativas do algoritmo que irão permitir avaliar a 
sua performance sem que o mesmo precise ser implementado em um computador. 
 Isto parece desnecessário, mas não é. Considere o caso de dois 
algoritmos A e B, sendo que o algoritmo A é extremamente eficiente quanto ao 
tempo e o algoritmo B não. Suponha agora que o algoritmo A será codificado em 
um computador antiquado e lento, enquanto que o algoritmo B será 
implementado em uma máquina de última geração. Será possível comparar os 
tempos de execução de ambos? Obviamente que não. 
 Mais além, não precisamos usar duas máquinas tão distintas, mas dois 
compiladores diferentes, de uma mesma linguagem, em uma mesmo computador. 
Basta que um deles seja capaz de gerar um código executável um pouco mais 
aprimorado para que a tarefa de comparar os algoritmos seja inútil. 
 Sabendo então que estamos medindo a eficiência de dois algoritmos 
distintos, sob os mesmos parâmetros de avaliação, estaremos também capacitados 
a compará-los e determinar sob quais condições um trabalha melhor do que o 
outro. 
 15
 Existe ainda uma justificativa teórica para a análise de algoritmos, pois 
ela pode estabelecer se o problema em questão é difícil ou não de ser solucionado 
e quais são os seus limites reais. Desta forma, pesquisas podem ser realizadas 
constantemente na busca por algoritmos e soluções mais eficientes que resolvam 
corretamente o problema. 
 Formalmente, análise de algoritmos objetiva determinar o nível de 
complexidade do mesmo e classificar problemas com complexidades similares. O 
que realmente isto é e como realizá-lo é o que vamos ver durante este capítulo. É 
importante salientar que o estudo teórico aprofundado sobre este tema, por mais 
que fundamental para um perfeito entendimento do conteúdo abordado, está fora 
do escopo deste trabalho. Para complementação, pode-se recorrer à referência 
bibliográfica existente no final ([AHU74], [AU92], [Baa88], [CLR91], [CJ79], 
[Knu73], [Man89], entre outros abordam o tema de forma bastante detalhada). 
 Antes de iniciarmos o estudo deste tema, é necessário estabelecer a 
relação existente entre este assunto e o tema em estudo: estruturas de dados. 
Estruturas de dados nada mais são do que regras transformadas em algoritmos 
que manipulam informações. Bem, esta manipulação deve ser feita de forma 
correta e eficiente, sem contar que frequentemente necessitamos comparar 
algoritmos que manipulam a mesma ou semelhantes estruturas. É para isso que 
um bom entendimento de análise de algoritmos vem ao nosso auxílio. 
 
2.2 Analisando Algoritmos 
 
 Segundo Paulo Azeredo (Aze[92]) e em consonância ao que já foi dito: 
“Analisar um algoritmo consiste em estudar o seu comportamento frente a 
diferentes tamanhos e valores de entrada”. Podemos então dizer que 
necessitaremos saber quantas operações o algoritmo em questão faz para uma 
entrada em particular. Esta pode ser uma boa definição para comportamento do 
algoritmo. 
 Analisando este tema sob o aspecto de operações realizadas para que o 
algoritmo produza a saída desejada, poderemos deduzir um tempo aproximado 
(ou gasto aproximado de recursos) em uma determinada máquina, bastando 
conhecer o comportamento desta frente as operações que serão feitas. Isto ficará 
mais evidente na seção que tratar das técnicas de análise. 
 Veja que, fazendo-se a análise desta forma não é possível se levar em 
conta características como a linguagem utilizada para a sua codificação, o 
compilador, metodologia de programação, dentre outros. Estes fatores podem, 
entretanto, ser considerados secundários se todos os algoritmos analisados aqui 
obedecerem a um mesmo critério de análise. 
 
 16
2.2.1 Algoritmos vs. Problemas 
 É importante salientar ainda que esta análise pode ser realizada de duas 
maneiras: podemos analisar algoritmos e podemos analisar problemas. 
Algoritmos e problemas são diferentes? 
 Sim, eles são. Algoritmos são soluções ou modalidades de soluções para 
um dado problema. Por exemplo, considere o seguinte caso no qual temos que 
encontrar um dado valor em um vetor de tamanho n com os seus elementos em 
ordem crescente de valor (este é o problema). Uma solução poderia ser percorrer 
o vetor do inicio ao final e, para cada elemento, verificar se é o que procuramos. 
Esta será a solução ou algoritmo 1. Outra forma seria dividir o vetor ao meio e, 
sabendo que ele está ordenado, realizar a busca somente em uma das suas 
metades, inferior ou superior, de acordo com o elemento que buscamos. Para isso 
basta testar o elemento buscado com aquele que estiver no meio do vetor. Este 
trabalho pode ser repetido até que encontremos o valor ou determinamos a sua 
ausência. Está é a solução ou algoritmo 2. 
 Já que estas duas coisas são diferentes, elas devem ser analisadas ou 
terem suas análises vistas de forma diferenciada. Enquanto que devemos ver a 
análise de algoritmos como um resultado concreto sobre a eficiência de uma 
determinada solução, a análise de um problema, na maioria das situações, apenas 
propõem um referencial teórico sobre o mesmo. Isto faz com que a análise de um 
problema seja uma tarefa árdua, penosa e, principalmente, com alto grau de 
subjetividade. 
 Quando analisamos um problema, estamos buscando estabelecer limites 
dentro dos quais as soluções propostas (algoritmos) devem estar enquadradas. Se 
isto não está acontecendo, o mínimo a se fazer é trabalhar esta solução de forma a 
melhorá-la e trazê-la aos limites encontrados ao problema. Um pouco mais 
concretamente, suponha a existência de um certo problema P, para o qual, após 
exaustiva análise, determinou-se um limite de gasto de recursos computacionais 
da ordem de X. Por outro lado, o algoritmo que foi desenvolvido para solucioná-
lo, gasta recursos da ordem de X2. Bem, é muito fácil perceber que existe uma 
grande diferença entre este dois fatores e o algoritmo pode e deve ser melhorado. 
 Este raciocínio também pode (e deve) ser aplicado para um limite 
mínimo. Se foi provado um dado limite mínimo para o problema (como no caso 
acima) e um algoritmo gasta menos tempo do que isto para solucioná-lo, duas 
coisa podem estar acontecendo: a algoritmo tem algum erro e não produz o 
resultado corretamente para todos os casos; ou, a análise do problema não foi 
bem feita. Mas uma vez, a tarefa de análise propicia referências valiosas para o 
trabalho futuro. Esta lógica também serve para trabalhar com um limite superior 
do problema (veja [CLR91]). 
 Os limites mencionados no parágrafo anterior são de fundamental 
importância para o trato analítico de algoritmos e problemas. Conhecidos com 
 17
limites inferior e superior, eles fazem com que a subjetividade de um processo de 
análise fique sujeita a intervalos muito claros. Suponha que foram determinados 
dois limites para um problema: 10 como limite inferior e 50 como superior (estes 
valores são hipotéticos). Isto significa dizer que este problema nunca poderá ser 
solucionado com consumo de recursos menor do que 10 e maior do que 50. 
 Se fosse dito que o problema acima tem intervalos limites entre 1 e 100, 
não estaria errado pois este intervalo engloba o primeiro dado no parágrafo 
anterior. Perceba, entretanto, a tamanha diferença de realidade deste problema 
(supondo que o primeiro intervalo esteja correto), pois não tendo uma análise 
ajustada ao seu comportamento real, estaremos inviabilizando o uso prático dos 
resultados obtidos, que são verdadeiros, mas não são fieis. 
 Resumindo, nesteprocesso devemos sempre buscar a análise mais justa 
possível, mesmo que já tenhamos encontrado limites que “pareçam” bons. 
 
2.2.2 Estudo de casos 
 Por mais que, ao expressarmos um algoritmo tenhamos clareza da sua 
ação e seus passos sejam extremamente bem definidos, o comportamento nem 
sempre segue esta regra. 
 Vamos analisar um pequeno exemplo, expresso pelo algoritmo 2.1, que 
faz a busca de um valor informado dentro de um vetor de N números inteiros. 
Este algoritmo percorre sequencialmente este vetor e, ao encontrar o elemento 
desejado, encerra sua busca. Ele necessita olhar todas as posições do vetor para 
determinar se o elemento está ou não presente. Nenhuma informação a respeito 
do conteúdo do vetor é conhecida, com por exemplo a ordenação deste, e 
aproveitada. 
 Vamos então, utilizando este algoritmo, simular algumas situações de 
busca. Todas estas situações vão utilizar o vetor abaixo como elemento de 
pesquisa: 
 
15 5 13 10 1 0 8 7 3 9 
1 2 3 4 5 6 7 8 9 10 
 
 Em primeiro lugar, vamos procurar neste vetor o valor X = 1. Após 
algum trabalho (5 iterações do laço enquanto, para sermos exatos), o valor 1 será 
encontrado na posição 5 do vetor. Se formos buscar o valor X = 9, ele será 
encontrado, após 10 iterações, na décima posição do vetor. Para o valor X = 15, 
bastará uma única iteração. Finalmente, quando procurarmos o valor X = 25, 
 18
percorreremos todo o vetor e verificaremos que ele não existe (após 11 iterações 
do laço). 
 
procedimento busca( v: vetor[1..N] de inteiro; x: inteiro ): inteiro 
var 
 i: inteiro; 
início 
 i := 1; 
 enquanto i <= N e v[i] <> x faça 
 i := i + 1; 
 fim 
 se i > N então 
 retornar -1; /* Não achou o elemento buscado */ 
 senão 
 retornar i; /* Encontrou na posição i */ 
 fim 
fim 
Algoritmo 2.1 - Busca em um vetor não ordenado. 
 
 É fácil perceber que um mesmo algoritmo, com o mesmo vetor de 
trabalho, executa de forma diferenciada a sua tarefa sob a ótica do trabalho 
realizado. Como isto pode ser explicado? 
 Na verdade estamos falando de casos de um algoritmo. Todo e qualquer 
problema e/ou algoritmo apresenta situações diversas conhecidas como os seus 
casos de execução. Em particular, três destes casos são do nosso interesse direto. 
Vejamos: 
a) Melhor caso: é aquela situação, dentre todas as possíveis, onde o algoritmo 
(ou problema) realiza a sua tarefa com menor consumo de recursos possível, 
ou seja, onde ele menos trabalha. No exemplo acima, isto acontece quando o 
valor buscado se encontra na primeira posição do vetor, pois com apenas uma 
verificação o trabalho termina. 
b) Pior caso: é a situação inversa ao melhor caso, onde o trabalho realizado é o 
maior dentre todos os possíveis. No exemplo, isto ocorrerá sempre que o valor 
desejado não estiver no vetor, pois teremos que verificar todo ela para darmos 
esta garantia. 
c) Caso médio: este caso é a média de todos os casos conhecidos para o 
problema ou algoritmo em questão. 
 Um comentário especial deve ser feito par ao caso médio. Como ele é a 
média dos casos conhecidos, o universo de amostragem deve ser abrangente o 
suficiente para permitir uma boa expressão de “trabalho médio”. Por exemplo, se 
 19
para a busca em vetor com algoritmo 2.1 conhecemos somente os dois casos 
extremos: uma iteração para o melhor caso; e, uma iteração a mais do que o 
tamanho do vetor (N+1) para o pior caso. Assim, a média seria 1 1
2
2
2
+ +
=
+( )n n
 
e, com isso, estamos afirmando que, em qualquer conjunto de casos, teremos este 
trabalho, o que nem sempre é verdade. 
 Então, para que a análise de caso médio tenha validade, devemos 
conhecer uma quantidade “razoável” de casos. É este conhecimento prévio que 
torna esta análise a mais difícil dentre as possíveis pois, na maioria das vezes, não 
sabemos nada sobre o algoritmo ou problema além do que ele se propõem a 
solucionar. 
 
 
2.3 Comportamento Assintótico de Funções 
 
2.3.1 Introdução 
 O que funções matemáticas e análise de algoritmos tem em comum? 
Provavelmente mais do que a maioria dos programadores tenha idéia. Neste item, 
repousa um dos elos de ligação entre a informática e elementos do cálculo 
matemático (principalmente cálculo diferencial, veja [CLR91]). 
 
2.3.2 Crescimento de funções 
 Todos nós, sem exceção, em algum momento, aprendemos e fizemos 
gráficos cartesianos com funções matemáticas dadas. Poucos, entretanto, pararam 
para analisar estes gráficos. 
 
Figura 2.1 - Gráficos de funções no Plano Cartesiano. 
 20
 Vamos considerar o caso expresso na figura 2.1, onde existem duas 
funções f(x) = 2x + 1 e g(x) = x2. O processo de desenho é simples e conhecido 
de todos: se atribuem valores ao elemento x das funções, encontra-se o valor da 
função para cada valor atribuído e forma-se um par de coordenadas cartesianas 
com ambos. Da marcação destes pares no gráfico, resulta o desenho da função. 
 Veja a baixo uma pequena parcela destes intervalos e seus respectivos 
valores: 
x f(x) = 2x + 1 g(x) = x2 
0 1 0 
1 3 1 
2 5 4 
3 7 9 
4 9 16 
5 11 25 
: : : 
10 21 100 
: : : 
30 61 900 
: : : 
 Observe atentamente que os valores resultantes da função g(x) são, 
inicialmente, menores do que aqueles da função f(x) (até x=2). Após um ponto, 
além deles serem maiores, a taxa proporcional de crescimento da função g(x) é 
muito maior. Isto nos permite dizer que a função g(x) cresce muito mais 
rapidamente do que a função f(x). 
 Recordando agora noções de cálculo diferencial, vemos que o cálculo de 
derivadas de funções nos dá uma interpretação análoga. Sabemos que, ao 
derivarmos uma função em x, conhecemos qual o seu sentido de crescimento (se 
positivo ou negativo), analisando os pontos de interseção obtidos. Derivando 
novamente (encontrando a segunda derivada), encontramos a taxa deste 
crescimento. Se fizermos isto com o exemplo dado antes, veremos que, mais uma 
vez, a função g(x) tem taxa de crescimento maior. Veja: 
 f(x) = 2x +1 f’(x) = 2 f”(x) = 0 
 g(x) = x2 g’(x) = 2x g”(x) = 2 
 Muito bem, suponha agora que as funções f(x) e g(x) representam o 
trabalho realizado por dois algoritmos F e G, respectivamente, para uma entrada 
de tamanho x. Qual dos dois você escolheria para ser implementado? 
Obviamente o algoritmo F pois ele trabalha menos do G a medida que a entrada 
 21
aumenta de tamanho ( o seu gráfico nos disse isto quando comparamos com a 
função g(x)). 
 É neste ponto que entra o uso de funções no trato com algoritmos. Todo 
o nosso processo de análise culminará em uma função que irá expressar o 
comportamento do algoritmo sob determinados parâmetros. Desta forma, ao 
compararmos as funções entre si por taxa de crescimento, estaremos comparando 
os algoritmos e determinando aquele que trabalhará mais ou menos de acordo 
com a situação. 
 Quando estamos comparando funções de acordo com a sua taxa de 
crescimento, podemos observar que são os termos de maior grau do polinômio 
formador da função que determinam a parte principal da sua curva. Os termos de 
menor grau e constantes multiplicativas, importantes na determinação do valor 
nominal da função, aqui contribuem apenas para a posição gráfica daquela. Desta 
forma, é possível criar uma pequena tabela onde as funções são organizadas por 
tipo, em ordem crescente de taxa de crescimento. Veja: 
 
 
Função Descrição Exemplos 
Constantes São funções que tem valor 
constante independente da 
variável x 
f(x) = 1 
f(x) = 3 
f(x) = 10 
Logarítmicas São funções expressas 
através de logaritmos 
f(x) = log x 
f(x) = 3log x 
f(x) = log( x+1) 
Lineares São as funções expressas 
com equações de grau 1 e 
que formam uma reta no 
gráfico cartesiano 
f(x) = 2x + 1 
f(x) = 4x 
f(x) = x + 2Quadráticas São equações de grau 2 
(segundo grau) e formam 
uma parábola no gráfico 
f(x) = x2 
f(x) = 3x2 + 2x + 1 
f(x) = 4x2 + 2 
Cúbicas Equações de terceiro grau f(x) = x3 + 2x 
f(x) = 3x3 
f(x) = 2x3 + x2 + 2 
Quárticas Equações de quarto grau f(x) = 2x4 + 3x + 1 
f(x) = x4 + x3 
: : : : : : : : Obs: Continua com as 
funções aparecendo na 
ordem crescente de grau. 
 
Exponencial de 
base 2 
São funções onde a base da 
exponencial é 2 
f(x) = 2x 
f(x) = 2x+1 + 2 
f(x) = 2x + x2 
 22
Exponencial de 
base 3 
São funções onde a base da 
exponencial é 3 
f(x) = 3x 
f(x) = 3x + 2x 
f(x) = 32x + 1 
: : : : : : : : Obs: Continuam as funções 
em ordem crescente de base 
da exponencial 
 
 
 Algumas observações são importantes sobre este tema. Em primeiro 
lugar, não trabalharemos com funções de crescimento negativo, pois não há 
nenhum algoritmo que trabalhe menos a medida que seus dados aumentam de 
tamanho. Depois, estamos interessados nos valores de função no primeiro 
quadrante do plano cartesiano, pois teremos, no mínimo, um número maior ou 
igual a zero de tamanho de entrada, nunca negativo. 
 Finalmente, uma observação fundamental: entre cada grupo de funções 
da tabela acima podem ser inseridos os grupos inferiores. Por exemplo, entre as 
funções lineares e as quadráticas, estão aquelas com um termo composto de um 
elemento linear e um elemento logarítmico: f(x) = x log x. Como estes termos são 
multiplicativos e não são constantes, eles não podem ser desconsiderados na 
classificação. O mesmo raciocínio vale para os demais quadros da tabela. Para 
outros detalhes, consulte a bibliografia [CLR91], [AU92], [Knu73], [Man89], 
entre outros. 
 Vamos agora realizar um exercício como exemplo desta classificação. 
Exercício: Classifique as funções a seguir por taxa de crescimento: 
 x
2
 1 2x + 1 x2 log x 2x 3x + 1 
 5 x log x log log x 2xx2 3xlog x2 log x2 
Resposta: 
 1, 5, log log x, log x2, 2x + 1, x log x, x2, x2 log x, 2x, 
2xx2, 3x + 1, 3xlog x2 
 Existe uma procedimento que pode ser adotado para fazer a classificação 
ou comparação entre funções. Em primeiro lugar, tente fazer isto utilizando a 
tabela acima, onde a solução é direta. Se não foi possível, tente desenhar o gráfico 
das funções, mas faça isso para um intervalo grande o suficiente de x para que as 
funções esteja bem definidas no plano. Em último lugar, tente calcular as 
derivadas das funções e compare os resultados. 
 
2.3.3 Classificação assintótica 
 Pelo que já foi dito, aprece óbvio que, ao compararmos algoritmos 
através de suas funções, não estamos interessados em um valor específico da 
 23
variável x, mas sim em quanto esta função cresce a medida que este x aumenta. 
Assim sendo, o uso de sinais matemáticos convencionais (maior, menor, igual, 
etc...) não se adequa ao caso, pois estes são muito restritos. 
 Por exemplo, analise o caso citado como exemplo na figura 2.1. Até o 
valor x = 2, a função f(x) tem um valor nominal maior do que a função g(x). 
Assim, como vamos dizer que f(x) é menor do que g(x)? É uma imprecisão e uma 
incoerência matemática. 
 Para solucionar este problema utiliza-se uma classificação alternativa. 
Esta classificação lança mão de cinco classes assintóticas que comparam funções 
através da sua taxa de crescimento. Estas classes estão listadas abaixo: 
 
a) Classe O  Oh Grande 
Esta classe estabelece uma relação análoga ao sinal matemático “menor 
ou igual que” enquanto taxa de crescimento. Assim, dizer que f(x) ∈ Ο (g(x)) 
ou f(x) = Ο (g(x)) (lê-se: f(x) pertence ou é Oh grande de g(x)), significa 
dizer que a função f(x) tem taxa de crescimento menor ou, no máximo, igual 
à função g(x). 
b) Classe Ω  Ômega Grande 
Da mesma forma, esta classe substitui a relação convencional “maior ou 
igual que” sob a ótica do crescimento de funções. Quando classificamos uma 
função f(x) como pertencendo à classe Ω de outra função g(x), na forma 
f(x) ∈ Ω(g(x)) ou f(x) = Ω(g(x)), estamos nos referindo ao fato da função 
f(x) crescer igual ou mais do que a função g(x). 
c) Classe Θ  Theta 
Procede-se como as anteriores, mas estabelecendo uma relação de 
igualdade, ou seja, ambas as funções tem taxa de crescimento equivalente. A 
relação deve ser escrita também como as anteriores: f(x) ∈ Θ(g(x)) ou 
f(x) = Θ(g(x)). 
d) Classe o  Oh Pequeno 
Tem a mesma implicação da classe O, mas não admite a igualdade entre 
as duas funções. Ou seja, as funções não podem ter a mesma taxa de 
crescimento. Expressa-se da seguinte forma: f(x) ∈ o(g(x)) ou f(x) = o(g(x)). 
Neste caso, a função f(x) cresce menos do que a função g(x). 
e) Classe Ω  Ômega Pequeno 
Semelhante a anterior, acompanha a relação convencional “maior”, sem 
admitir a igualdade entre as duas funções quanto ao crescimento destas. Deve 
ser expressada como segue: f(x) ∈ Ω(g(x)) ou f(x) = Ω(g(x)), onde estamos 
dizendo que a função f(x) cresce mais do que a função g(x). 
 24
 
 É importante salientar que, quando classificamos uma função com as 
classes assintóticas, nem sempre precisamos duas delas. Não há nenhum 
problema de utilizarmos uma das envolvidas de forma fixa, como por exemplo: 
f(x) ∈ O( x2 ) ou f(x) = O( x2 ) 
 No caso acima estamos apenas dizendo que a função f(x) tem um limite 
superior de crescimento dado por x2, pois cresce menos ou igual a este valor. Na 
verdade podemos e devemos utilizar esta notação para estabelecer os limites 
inferior e superior de um algoritmo, conforme descrito no item 2.2.1. 
 Uma outra observação a ser feita é quanto ao sinal utilizado para 
estabelecer a relação entre a função e a classe. Nos casos mostrados foram 
utilizados ∈ e =. Ambos poder aparecer, ficando a critério de cada um a escolha 
daquele que for mais familiar. Não há nenhum problema quanto ao uso do sinal 
de igualdade (=) neste caso, pois ele tem o significado de atribuição e não de uma 
relação numérica. 
 Veja agora uma pequena lista de exemplos de funções e suas 
classificações assintóticas admissíveis: 
 
f(x) g(x) Classificação Observações 
2x + 3 x2 2x + 3 = 0( x2 ) Veja que todas estas 
 x
2
 = Ω( 2x + 3 ) classificações são 
 2x + 3 = o( x2 ) possíveis 
 x
2
 = Ω( 2x + 3 ) 
x
2
 + 2x x2 + 5 x2 + 2x = Θ(x2 + 5) Observe que, en-
quanto taxa de cres-
cimento, estas fun-
ções são iguais. 
log x x log x log x = O( x log x ) Veja que todas estas 
 x log x = Ω( log x ) classificações são 
 log x = o( x log x ) possíveis 
 x log x = Ω( log x ) 
 Observe ainda que, na maioria dos casos, serão admissíveis várias 
classificações para uma mesma função. Nestes casos, sempre que possível, utilize 
a classificação mais justa e apertada (próxima do real) que conseguir. Isto 
facilitará a tarefa de escolha e comparação entre os algoritmos. 
 25
 
2.4 Técnicas de Análise 
 
2.4.1 Introdução 
 Agora que já temos conhecimentos sobre a análise de algoritmos e 
formamos um referencial teórico para o caso, vamos estudar formas práticas de 
realizarmos esta análise. 
 Como vimos no capítulo anterior, existem duas formas de se expressar 
um algoritmo: iterativa e recursivamente. Bem, estes dois tipos de algoritmos 
necessitarão de análises separadas. A razão disto é que, no algoritmo recursivo, 
nunca temos clareza do momento no qual a recursão termina e fica muito difícil 
quantificar o gasto de recursos. 
 Assim, primeiramente veremos como analisar algoritmos iterativos e 
depois, no próximo capítulo, ao estudarmos relações de recorrência estudaremos 
as formas de análise um algoritmo recursivo. 
 
2.4.2 Análise de algoritmos iterativos 
 Antes de mais nada, vamos retomar uma questão já abordada: o que 
queremos analisar? Como havíamos visto, o processo de análise visa aquantificação dos recursos computacionais gastos durante a execução da tarefa 
proposta. Por recursos podemos entender tudo que é caro ao processo. Para 
aprendermos as técnicas de análise, vamos especificar melhor isto. 
 Voltemos ao exemplo dado no algoritmo 2.1, que faz a busca de um 
elemento dentro de um vetor. O que neste algoritmo caracteriza o consumo de 
recursos? Olhando de forma mais detalhada, observaremos que todas as 
operações realizadas gastam algum tipo de recurso do sistema. 
 Como são, desta forma, as operações realizadas pelo algoritmo que 
consomem os recursos, resta-nos perguntar quais são elas? Neste caso, 
detalhando o procedimento, veremos que estas operações são as comparações, 
atribuições, somas e indexações ao vetor de trabalho. Estas últimas por fazerem, 
além do cálculo de posicionamento, um acesso à memória que é lento. 
 Para efeito deste trabalho, utilizaremos cinco tipos ou grupos de 
operações básicas para análise: 
a) Somas e subtrações (+ -); 
b) Multiplicações e divisões (* /); 
c) Atribuições (:=); 
d) Testes (se, enquanto,...); 
 26
e) Indexações de vetor ([]). 
 Perceba que o processo de análise não é rígido, ou seja, se necessitar 
analisar outro tipo qualquer de operação, o processo a ser descrito é análogo. Da 
mesma forma, muito autores não caracterizam a indexação como uma operação 
computável e, em alguns casos, até admissível, por entender que ela pode ser 
traduzida em operações mais básicas, com somas, atribuições e testes. Não 
procederemos assim por que tal grau de detalhismo não acrescenta ganhos 
substanciais ao processo como veremos a seguir. 
 Uma vez que sabemos o que desejamos analisar, precisamos responder a 
uma única questão adicional: quantas vezes o algoritmo em análise executa cada 
uma destas operações listadas? Nesta questão está posto todo o segredo do 
processo analítico de algoritmos. Basta respondê-la que saberemos o 
comportamento daquele. 
 Esta forma de proceder apresenta uma vantagem adicional já citada: é 
independente das condições de implementação. Sabendo estas quantidades, para 
cada operação, bastará conhecer o tempo de cada operação em uma máquina ou 
linguagem específica para sabermos o desempenho real com uma fidelidade 
bastante aproximado. 
 
2.4.3 Processo de análise 
 Este trabalho apresenta uma técnica particular de análise baseada (e 
muito) naquela tradicional da bibliografia da área, acrescida da experiência 
adquirida nas disciplinas ministradas sobre este assunto. Esta técnica é, 
necessariamente, dividida em pequenos passos que, se forem levados ao final, 
produzirão no resultado correto. 
 Antes de mais nada, é fundamental uma boa compreensão do algoritmo. 
Esse é o primeiro passo. É impossível análise qualquer coisa que não se conheça 
bem e, para conseguir isto, a melhor alternativa continua sendo um teste de mesa 
bem feito. Ou seja, execute o algoritmo com lápis e papel para entender 
claramente a sua lógica. Lembre-se de que nem sempre o algoritmo em análise 
foi feito por você. 
 Agora, partindo do pressuposto que o passo anterior foi realizado, 
veremos a próxima etapa. Em primeiro lugar, como já vimos antes, os algoritmos 
realizam procedimentos diferentes para cada um dos seus casos e, em especial, 
para o melhor e pior caso. Como conhecemos estes casos (ou devemos conhecê-
los  também para isso foi realizada a etapa citada no parágrafo anterior) e não 
os demais, vamos trabalhar somente com eles. 
 Assim, a próxima etapa será avaliar quantas vezes passaremos por cada 
uma das linhas do algoritmo em cada um dos casos. Isto é feito para facilitar a 
 27
tarefa de quantização das operações, que é o próximo passo. Utilizando o 
exemplo mencionado antes, uma boa alternativa é formar uma tabela, com as 
linhas do algoritmo formando as linhas da tabela e as quantidades serão as 
colunas. Veja a tabela 2.1. 
 
No Algoritmo Passagens 
no melhor 
caso 
Passagens 
no pior 
caso 
1 i := 1; 1 1 
2 enquanto i <= N e v[i] <> x faça 1 N + 1 
3 i := i + 1; 
 
N 
4 fim 
  
5 se i > N então 1 1 
 6 retornar -1; 
 
1 
7 Senão 
  
8 retornar i; 1 
 
9 Fim 
  
Tabela 2.1 - Contagem de passagem pela linhas do algoritmo de busca. 
 
 Observe aqui uma particularidade dos controladores de laço (enquanto, 
para, repita,....). Eles, no pior caso, executam uma vez mais do que o tamanho do 
seu escopo, por necessitarem “estourar” o seu limite. No caso acima, no laço 
enquanto, o final da iteração de pior caso se dará quando a variável i invalidar a 
primeira das condições ( i <= N ). Como o incremento de i é linear, isto 
acontecerá quando i = N + 1. Já a parte interna do laço é executada uma vez 
menos do que o controlador, pois ela não tem uso quando for verificado o estouro 
(observe isso no seu teste de mesa). Da mesma forma, os comandos fim e senão 
são pró-formas, pois apenas informam ao controlador do algoritmo pontos de 
continuidade. 
 Continuando o nosso processo de análise, o próximo passo será avaliar, 
em cada uma das linhas do algoritmo, quantas operações básicas serão realizadas 
em cada caso. Isto está posto na tabela 2.2, para a qual se fazem necessários 
alguns comentários: 
a) Na linha 1, ocorre somente uma atribuição em ambos os casos, já que ela 
somente inicializa a contagem de posições e não tem influência direta no 
algoritmo; 
b) O laço enquanto (linha 2), realiza dois testes, i <= N e v[i] <> x, a cada 
passagem. Este passo executa ainda uma indexação de vetor a cada passagem. 
Para o pior caso ocorre uma pequena alteração no comportamento do laço, 
 28
 
 29
pois na última iteração será realizado somente o primeiro dos testes que, ao 
ser falso, encerrará a execução desta parte. Note que nem todas as linguagens 
(quando da implementação), procedem desta forma e, se desejar, contabilize 
ambos os testes; 
c) Na parte interna do laço (linha 3), ao se incrementar a variável i, é realizada 
uma soma e uma atribuição; 
d) Na quarta linha (fim) não deve ser contabilizada pois, conforme foi dito, não 
toma tempo de execução. O comando senão (linha 7) apresenta a mesma 
característica e não representa um teste adicional; 
e) A quinta linha realiza um teste e, após este, retorna um dado valor. Note que o 
teste vale para os dois casos, mas somente uma das partes internas do mesmo 
é executa para cada um deles. Foi ainda considerado que o retorno do valor 
pressupõem a sua atribuição para alguma variável interna e esta deve ser 
contada. 
 A parte final do processo se dá ao totalizarmos as quantidades. Por 
exemplo, neste caso, faremos 2 atribuições, 3 testes e 1 indexação no melhor caso 
e N somas, N+2 atribuições, 2N+2 testes e N indexações para o pior caso, ambos 
em um vetor de N elementos. 
 Na tabela 2.3 é realizada a análise do método de ordenação bolha (veja 
[Aze96]) para um vetor de N elementos inteiros. Como todo o método de 
ordenação, o melhor caso para o bolha é encontrar o vetor já organizado na ordem 
desejada (já ordenado), enquanto que o pior caso ocorre quando os elementos do 
vetor estão na ordem inversa a desejada. 
 Por este exemplo ser mais complexo, faça o seu teste de mesa, analise as 
quantificações e observe com atenção as características listadas a seguir. Em 
primeiro lugar vamos analisar o melhor caso: 
a) Na linha 1 o algoritmo passa uma única vez; 
b) Na linha 2 serão duas passadas, pois existe uma inicial e, dentro esta, quando 
da passagem completa pelo vetor sem fazer nenhuma troca, ocorrerá a 
verificação para o encerramento do laço já que a variável flag continua falsa; 
c) Internamente ao laço, as linha serão executadas apenas uma vez; 
d) Observe agora a linha 4. Por força do laço enquanto, chegaremos nela 1 única 
vez. Por outro lado, nesta única vez, ela irá executarN vezes, pois também é 
um laço. Assim, o número total de passagens é a multiplicação das duas, ou 
seja, N; 
e) Ainda na linha 4, vamos olhar o laço para internamente. Na primeira iteração, 
ele atribui o valor inicial à variável de controle e verifica se não houve estouro 
do limite superior. Nas demais, ele soma 1 à variável (i := i+1) e verifica o 
 30
 31
estouro. Desta forma, veja uma pequena simulação deste laço variando de 1 
até 5: 
1a vez => i := 1 => testa se i <= 5 => O.k. 
2a vez => i := i + 1 => testa se i <= 5 => O.k. 
3a vez => i := i + 1 => testa se i <= 5 => O.k. 
4a vez => i := i + 1 => testa se i <= 5 => O.k. 
5a vez => i := i + 1 => testa se i <= 5 => O.k. 
6a vez => i := i + 1 => testa se i <= 5 => falso e fim 
Veja então que, além de executar uma vez a mais a linha controladora do laço, 
o número de tarefas executadas pode ser diferente. É por essa razão que as 
colunas da tabela, para a contagem de operações desta linha apresentam 
valores diferentes; 
f) Obviamente, dentro do laço para, o número de execuções será de uma vez 
menos que ele. 
 Para o pior caso, a situação é um pouco mais complexa. Observe os 
comentário a respeito da análise feita: 
a) A primeira linha, assim como no melhor caso, será executada uma única vez 
na inicialização da variável de controle; 
b) Na linha 2, ocorrerão tantas passagens quantas forem as trocas feitas no vetor. 
Nesta caso, a primeira passagem colocará o maior elemento na sua posição. A 
segunda varredura colocará o segundo maior elemento na posição, e assim por 
diante. Desta forma, serão necessárias N-1 passagens para posicionar todos os 
elementos (veja que não são N, pois a última passagem, ao trocar o penúltimo 
maior, já colocará o menor elemento na sua posição) e uma a mais para 
certificar que estão todos ordenados, sendo que nenhuma troca será feita. 
Portanto, serão N passadas no laço enquanto; 
c) Dentro do laço enquanto, toda a linha será executada 1 vez menos do que o 
controlador do laço. Portanto, N-1 vezes; 
d) Considere agora o laço para da linha 4. Ele, de forma isolada, seria executado 
N vezes, conforme visto nos comentários da análise de melhor caso. Como, 
entretanto, ele está dentro do laço enquanto, será executado, como qualquer 
uma das outras linhas, N-1 vezes. Portanto, o número total de execuções será 
a multiplicação das duas, ou seja, N(N-1) vezes; 
e) A linha 5 teve o mesmo raciocínio da linha 4. Ela seria executada N-1 vezes 
por estar dentro do laço para. Já pelo laço enquanto, outro tanto. Assim o 
total é a multiplicação de ambas: (N-1)(N-1) vezes; 
f) Dentro do teste, nas linhas 6 à 9, foi aplicada outra técnica. No pior caso, na 
primeira vez (laço enquanto) serão necessárias N-1 trocas para posicionar o 
maior elemento (veja o teste de mesa). Na segunda vez, o número de trocas 
 32
cai uma unidade, pois não haverá troca com o último elemento. Na terceira 
vez, serão N-3 trocas e assim sucessivamente até que, na última vez, haverá 
uma só troca. Portanto o número total de trocas e, consequentemente, de 
execução destas linhas será ( ) ( ) ( ) ( )N N N N N− + − + − + + + + = +1 2 3 3 2 1 1
2
" . O 
resultado do somatório pode ser obtido das propriedades dos somatórios ou 
através da soma dos termos de uma progressão aritmética  PA. 
 
 Mais uma vez, totalizam-se as colunas para saber a quantidade final de 
operações realizadas em cada um dos casos. A coluna que informa o número total 
de passagens em cada uma das linha não tem porquê ser totalizada. Da mesma 
forma, não há razão para termos uma coluna destinada as operações de 
multiplicação e divisão, pois elas não estão presentes no algoritmo. 
 
2.4.4 Considerações gerais 
 Todo o processo de análise é meticuloso e detalhista. Para facilitá-lo ou 
torná-lo mais objetivo existem algumas considerações (ou regras) importantes. 
Veja: 
a) Contabilize apenas as linhas que realizam operações. Assim, comentários e os 
comandos fim e senão, não representam gastos; 
b) Sempre que houverem laços aninhados (um dentro do outro), lembre-se de 
que o(s) mais externo(s) faz(em) que o(s) interno(s) seja(m) executado(s) 
tantas vezes quanto qualquer outra linha interna. Desta forma, multiplique os 
totais individuais tantas vezes quantas necessário; 
c) Tome cuidado com os controladores de laço. Abra-os e analise o que acontece 
internamente a cada um deles; 
d) Quando existir, em um algoritmo, uma chamada a um procedimento ou outro 
algoritmo, analise este primeiro e substitua os totais encontrados nas 
respectivas colunas do algoritmo original, pois estes são os custos daquela 
linha; 
e) Nos testes, com cláusulas então e senão, lembre-se que apenas uma delas é 
executada a cada momento; 
f) Se você quiser a complexidade assintótica do algoritmo, classifique somente a 
expressão obtida no total da coluna; 
g) Propriedades matemáticas, como funções, somatórios e progressões são 
importantes para totalizar corretamente as operações. Procure um bom livro 
de matemática para auxiliá-lo; 
 33
h) Somente analise os algoritmo e casos que você conheça bem. Antes da análise 
é importante realizar um teste de mesa completo no algoritmo; 
i) Nunca some a linha dos totais, pois ela só tem sentido individualizada; 
j) Operações mais complexas devem sempre ser detalhadas e analisadas na sua 
composição. Por exemplo, laços, raiz quadrada, etc.. Estas operações, quando 
não for possível detalhar, devem ser quantificadas em uma nova coluna e 
informadas em separado; 
k) Existem algoritmos que tem o melhor e o pior casos iguais, como, por 
exemplo, a soma ou multiplicação de duas matrizes. Isto não significa que 
eles tenha um caso só. Eles tem ambos (só que iguais) e devem ser analisados 
em separado; 
l) Finalmente, em alguns casos não será necessário nem interessante fazer uma 
análise tão detalhada quanto a proposta. Pode ser que saber somente quantas 
trocas ou testes ou outra operação qualquer será feita, sem esmiuçar em 
demasia. Isto é muito frequente na bibliografia, inclusive para a análise de um 
problema. 
 
2.5 Exercícios 
1. Por que crescimento de funções, uma ferramenta matemática, é fundamental 
para a análise de algoritmos? 
2. Escreva e analise um algoritmo que solucione um polinômio genérico na forma 
P(x) = A0 + A1X + A2X2 + ..... + AnXn. É possível melhorá-lo? Analise outras 
formas possíveis de solução para este caso. 
3. É possível diminuir o número de passos do algoritmo de ordenação pelo 
método de bolha descrito na tabela 2.3? Esta redução, se obtida, também diminui 
a complexidade assintótica? 
4. Segundo Paulo Carvalho (Algoritmos Geométricos para Computação Gráfica 
 SIBGRAPI, 1993): “É importante frisar que as notações O e Ω dão apenas 
estimativas, que podem depender das condições de análise do algoritmo. Assim, 
não há nenhuma contradição de um algoritmo ter complexidades O(n2) e O(n), 
pois ter complexidade O(n) implica em ter complexidade O(n2)”. Explique esta 
afirmação. 
5. Classifique as funções abaixo por taxa de crescimento: 
100n + log n n + log2 n n2 log-1 n n log2 n 
 n
0.5 log5 n n2n 3n 
 log n log n2 22n log log n 
 n log n 
 34
 
6. Utilize as funções acima e classifique-as entre si com as classes assintóticas. 
7. Escreva e analise um algoritmo iterativo que faça uma pesquisa binária em um 
vetor de n elementos inteiros. 
8. Marque como verdadeiro ou falso as afirmações abaixo e justifique cada uma 
delas: 
( ) Se a complexidade de um algoritmo para o melhor caso é f(n) , então o 
número de passos que ele efetua, para qualquer entrada é Ω(f(n)). 
( ) Se a complexidade de um algoritmo para o pior caso é f(n) , então o número 
de passos que ele efetua, para qualquer entrada é Θ(f(n)). 
( ) A complexidadede melhor caso para um algoritmo é necessariamente maior 
do que qualquer limite inferior para o problema. 
( ) Se duas funções f(n) e g(n) são crescentes e f(n) = O(h(n)) e g(n) = O(v(n)), 
então f(n) + g(n) = O( h(n) + v(n) ). 
( ) Se duas funções f(n) e g(n) são crescentes e f(n) = O(h(n)) e g(n) = O(v(n)), 
então f(n) - g(n) = O( h(n) - v(n) ). 
( ) O melhor caso de um algoritmo é sempre menor que seu caso médio que, 
por sua vez, é menor do que o pior caso. 
( ) Se a complexidade de melhor caso de um problema é f(n), então deve existir 
um algoritmo que o soluciona em tempo O(f(n)). 
 
9. Preencha as lacunas das afirmações abaixo: 
a) Se f(n) = Θ(g(n)) e g(n) = Θ(h(n)), então f(n) = ______(g(n)). 
b) Se f(n) = O(g(n)) e g(n) = O(h(n)), então f(n) = ______(g(n)). 
c) Se f(n) = Ω(g(n)) e g(n) = Ω(h(n)), então f(n) = ______(g(n)). 
d) Se f(n) = o(g(n)) e g(n) = o(h(n)), então f(n) = ______(g(n)). 
e) Se f(n) = Ω(g(n)) e g(n) = Ω(h(n)), então f(n) = ______(g(n)). 
f) f(n) = _____(f(n)). 
g) f(n) = Θ(g(n)) se, e somente se, g(n) = ______(f(n)). 
h) f(n) = O(g(n)) se, e somente se, g(n) = ______(f(n)). 
i) f(n) = Ω(g(n)) se, e somente se, g(n) = ______(f(n)). 
 
 35
10. Considere duas matrizes A e B, quadradas de ordem n, e três algoritmos assim 
descritos: 
• O algoritmo X deve fazer a soma das duas matrizes; 
• O algoritmo Y deve fazer a multiplicação das duas matrizes; 
• O algoritmo Z recebe um valor f (booleano) como parâmetro e, se f 
for verdadeiro, faz uma chamada ao algoritmo X. Caso contrário, 
executa o algoritmo Y. 
Com estas definições, responda as seguintes questões: 
a) Escreva os três algoritmos. 
b) Analise o melhor caso, o caso médio e o pior caso dos algoritmos X e Y. 
c) Analise o melhor e o pior caso do algoritmo Z. 
d) Considerando a existência de uma quantidade p que representa a 
probabilidade de que a variável f seja verdadeira, responda qual é o caso 
médio do algoritmo Z. 
11. Escreva e analise um algoritmo que busca o menor e o maior elemento dentro 
de um vetor de n elementos. Este algoritmo deve executar esta tarefa em uma 
única passagem no vetor. 
12. Escreva e analise um algoritmo que, dada uma matriz quadrada de ordem n, 
encontre a inversa desta (utilize a regra dos cofatores para inverter a matriz). 
13. Analise os algoritmos de ordenação descritos a seguir. Todos eles trabalham 
com um vetor de n elementos inteiros. 
a) procedimento ordenaA( var v:vetor[1..N] de inteiros ) 
var 
 i, j, min, aux: inteiros; 
início 
 para i := 1 até N-1 faça 
 min := i; 
 para j := i+1 até N faça 
 se v[j] < v[min] então min := j; 
 aux := v[i]; 
 v[i] := v[min]; 
 v[min] := aux; 
 fim 
fim 
 
 
 
 36
b) procedimento ordenaB( var v:vetor[1..N] de inteiros ) 
var 
 i, j, aux: inteiros; 
início 
 para i := 2 até N faça 
 aux := v[i]; 
 j := i – 1; 
 enquanto j > 0 e v[j] > aux faça 
 v[j+1] := v[j]; 
 j := j – 1; 
 fim 
 v[j+1] := aux; 
 fim 
fim 
c) procedimento ordenaC( var v:vetor[1..N] de inteiros ) 
var 
 i, j, aux: inteiros; 
início 
 para i := 2 até N faça 
 aux := v[i]; 
 j := i; 
 v[0] := aux; /* Sentinela */ 
 enquanto v[j-1] > aux faça 
 v[j] := v[j-1]; 
 j := j – 1; 
 fim 
 v[j] := aux; 
 fim 
fim 
 37
3 
 
Relações de Recorrência 
 
 
 
 
 
 
 
3.1 Introdução 
 
 No capítulo anterior, verificamos a razão e forma de analisarmos 
algoritmos. Entretanto, nada foi mencionado sobre como realizamos esta análise 
em algoritmos recursivos, direta ou indiretamente. 
 Há uma diferença fundamental entre analisarmos algoritmos iterativos e 
algoritmos recursivos. No primeiro caso, a metodologia proposta é baseada em 
uma contagem (quantificação) do número de operações realizadas por cada linha 
do algoritmo. Já no caso recursivo, isto é muito difícil de ser feito desta forma 
direta, uma vez que não conhecemos com precisão o número de vezes que 
executamos as chamadas recursivas e, consequentemente, as execuções de cada 
linha. 
 É justamente neste horizonte e para a solução (ou para facilitação da 
solução) deste problema que lançamos mão de uma outra ferramenta conhecida 
como relação de recorrência. 
 
3.2 Definição 
 
 A definição e a utilização de relações de recorrência extrapola o trato de 
algoritmos. Na verdade ela é uma ferramenta matemática para explicar funções 
em série. 
 Vamos considerar uma exemplo! Possivelmente todos já ouviram falar 
de uma série matemática conhecida como Série de Fibionacci ou Números de 
Fibionacci. Ela é assim definida: 
 38
• o primeiro número da série é 1; 
• o segundo número é 1; 
• a partir do terceiro, cada número é resultado da soma dos 
dois anteriores. 
Segundo esta definição, a sequência é assim disposta: 
 1 1 2 3 5 8 13 21 34 55 89 ...... 
 Sendo o primeiro e o segundo números 1, o terceiro é a soma de ambos, 
ou seja, 2. Uma vez conhecido este terceiro valor, a sua soma com o segundo 
resulta no quarto deles. Seguindo este procedimento, sucessivamente, serão 
obtidos os demais valores. 
 Esta série pode ser expressa, de forma mais precisa e matemática, com a 
seguinte expressão: 



−+−=
=
=
)2()1()(
1)2(
1)1(
nFnFnF
F
F
 
 Perceba que esta definição é idêntica aquela dada acima e aplica-se da 
mesma forma na busca dos valores: 
 F(1) = 1 
 F(2) = 1 
 F(3) = F(2) + F(1) = 1 + 1 = 2 
 F(4) = F(3) + F(2) = 2 + 1 = 3 
 F(5) = F(4) + F(3) = 3 + 2 = 5 
 : : 
 Bem, a Série de Fibionacci é uma relação de recorrência. Sabendo disto, 
vejamos a sua definição formal: 
Relação de Recorrência é uma equação ou inequação que 
descreve uma função ou série numérica utilizando-se dela 
própria na definição. 
 
 Um outro exemplo bastante comum é o cálculo do fatorial de um 
número inteiro. Ele é definido matematicamente como: 
 
 


−⋅=
=
)!1(!
1!1
nnn
 ou 


−⋅=
=
)1()(
1)1(
nFnnF
F
 
 Não é muito complicado perceber uma conexão entre esta forma de 
expressar uma relação de recorrência e a sua solução via algoritmos recursivos. 
 39
Basta comparar a definição do fatorial acima com o algoritmo da figura 1.2 para 
ver que este é a implementação daquela. 
 Sempre, nestes casos, os elementos conhecidos da relação (caso base) 
são utilizados para terminar as chamadas recursivas. Por exemplo, F(1)=1 no caso 
do fatorial. Já a definição recorrente ( F(n) = n . F(n-1) ) é justamente o elemento 
principal da chamada recursiva. 
 Se este raciocínio é válido neste sentido, da relação de recorrência ao 
algoritmo, o inverso também é. Ou seja, dado um algoritmo, é possível encontrar 
a relação de recorrência capaz de descrevê-lo. 
 
procedimento busca_binária( v: vetor[1..N] de inteiros; 
 x,min,max: inteiro ): inteiro 
variáveis 
 meio: inteiro; 
início 
 se max < min então 
 retorna –1; /* Não encontrou o elemento */ 
 meio := ( min + max ) / 2; 
 se v[meio] = x então 
 retorna meio; /* Encontrou o elemento na posição meio */ 
 se x < v[meio] então 
 retorna busca_binária( v, x, min, meio-1 ); 
 senão 
 retorna busca_binária( v, x, meio+1, max ); 
 fim 
fim 
Algoritmo 3.1 - Busca binária em um vetor ordenado. 
 
 Considere, por exemplo, o caso do algoritmo 3.1. Neste algoritmo é 
buscado um valor em um vetor de números inteiros ordenados crescentemente 
através do método de busca binária, ou seja, encontra-se o meio do vetor; se este 
meio é o elemento procurado, a busca termina; caso contrário, se o elemento 
buscado é menor do que aquele presente no meio do vetor, ele somente poderá 
estar naparte inferior do mesmo; senão, na parte superior. A busca irá terminar 
quando não tivermos mais intervalos de valores a pesquisar (max < min). 
 Para simplificar, vamos contar somente o número de passagens em cada 
uma das linhas válidas. Em cada chamada ao procedimento, as linhas serão 
executadas apenas uma vez, com exceção daquelas dentro dos testes, que podem 
não ser executadas. Supondo que não seja encontrado o elemento, será realizado 
o primeiro teste, o cálculo da variável meio, o segundo e o terceiro testes. Desta 
forma, serão quatro linhas executadas ao todo. 
 40
Na última chamada recursiva, quando o valor é determinado como não 
presente no vetor pois o intervalo de trabalho não tem valores válidos, somente 
um teste será realizado. Assim, podemos descrever este algoritmo na seguinte 
forma recorrente: 

 +=
=
4)2()(
1)1(
nTnT
T
 
Ou seja, o trabalho para solucionar o problema com um elemento na entrada 
(análogo ao caso onde não há nenhum mais a pesquisar), será de 1 operação  
teste de verificação do final. Se o problema tiver uma entrada maior, serão 
necessárias 4 operações (testes e cálculo do meio) e uma chamada recursiva para 
o mesmo problema, só que com uma entrada equivalente a metade da original. 
 Assim, é sempre possível extrairmos uma relação de recorrência de um 
algoritmo recursivo. O ponto de término da recursão será o caso base da 
recorrência. O número de chamadas recursivas aparece na definição recorrente e 
o trabalho adicional, medido por operações se necessário, no acréscimo à esta 
definição. 
 Veja mais um exemplo: 

 +=
=
nnTnT
T
)2(2)(
2)1(
 
Se esta relação de recorrência representa um algoritmo, ele necessita de duas 
operações para concluir o caso óbvio (não é possível dizer que tipo de operação). 
Não sendo este caso, ele divide o problema pela metades (T(n/2)) e executa 
recursivamente o algoritmo para estas duas metades (2T(n/2)). Ele ainda faz um 
trabalho adicional de n operações, que pode ocorrer antes, entre ou depois das 
duas chamadas recursiva (para a quantificação é indiferente o momento no qual 
isso acontece). 
 
3.3 Métodos de Solução 
 
3.3.1 Introdução 
 Uma vez compreendido o conceito e a função de uma relação de 
recorrência, verificamos que, no nosso caso, ela representa o trabalho ou o 
comportamento de um algoritmo recursivo. Resta-nos então buscar a solução 
desta relação. Por solução se entende o total geral de operações realizadas por ela, 
em todas as chamadas e representará o trabalho total realizado pelo algoritmo. 
 41
 Existem na bibliografia da área ([AU92], [Baa88], [CLR91], [Knu73], 
[Man89], entre outros) três formas de se buscar esta solução: por substituição ou 
prova inteligente; por história completa; e, pelo método mestre. 
 A primeira das alternativas, por prova inteligente, é a mais abrangente 
das três propostas, mas pressupõem o uso de uma ferramenta matemática 
conhecida como indução. Como este assunto está fora do escopo deste texto, 
serão apresentados e analisados os dois outros métodos. Na bibliografia citada 
acima você encontrará este método indutivo com detalhes; em especial em 
[AU92] e [Man89]. 
 
3.3.2 Método de história completa 
 Como foi visto, uma relação de recorrência, assim como um algoritmo 
recursivo, apresenta uma dificuldade adicional na busca da solução, pois não 
conhecemos o seu ponto de parada, ou seja, quando acontece a última chamada 
recursiva. 
 Veja, se soubermos o número de vezes que uma recorrência é executada, 
teremos apenas que somá-la para encontrar o resultado final. O problema reside 
exatamente neste fato, não sabemos com clareza como isso acontece. 
 A solução de uma recorrência por história completa trabalha justamente 
neste horizonte. O objetivo é “abrir” a recorrência tentando deduzir coisas sobre 
ela de forma a chegarmos ao total. Ou seja, tenta-se mostrar a sua história. 
Vamos utilizar como primeiro exemplo a seguinte relação: 

 +=
=
nnTnT
T
)2(2)(
1)1(
 (3.1) 
 Supondo uma entrada ou um dado de tamanho n, no nível mais alto a 
recursão trabalhará o equivalente a este n acrescida de duas chamadas recursivas 
a ela mesma com uma entrada de metade do original. Perceba que cada uma 
destas chamadas recursivas, no primeiro nível, terá a forma: 
2)4(2)2( nnTnT += 
Seguindo o mesmo raciocínio, 
8)16(2)8(
4)8(2)4(
nnTnT
nnTnT
+=
+=
 
 Então, da relação 3.1 pode ser feita a seguinte leitura (perfeitamente 
correta): ao receber uma dada entrada (independente do tamanho), ela trabalha 
 42
duas vezes, de forma análoga, com uma entrada com tamanho de metade da 
original; após, (poderia ter sido antes), realiza um trabalho adicional equivalente 
(da mesma ordem) ao que entrou. 
Segundo esta idéia, esta recorrência poderia ser escrita assim: 
nnTnT += )2(2)( 
ou, sabendo que 
2)4(2)2( nnTnT += , na forma: 
( ) nnnTnT ++= 2)4(22)( 
E assim, este desmembramento pode continuar indefinidamente: 
( )( )
( )( )( ) nnnnnTnT
nnnnTnT
++++⋅⋅⋅=
+++⋅⋅=
248)16(2222)(
24)8(222)(
 
 : : : : 
 Obviamente esta forma de desenho da recorrência ou da sua história é 
muito confusa e na acrescenta à busca da solução, pelo menos a primeira vista. 
Desta forma, este método de solução faz a descrição da relação na forma de uma 
árvore. Veja: 
 
 nnTnT += )2(2)( Î n 
)2( nT )2( nT 
Nesta árvore nós temos o trabalho adicional como elemento 
centralizador. A partir deste elemento ocorrem tantas ramificações quantas as 
chamadas recursivas da recorrência. Neste caso serão duas delas (2T(n/2)), sendo 
cada uma delas de T(n/2). 
 A mesma forma de procedimento deve ser utilizada para cada uma das 
ramificações. Como 
 
2)4(2)2( nnTnT += Î 2n 
 
)4( nT )4( nT 
ele pode ser levado para a primeira árvore e ela aumentará um nível. Veja o 
resultado: 
 43
 
 n n 
 Î 
)2( nT )2( nT 2n 2n 
 
 )4( nT )4( nT )4( nT )4( nT 
Agora, se ampliarmos sempre este raciocínio encontraremos, para este 
caso, a árvore apresentada na figura 3.1. Esta forma de desenho da recorrência 
ainda não apresenta a solução da mesma, mas fornece importantes detalhes sobre 
o seu comportamento. 
 
Figura 3.1 – Árvore da história completa da recorrência 3.1. 
 
 Em primeiro lugar, perceba que necessitamos somar todo o conteúdo 
desta árvore para sabermos a solução da recorrência. Neste ponto esbarramos no 
mesmo problema inicial com a relação original: o final da execução. 
 Aqui, entretanto, está mais fácil se chegar a uma dedução sobre o tema. 
Antes disso, vamos somar cada um dos níveis desta árvore. O primeiro nível, por 
ter comente n, tem este como soma. O segundo, por sua vez, também soma n. O 
 44
mesmo acontece com o terceiro nível. A árvore completa, com seus níveis 
somados está na figura 3.2. Este desenho permite deduzir que todos os níveis 
desta árvore somam um trabalho equivalente a n. 
 
Figura 3.2: Árvore de história completa com somatório dos níveis 
 
 Sabemos agora que a mesma recorrência 3.1 pode ser escrita como: 
∑
=
=+++++=
X
i
nnnnnnnT
1
)( " 
 Fica somente uma questão ainda a ser respondida: quantas vezes isto 
acontece? Ou então, quantos níveis tem está árvore? Ou ainda, quanto é o valor 
do X no somatório acima? 
 Para isso basta analisar um pouco melhor a recorrência e lembrar (ou 
relembrar) algumas propriedades básicas da matemática. Note que, em cada um 
dos níveis da relação estamos dividindo o elemento do nível sempre por dois. 
Segundo a definição desta relação, a divisão deve parar quando o tamanho da 
entrada chegar até 1  que é o caso óbvio. Note que, se o final for um nível 
acima, com T(2)