nenhum

Teoria dos Grafos e
Complexidade de Algoritmos

Aula passada
•

Busca em grafos

-

Largura
Profundidade

Aula de hoje
•
•

Análise de algoritmos
Análise de complexidade de algoritmos

•

Análise de tempo e espaço
Exemplos

Algoritmos de ordenação

Análise de algoritmos
•

Algoritmo é um procedimento computacional que toma os valores de entrada e os transforma nos valores de saída

•

Análise:

-

Recursos necessários para executar o procedimento (tempo e espaço)

-

Independente da máquina: baseada na taxa de crescimento dos recursos baseado na entrada

Análise de complexidade
•

Porque estudar complexidade:

-

Fundamental para projetar algoritmos eficientes
Representa a eficiência de um algoritmo
Comprar diferentes algoritmos que resolvam o mesmo problema

Análise de complexidade
•

Medidas:

-

Tempo de execução (minutos, segundos, etc).
Porém depende da máquina

-

Número de operações (operações aritméticas, movimento de dados). É expressada através de uma função de n

Análise de complexidade
•

O número de operações pode depender de uma particular entrada

•
•

Assim, consideramos o pior caso
Mas também podemos considerar o melhor caso e o caso médio

Análise de complexidade
•

Exemplo: Dado 2 algoritmos que resolvem o mesmo problema como função de n

-

Algoritmo 1: f1(n) = 2n2 + 5n operações

-

Dependendo do valor de n, o algoritmo 1 pode requerer mais ou menos operações que o algoritmo 2

Algoritmo 2: f2(n) = 500n + 4000 operações

Análise de complexidade
•

Quando n tem valor muito grande (n ➝ ∞), denominamos comportamento assintótico

•

O importante é observar que:

•

f1(n) cresce com n2 f2(n) cresce com n

Como um crescimento quadrático é considerado pior do que um crescimento linear, podemos preferir o algoritmo 2 ao algoritmo 1

Análise de complexidade
•
•

Notação: O()
Avaliação da taxa de crescimento

-

(c):