Técnicas de Análise de Algoritmos

Pontifícia Universidade Católica de Minas Gerais
Instituto de Ciências Exatas e Informática
Departamento de Ciência da Computação
Curso de Ciência da Computação

Projeto e Análise de Algoritmos
Parte 2

Raquel Mini [e-mail] Técnicas de Análise de Algoritmos

Ziviani – págs. 19 até 23 e 35 até 42
Cormen – págs. 21 até 31 e 50 até 72

Técnicas de análise de algoritmos
•
•
•

Determinar o tempo de execução de um programa pode ser um problema matemático complexo
Determinar a ordem do tempo de execução, sem preocupação com o valor das constantes envolvidas, pode ser uma tarefa mais simples
A análise utiliza técnicas de matemática discreta, envolvendo contagem ou enumeração dos elementos de um conjunto:
− manipulação de somas
− produtos
− permutações
− fatoriais
− coeficientes binomiais
− solução de equações de recorrência
3

Análise do tempo de execução
•
•
•
•

Comando de atribuição, de leitura ou de escrita: O(1)
Sequência de comandos: determinado pelo maior tempo de execução de qualquer comando da sequência
Comando de decisão: tempo dos comandos dentro do comando condicional, mais tempo para avaliar a condição, que é O(1)
Anel: soma do tempo de execução do corpo do anel mais o tempo de avaliar a condição para terminação (geralmente
O(1)), multiplicado pelo número de iterações

4

Análise do tempo de execução
•

Procedimentos não recursivos:
− Cada um deve ser computado separadamente um a um, iniciando com os que não chamam outros procedimentos
− Avalia-se então os que chamam os já avaliados (utilizando os tempos desses) − O processo é repetido até chegar no programa principal

•

Procedimentos recursivos:
− É associada uma função de complexidade T(n) desconhecida, onde n mede o tamanho dos argumentos
− Obtemos uma equação de recorrência para T(n)
− Resolvemos a equação de recorrência

5

Análise de algoritmos não recursivos
•
•

Considerando que a operação relevante seja