Estrutura de Dados

Análise de
Complexidade de
Algoritmos

Marco Antonio Moreira de Carvalho
Algoritmos e Estruturas de Dados

Bibliografia Básica

Cormen, Leiserson, Rivest. Introduction to
Algorithms. 2nd edition. MIT Press, 2001.
Capítulo 3.
Aho, Alfred V., Hopcroft, John F., Ullman,
Jeffrey D., Data Structure and Algorithms,
Massachusetts: Addison-Wesley, 1987.
Capítulos 1, 9.

2

Análise de Algoritmos
Analisar um algoritmo significa prever os recursos que ele necessitará para sua execução
Os mais importantes são tempo e espaço
O tempo de execução é o número de operações primitivas executadas pelo algoritmo;
O espaço é de fato o espaço necessário para armazenar dados durante a execução do algoritmo.

Com base na análise, podemos identificar a eficiência de cada algoritmo para um determinado problema Qual é o mais apropriado em um conjunto de candidatos?

A análise é realizada levando em consideração um determinado modelo computacional.
3

Modelo Computacional
O modelo computacional utilizado é genérico
Um único processador;
Memória RAM
Operações sequenciais, não há paralelismo;
Instruções
Aritméticas (soma, subtração, multiplicação, divisão, resto, piso e teto);
Movimentação de dados (carregar, armazenar e copiar)
Controle (desvio condicional e incondicional, chamada e retorno de rotinas).
Cada instrução tem tempo de execução constante, embora possam ser diferentes.
4

Modelo Computacional
Com base nas operações definidas, outras operações mais complexas podem ser derivadas
Algumas áreas “cinzas” como exponenciação serão tratadas como tempo constante também.

5

Perspectivas
Além do ambiente computacional, o comportamento de um algoritmo pode variar de acordo com o comportamento da entrada, o que gera diferentes perspectivas Melhor caso: A entrada está organizada de maneira que o algoritmo levará o tempo mínimo para resolver o problema;
Pior caso: A entrada está organizada de maneira que o algoritmo levará o