Complexidade Algoritmica

Departamento de Ciências e Tecnologias da Informação

Filipe Santos

ALGORITMOS E COMPLEXIDADE
COMPLEXIDADE DE ALGORITMOS E
PROBLEMAS

Algoritmos e Complexidade

1

Departamento de Ciências e Tecnologias da Informação

Filipe Santos

Plano
Eficiência de algoritmos. Eficiência no melhor caso, pior caso e em média. Ordem de complexidade. Melhoramentos de pequena e grande magnitude na eficiência de algoritmos.
Exemplos de diferentes algoritmos com diferentes eficiências para o mesmo problema. Complexidade de um problema.
Problemas fechados e abertos.
Algoritmos: Insert sort; Pesquisa Linear; Pesquisa Binária;
Bubblesort; Barricada dos tigres adormecidos.

Algoritmos e Complexidade

2

Filipe Santos

Departamento de Ciências e Tecnologias da Informação

Eficiência de algoritmos
Que recursos computacionais são necessários para executar um algoritmo? tempo de execução espaço de memória

Complexidade Temporal
Complexidade Espacial

espaço e tempo dependem da dimensão dos dados. Podemos portanto representar a eficiência por funções! e s p a ç o

S(n)

n - dimensão dos dados

S(n)
T(n)

memória utilizada pelo algoritmo em função do tamanho n do input tempo de execução do algoritmo em função do tamanho n do input

Algoritmos e Complexidade

3

Departamento de Ciências e Tecnologias da Informação

Filipe Santos

Eficiência de algoritmos
Na prática é muito difícil calcular com rigor o tempo de execução de um algoritmo! ☺ Identificar no algoritmo as operações elementares e determinar o número de vezes que são executadas. O tempo real de execução de cada operação elementar será uma constante multiplicativa!
Independentemente do computador!
Dados vários algoritmos para solucionar um mesmo problema, devemos escolher aquele que nos permite resolver o problema mais rapidamente e utilizando o menor espaço possível para representar os dados do problema!
Mas …

Algoritmos e Complexidade

4