Complexidade de Algoritmos

Prévia do material em texto

Complexidade
Raphael Winckler de Bettio
 
Complexidade
 Um algoritmo é uma sequência de instruções 
não ambíguas para resolver um problema 
obtendo uma saída desejada para qualquer 
entrada legítima em um intervalo de tempo 
finito.
“Alessandro L. Koerich”
 
Complexidade
 Então, um algoritmo deve satisfazer:
− Entrada: uma ou mais quantidades são fornecidades 
externamente;
− Saída: Ao menos uma quantidade é produzida;
− Certeza: Cada instrução é clara e não ambígua;
− Finito: Se seguirmos as instruções de um algoritmo, 
então, para todos os casos, o algoritmo termina após 
um número finito de passos;
− Efetividade: Cada instrução deve ser simples o 
suficiente de modo a permitir que uma pessoa 
utilizando somente lápis e papel realize-o.
 
Complexidade
 Passo 1: Análise do Problema;
 Passo 2: Projeto do Programa;
− Análise (Abordagem) Teórica;
 Passo 3: Implementação;
 Passo 4: Verificação
− Análise (Abordagem) Experimental;
 
Complexidade
 Ordenação
− Bubble Sort (Bolha), Quick Sort, Merge Sort ...
 Busca
− Binária, Sequencial, Interpolação ...
 Caminho mais curto
− Dijkstra, Bellman-Ford, A*, Floyd-Warshall ...
 Árvore geradora Mínima
− Algoritmo Prim, Kruskal, Boruvka ...
 
Complexidade
 Algoritmos criados para resolver o mesmo 
problema diferem muito em sua eficiência
− BubbleSort x QuickSort
 Suponha que os computadores possuissem 
memória infinita e processamento também;
− O algoritmo responde corretamente ao problema?
 No mundo real deve-se considerar tempo e 
espaço.
 
Complexidade
 O Desempenho total de um sistema 
computacional depende da combinação de 
Hardware e Software
Computadores com maior poder de processamento
Algoritmos que resolvam o problema de maneira mais eficiente
 
Complexidade
 Se for feita uma análise ao longo dos anos:
− Antigamente Hardware representava o maior 
investimento;
− Software era considerado um “adendo”;
− Atualmente o profissional de TI é o maior 
investimento;
− Em termos de Hardware
 De modo geral o investimento é baixo;
 Memória também tem um investimento baixo;
 Processamento ainda é muito limitado.
− Eficiência temporal
 
Complexidade
 Criterios
− Correção;
− Eficiencia Temporal;
− Eficiencia Espacial;
− Otimalidade;
 Dois metodos
− Experimental
− Teorica
 
Complexidade
 Eficiência de Algoritmos:
− Temporal: indica a rapidez de um algoritmo;
− Espacial: indica a quantidade de espaço ou 
memória que um algoritmo precisa.
 
Complexidade
 Experimental
− Verificação
− Em geral depois de desenvolvido
No momento do Teste;
Após termos problemas de performance;
− Ferramentas (profiler)
 
Complexidade
 Temporal:
Método
Perc Processamento
No. Exec
 
Complexidade
 Espacial:
Objeto
Bytes Alocados
Objetos Alocados
 
Complexidade
 Não podemos testar todas as entradas 
possíveis;
 Não é possível fazer uma análise completa, 
podem existir determinadas entradas onde a 
eficiência não é suficiente;
 Os resultados dependem muito da 
implementação (Linguagem, Hardware e 
outras condições externas)
 
Complexidade
 Teorica
− Projeto do Programa
− Tenta prever os aspectos gerais
− Correção: Fornece uma solução valida para o 
problema?
− Eficiência: Rapidez (Temporal) e Quantidade de 
Memória (Espacial)
 
Complexidade
 Quase todos os algoritmos levam mais tempo 
para ser executados sobre entradas maiores;
 Assim, deve-se investigar a eficiência de 
algoritmos levando em consideração o 
parametro n que representa o tamanho da 
entrada.
 
Complexidade
 Existem padrões para:
− Medida do tamanho de entrada;
− Definição do Tipo de Entrada;
− Operação básica;
 
Complexidade
 Métrica que não dependa de fatores externos
− Identificar a operação mais importante do algoritmo 
(operação básica).
− Contar o número de vezes que a operação básica é 
realizada.
 
Complexidade
 Media do Tamanho da Entrada
 
Complexidade
Operação básica
Entrada (n)
Operação 
Básica (número 
de repetições)
 
Complexidade
 Porque não utilizar unidade “física” de tempo?
− Dependência do hardware, qualidade da 
implementação, compilador, etc.
 
Complexidade
 Eficiência Temporal: Analise do número de 
repetições de operações básicas com uma 
função de entrada. (Não usar unidade física de 
tempo).
 Operação Básica: Operação mais importante.
T(n) ≈ C(n)
Eficiência ou Tempo de Execução
Tempo Operação Básica
Número de vezes
 
Complexidade
T(n) ≈ C(n)
Eficiência ou Tempo de Execução
Tempo Operação Básica
Número de vezes
 Algoritmo que soma os números em um Array;
 Array de 10 itens;
 Operação Básica é a soma;
 Operação de soma leva 10s;
 Para 10 itens teremos 10 somas;
 T(10) ≈ 10s * 10 = 100s (10)
 Ignoramos constantes multiplicativas e nos concentramos na ordem de crescimento da 
contagem da operação básica
 
Complexidade
(n) C(n)
10 10
50 50
100 100
500 500
1000 1000
0 200 400 600 800 1000 1200
0
200
400
600
800
1000
1200
C(n)
 
Complexidade
 Tamanho da Entrada – 10
 Algoritmo – Busca Sequencial
 Operação Básica - Comparação
Entradas diferentes geram número
diferente de execuções
 
