Complexidade de Algoritmos
[email protected]
Complexidade de Algoritmos
• Algoritmos
– Seqüência de passos conhecidos
– Finitos
• Entrada Processamento Saída
– Mesmo que “se confunda” no tempo
• Tem que ter uma saída
– Problema da Parada
Algoritmos
• Algoritmos (definições)
– Procedimento computacional que recebe uma
entrada e produz uma saída
– Seqüência de passos que transformam entrada
em saída
– Máquina de Turing que transforma uma entrada
M numa saída S
Complexidade
• Algoritmos podem ser mais ou menos
eficientes
– Ortogonal à computabilidade
• Podemos otimizar nossos códigos!
– Busca Seqüencial X Busca Binária
– Bubble Sort X Quick Sort
Tipos de Complexidade
• Algoritmos podem ser mais ou menos
eficientes com respeito a
– Tempo: quanto tempo será necessário para que
o algoritmo termine e dê a resposta?
– Espaço: quanto de espaço será necessário para
que o algoritmo possa trabalhar e dar a
resposta?
Exemplo
• Em bancos de dados:
– Uma busca usando índice B+Tree
– Mais rápida (mais eficiência no tempo)
– Mais espaço (menos eficiência no espaço)
• Outros exemplos
– Árvores X Ordenação
– Ordenação em disco
Exemplo práticos
• Qual a complexidade temporal da busca
seqüencial?
• E da busca binária?
• Qual a complexidade temporal do Bubble
Sort?
• E do Merge Sort?
Notação O(n)
• Sejam duas funções g(n) e f(n)
• Diz-se que g(n) = O(f(n)) sse há algum C tal
que g(n) = cf(n)
• Exemplo: 3n = O(n)
– 4n2 -2n + 7 = O(n2)
– 176.439log10(n)/3 = O(log(n))
Notação O(n)
• Porque O(n) é importante?
– n2 e n2 + 18876547n geram valores diferentes
– Mas padrões de crescimento iguais!
– Para N muito grande (digamos
1.000.000.000.000)
• n2 = 1x1024 e n2 + 18876547n =
1x1024+18876547x1012
• Quanto 18876547x1012 é significativo no final?
Padrões importantes
• Certos tipos de complexidade são
importantes
• Caracterizam classes de problemas
particulares
• Facílimos, Muito fáceis, Fáceis, Difíceis,
Muito difíceis, etc. e os intratáveis!
Padrões importantes
•
•
•
•
•
•
•
O(1) – tempo constante: facílimo
O(log n) – logarítmica: muito fácil
O(n) – linear: fácil
O(n log n) – polinomial-logaritmico:fácil
O(nm) – polinomial: difícil
O(n!) – fatorial (exponencial): intratáveis!
O(mn) – exponencial: intratáveis!
Gráfico Comparativo
Logaritmicas
12
10
Tempo
8
6
4
2
0
0
2
4
6
8
Tmanho da entrada
log(n)
n*log(n)
10
12
Gráfico Comparativo
Polinomiais
12000
10000
Tempo
8000
6000
4000
2000
0
0
20
40
60
80
Tamanho da Entrada
n*log(n)
n^2
100
120
Gráfico Comparativo
Polinomiais X Expoenciais
4500
4000
3500
Tempo
3000
2500
2000
1500
1000
500
0
0
5
10
Tamanho da Entrada
n^2
2^n
15
Gráfico Comparativo
Exponenciais
800
700
Tempo
600
500
400
300
200
100
0
0
2
4
6
Tamanho da Entrada
n!
2^n
8
Importância da complexidade
• O que são elementos de hardware e de
software
• Um exemplo: ordenação
– Computador A – Um bilhão de comparações
por segundo (1012)
• Ordenação por inserção
– Computador B – Dez milhões de comparações
por segundo (1010)
• Ordenação rápida (Quick Sort)
Importância da complexidade
• Complexidade dos algoritmos
– Quick Sort: O(n log n)
– Insertion Sort: O(n2)
• Ordenar 1 milhão de números (n=106)
– Computador A: (106)2/1012 = 1seg
– Computador B: 106xlog106/1010 = 6x10-9seg
• E se fosse para ordenar um trilhão de
números (n=1015)?
Importância da complexidade
• Outro exemplo – determinante de matrizes
• Calcular o determinante de uma matriz
quadrada de ordem n (MNxN)
• Método de Gauss: 4n3+9n2-7n)/6 = O(n3)
• Método de Crammer: (n+1)!(e-1) = O(n!)
Importância da complexidade
n
Crammer
2
20
3
102
4
456
5
2,35ms
10
1,19min
20 15225 séculos
40 5,1033 séculos
Gauss
50
159
353
666
4,95ms
38,63ms
0,315s
Classes de problemas
• Problemas polinomiais
• Problemas para os quais se conhece
algoritmo polinomial para resolver
• O(nk) ou inferior
• Classe P
Classes de problemas
• Problemas polinomiais não determinísticos
• Problemas para os quais não se conhece
solução determinística senão exponencial
• O(kn) ou que o valha (O(n!), etc)
• Classe NP
• P  NP (todo problema P admite solução
exponencial!)
Problemas da classe NP
• O problema do caixeiro viajante
(simplificado)
• Percorrer todas as cidades com mais de 200
mil habitantes do interior da Bahia andando
o mínimo possível, começando em Ilhéus,
sem passar duas vezes na mesma cidade!
• E se não se fixar a cidade de origem?
Como fica
• Cidades:
–
–
–
–
Feira de Santana
Vitória da Conquista
Itabuna
Ilhéus
• Possíveis trajetos?
• Distâncias?
Distâncias
Km
FSA
VCO
ITA
IOS
FSA
400
360
390
VCO
400
240
270
ITA
360
240
30
IOS
390
270
30
-
Como escolher?
• Gerar todos os trajetos possíveis e comparar
seus custos – Método Algoritmico
• Dados
– C: Conjunto de cidades consideradas
– R e Rmenor: Listas encadedadas de cidades
(rotas)
– R.Tamanho(T): Retorna o tamanho da rota R
usando T
– T: Tabela de distâncias entre as cidades
Como escolher?
• Algoritmo
Inicio
C  Todas as Cidades
R.Criar( ) /*Cria a rota R vazia */
MenorTamanho = 
GerarRotas (C, R, Rmenor, MenorTamanho)
Retorna Rmenor
Fim
Como escolher?
Gerar_Rotas (C, R, Rmenor, MenorTamanho)
Se C   então
Para cada cidade c  C faça
R.Incluir(c)
C’ = C – {c}
Gerar_Rotas (C’, R, Rmenor, MenorTamanho)
R.Excluir(c)
Senão
Se R.Tamanho(T) < MenorTamanho então
Rmenor = R
MenorTamanho = R.Tamanho(T)
Fim_Gerar_Rotas
Como escolher?
• Gera todos os trajetos possíveis e comparar
seus custos
–
–
–
–
–
–
IOS/FSA/VCO/ITB: 390+400+240 = 1030
IOS/FSA/ITB/VCO: 390+360+240 = 990
IOS/ITB/FSA/VCO: 30+360+400 = 790
IOS/VCO/ITB/FSA: 270+240+360 = 870
IOS/VCO/FSA/ITB: 270+400+360 = 1030
IOS/ITB/VCO/FSA: 30+240+400 = 670
Performance!
• Quantos trajetos? Quantas cidades?
– 3 cidades, 6 trajetos, (3!)
• Cidades maiores do que 1000
habitantes
– 360 cidades, 3,98x10765 (360!) trajetos
• Um computador (jamais
construído) que possa gerar
10500 trajetos por segundo:
1,26x10256 séculos!
Outros problemas da classe NP
• Gerenciamento de filas para uso de
CPU (escalonamento)
• Gerenciamento de memória
(fragmentação)
• Otimização de consultas em SGBDs
• Localização de recursos em Sistemas
Distribuídos.
Como tratar problemas NP
•
•
•
•
Heurísticas
Técnicas de programação (meta-heurísticas)
Abrir mão da “melhor” solução
Garantir uma “boa” solução (possivelmente
a melhor)
• Tempo de execução polinomial
Método Guloso
• Começa em algum ponto
• Escolhe, na vizinhança, qual o ponto mais
“barato” a percorrer
• Repete a escolha até que não haja mais
nenhum
• Pode (ou não) resultar no melhor caso, em
problemas da classe P
– Problema do troco
Método Guloso
• No exemplo: saindo de Ilhéus
–
–
–
–
–
Escolhe Itabuna (30Km)
Escolhe Vitória da Conquista (240Km)
Escolhe Feira de Santana (400)
Total: 670
Melhor escolha? Sempre?
Método Guloso
Método Guloso
Método Guloso
Método Guloso
Método Guloso
Método Guloso
Dividir para Conquistar
• Parte do princípio de que unir duas melhores
soluções parciais resulta na melhor solução global
• N cidades
• K grupos de N/K cidades
• Resolve os K grupos
• “Une” a solução
• Pode (ou não) resultar no melhor caso, em
problemas da classe P
– Torre de Hanoi, Ordenação
Dividir para conquistar
• No exemplo: dois grupos ({Ilhéus, Itabuna}
e {Vit. Conquista, Feira de Santana})
• Ilhéus – Itabuna (30Km)
• Vit. Conquista – Feira de Santana (400Km)
• “Unir”: Itabuna-Feira (390) ou ItabunaConquista (240)
• Total: 670
• Melhor solução? Sempre?
Programação Dinâmica
• Quando uma seqüência de decisões locais
não gera uma solução ótima
• Gerar todas as seqüências: exponencial
• Princípio: Se i, i1, i2, i3, ..., ik, j é a melhor
solução entre i e j então i1, i2, ... ik é a
melhor solução entre i1 e ik.
– Requer um conhecimento prévio (heurística)
Programação Dinâmica
• No exemplo: sabe-se que a melhor divisão em
dois grupos é (Ilhéus, Itabuna e Vit. Conquista,
Feira de Santana)
• Ilhéus – Itabuna (30Km)
• Vit. Conquista – Feira de Santana (400Km)
• “Unir”: Itabuna-Feira (390) ou Itabuna-Conquista
(240)
• Total: 670
• Melhor solução? Proporcional ao conhecimento
prévio (Background Knowledge)!
BackTracking
• Soluções restritas
• Gerar árvore de soluções até que
– Uma resposta que satisfaça seja encontrada
– Não se possa mais alcançar resposta satisfatória
• No segundo caso há um retorno e toma-se
outro caminho
• O problema das 8 rainhas
BackTracking
• Soluções com custo inferior a 800
–
–
–
–
–
–
IOS/FSA/VCO/ITB: 390+400+240 = 1030
IOS/FSA/ITB/VCO: 390+360+240 = 990
IOS/ITB/FSA/VCO: 30+360+400 = 790
Solução ok!
Total: 790
Encontra a primeira solução “satisfatória”, se
houver.
NP-Completos
• Intratabilidade
• Problemas intratáveis
– Indecidibilidade (Problema da Parada, Fermat,
etc)
– Problemas decidíveis mas não polinomiais
– Problemas decidíveis e “aparentemente” não
polinomiais
NP-Completos
• Objetivo: encontrar problemas
“equivalentes” em complexidade
• Dicas sobre como resolvê-los (ou não
resolvê-los)
• Redução: mapeamento entre dois problemas
• 1 “engloba” 2  1 é pelo menos tão
difícil quanto 2
Exemplo de redução
1: Caixeiro viajante
2: Desfragmentar memória
Escolher Arquivo = Escolher Trecho
Possibilidades de organização dos arquivos
= Possíveis rotas
• Melhor conjunto de rotas X Seqüência
(desfragmentada) de arquivos
• 2 engloba 1
• Se houver solução polinomial para o
caixeiro viajante...
•
•
•
•
Definições
• P: classe de problemas resolvíveis em
tempo polinomial num computador
determinístico
• NP: classe de problemas resolvíveis em
tempo polinomial em um computador não
determinístico (NP: Non-deterministic
Polinomial)
Mais resultados
• NP é “polinomialmente verificável”, i.e. há
algoritmos polinomiais para verificar uma
solução de problemas em NP
• Sabe-se que P  NP (mais precisamente P 
NP)
– Mas não se sabe se P=NP ou se PNP
– Acredita-se que PNP
P e NP
NP
P
Problemas Intratáveis
• A suposição de que PNP nos leva a
questionar:
Quem são os problemas do
conjunto NP – P?
• Problemas intratáveis!
Teorema de Cook
• Se 1  2 (1 é redutível a 2 em tempo
polinomial) e 2  P então 1  P
• Satisfatibility: Problema que Cook mostrou
que todos os problemas em NP podem ser
reduzidos a ele em tempo polinomial
• Há outros problemas com essa mesma
característica: os NP-Completos
Propriedades dos NP-Completos
• Se 1  NPC e 2  NPC então 1 e 2 são
mutuamente redutíveis em tempo polinomial
• Se algum problema em NP for mostrado
intratável, todos os problemas NPC também o
serão, e o mesmo se dá no caso da tratabilidade
• Ou seja: seja  um problema NPC tem-se que,
  P  P  NP
• Mas não se provou nada até hoje
Mundo NP (suposto)
NPC
NP
P
Para que tudo isso?
• Respondamos à seguinte questão:
• Os problemas NP-Completos são intratáveis?
• Há centenas de problemas NP-Completos
conhecidos
• Se  é NP-Completo
– Ou usa-se uma heurística
– Ou espera-se uma revolução em Ciência da
Computação
Para que servem os NPCompletos?
• Como provar que um problema é NPCompleto?
–
–
–
–
Mostra que   NP
Seleciona algum problema NPC ’
Constrói  uma transformação de  em ’
Mostra que  é polinomial
• Problemas intratáveis podem ser úteis?
Complexidade de Algoritmos.
FIM!
Escher
“De vez em quando tropeçamos na verdade, mas
normalmente levantamos e seguimos em frente!”
Lei de Murphy aplicada ao ser humano