Complexidade
 Para alguns algoritmos, eficiência depende não 
somente do tipo de entrada, mas também das 
especificidades de uma entrada particular 
(Perspectivas)
− Pior caso: Máximo sobre entradas de 
tamanho n
− Melhor caso: Mínimo sobre entradas de 
tamanho n
− Caso médio: “média” sobre entradas de 
tamanho n
 
Complexidade
 Melhor caso: Consiste em assumir que vai 
acontecer o melhor. Pouco utilizado e de baixa 
aplicabilidade;
− Em uma lista telefonica queremos encontrar 
o nome do usuário de um número, 
assumindo-se o melhor caso o número 
telefônico será o primeiro da lista.
 
Complexidade
 Melhor caso (n) c(n)
10 1
20 1
30 1
100 1
0 20 40 60 80 100 120
0
0.2
0.4
0.6
0.8
1
1.2
c(n)
 
Complexidade
 Pior caso: Consiste em assumir que vai 
acontecer o pior. É a perspectiva mais utilizada 
− Ainda no exemplo da lista telefonica, 
assumindo-se o pior caso o número 
telefônico será o último da lista.
 
Complexidade
 Pior Caso (n) C(n)
10 10
50 50
100 100
500 500
1000 1000
0 200 400 600 800 1000 1200
0
200
400
600
800
1000
1200
C(n)
 
Complexidade
 Caso médio: É o caso mais difícil de ser 
determinado, pois, necessita de análise 
estatística.
− No mesmo exemplo da lista telefônica. Deve-
se levar em consideração a maneira como o 
algoritmo percorre a lista e determinar 
estatisticamente quantas operações em 
média serão executadas.
 
Complexidade
 Caso Médio (n) c(n) = (n)/2
10 5
20 10
30 15
100 50
0 20 40 60 80 100 120
0
10
20
30
40
50
60
c(n) = (n)/2
c(n) = n/2
 
Complexidade
(n) C(n)
10 10
50 50
100 100
500 500
1000 1000
10000 10000
20000 20000
(n) C(n)
10 1
50 1.6989700043
100 2
500 2.6989700043
1000 3
10000 4
20000 4.3010299957
0 10000 20000 30000
0
5000
10000
15000
20000
25000
C(n)
0 5000 10000 15000 20000 25000
0
0.5
1
1.5
2
2.5
3
3.5
4
4.5
5
C(n)
Algoritmo 
A
Algoritmo 
B
ComplexidadeComplexidade
X
Como comprar algoritmos em que a função 
que representa o crescimento é diferente?
 
Complexidade
 Notação Assintótica
− Análise da eficiência de algoritmos se concentra na 
ordem de crescimento da operação básicade um 
algoritmo, como o principal indicador de eficiência;
− Para comparar e classificar estas ordens de 
crescimento, são utilizadas notações assintóticas;
− Objetivo: Resumir o comportamento de um 
algoritmo em fórmulas simples e de fácil 
compreensão
 
Complexidade
0 100020003000 40005000600070008000
0
0.2
0.4
0.6
0.8
1
1.2
c(n)
0 10002000300040005000600070008000
0
100
200
300
400
500
600
700
800
c(n)
0 10002000 30004000 500060007000 8000
0
0.5
1
1.5
2
2.5
3
3.5
4
4.5
c(n)
Constante
LogarítmicaLinear
Um Algoritmo é assintoticamente mais eficiente será a melhor escolha para 
todas as entradas (exceto as muito pequenas)
 
Complexidade – Exercício 1
Algoritmo A Algoritmo B
Tempo Operação Básica
“Construa o gráfico que representa a eficiência dos dois algoritmos para o pior caso”
Função de EntradaFunção de Entrada
Tempo Operação Básica
 
Complexidade
Algoritmo A Algoritmo B
0 200 400 600 800 1000 1200
0
200
400
600
800
1000
1200
C(n)
0 100020003000 40005000600070008000
0
0.2
0.4
0.6
0.8
1
1.2
c(n)
 
Complexidade – Exercício 2
Algoritmo A Algoritmo B
Qual a fórmula que representa
a Complexidade no Pior caso?
0 200 400 600 800 1000 1200
0
200
400
600
800
1000
1200
C(n)
0 100020003000 40005000600070008000
0
0.2
0.4
0.6
0.8
1
1.2
c(n)
 
Complexidade
 Para cada Perspectivas 
− Pior caso, Melhor Caso e Caso Médio
 Notação O (Ô): Pior Caso;
 Notação Ω (Ômega): Melhor Caso;
 Notação Θ (Theta): Caso Médio
O(?)
Ω(?)
 
Complexidade
Algoritmo A Algoritmo B
O(n) O(1)
Qual a fórmula que representa
a Complexidade no Pior caso?
O Algoritmo B é mais eficiente que o Algoritmo A
(para entradas grandes)
0 200 400 600 800 1000 1200
0
200
400
600
800
1000
1200
C(n)
0 100020003000 40005000600070008000
0
0.2
0.4
0.6
0.8
1
1.2
c(n)
Linear
Constante
	Slide 1
	Slide 2
	Slide 3
	Slide 4
	Slide 5
	Slide 6
	Slide 7
	Slide 8
	Slide 9
	Slide 10
	Slide 11
	Slide 12
	Slide 13
	Slide 14
	Slide 15
	Slide 16
	Slide 17
	Slide 18
	Slide 19
	Slide 20
	Slide 21
	Slide 22
	Slide 23
	Slide 24
	Slide 25
	Slide 26
	Slide 27
	Slide 28
	Slide 29
	Slide 30
	Slide 31
	Slide 32
	Slide 33
	Slide 34
	Slide 35
	Slide 36
	Slide 37
	Slide 38
	Slide 39
	Slide 40