636257_Análise de Complexidade

Prévia do material em texto

Análise de Complexidade
Baseado em material do Prof. João Caran
Comportamento Assintótico
� Dizemos que uma função g(n) domina 
assintoticamente outra função f(n) se 
existem c e m tais que para n≥m, temos f(n) 
≤ c*g(n)
Domínio Assintótico
� Exemplos:
� f(n) = n e g(n) = n2
n<=n2 (c=1 e m=0)
� f(n) = n2 e g(n) = 
(n+1)2
n2<= (n+1)2 (c=1 e m=0)
(n+1)2 <= n2 (c=4 e m=1)
Notação O
� Para expressar que g(n) domina 
assintoticamente f(n) escrevemos f(n) = O(g(n))
� Notação O (Knuth, 1968)
� Exemplo: 
� f(n) = (n+1)2. 
− Para m=1 e c=4, f(n) = O(n2)
� A notação O define um limite superior 
para a função, por um fator constante.
Notação O
� Usando notação O para o pior caso, define-se o limite superior do tempo 
de execução desse algoritmo para todas as entradas
� Ex: f(n) = 3n3+2n2+n é O(n3) pois 3n3+2n2+n <= 6n3 para n >=1
�
Operações com a notação O
Classes de Comportamento
Assintótico
� f(n) = O(1)
− O uso do algoritmo independe do tamanho de n
− As instruções do algoritmo são executadas um 
número fixo de vezes.
Classes de Comportamento
Assintótico
� f (n) = O(log n)
− Ocorre tipicamente em algoritmos que resolvem um 
problema transformando-o em problemas menores.
− Nestes casos, o tempo de execução pode ser considerado 
como sendo menor do que uma constante grande.
− Supondo que a base do logaritmo seja 2:
� Para n = 1.000, log2 = 10
� Para n = 1.000.000, log2 = 20
� Exemplo: Algoritmo de pesquisa binária.
Classes de Comportamento
Assintótico
� f (n) = O(n)
− Um pequeno trabalho é realizado sobre cada 
elemento de entrada
− Cada vez que n dobra de tamanho, o tempo de 
execução também dobra.
− Exemplo:
� Algoritmo de pesquisa seqüencial
Classes de Comportamento
Assintótico
� f (n) = O(n log n)
− Típico de algoritmos que resolvem um problema 
quebrando-o em problemas menores, resolvendo 
cada um deles independentemente e depois 
agrupando as soluções.
− Supondo que a base do logaritmo seja 2:
� Para n = 1.000.000, log2 = 20.000.000
� Para n = 2.000.000, log2 = 42.000.000
Classes de Comportamento
Assintótico
� f (n) = O(n2)
− Os itens de dados são processados aos pares, 
tipicamente em um anel dentro do outro.
− Algoritmos deste tipo são úteis para resolver 
problemas de tamanhos relativamente pequenos
− Exemplos: Algoritmos de ordenação simples como 
seleção e inserção.
Classes de Comportamento
Assintótico
� f (n) = O(n3)
− Úteis apenas para resolver problemas 
relativamente pequenos
− Sempre que n dobra o tempo de execução é
multiplicado por 8
− Exemplo:Algoritmo para multiplicação de matrizes.
Classes de Comportamento
Assintótico
� f (n) = O(2n)
− Não são úteis sob o ponto de vista prático
− Ocorrem na solução de problemas por força bruta
− Sempre que n dobra o tempo de execução fica 
elevado ao quadrado
− Exemplo: Algoritmo do Caixeiro Viajante
Classes de Comportamento
Assintótico
� f (n) = O(n!)
− O(n!) é dita complexidade exponencial, apesar de 
O(n!) ter comportamento muito pior do que O(2n).
− n = 20, temos que 20! = 2432902008176640000, 
um número com 19 dígitos.
− n = 40, temos aproximadamente 
816000000000000000000000000000000000000000
000000
− um número com 48 dígitos!
Classes de Comportamento
Assintótico
� Algoritmos polinomiais
� Um algoritmo cuja função de complexidade é
O(p(n)), onde p(n) é um polinômio de grau n, é
chamado de algoritmo polinomial no tempo de 
execução.
� Algoritmos exponenciais
� Um algoritmo cuja função de complexidade é
O(cn), c > 1, é chamado de algoritmo exponencial 
no tempo de execução.
� Algoritmos eficientes
� Executam em tempo 
polinomial.
� Algoritmos ineficientes
� Executam em tempo 
superpolinomial.
� Exceções
� Exemplo: 
− f(n) = 2n
− g(n) = n5
− n<20
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23
0
1000000
2000000
3000000
4000000
5000000
6000000
7000000
8000000
9000000
2n
n5
� Algoritmos polinomiais
� Mais úteis na prática.
� Tempo de execução menor em relação a 
algoritmos exponenciais, para entradas n grandes.
� Tratabilidade: 
� Problema tratável: Existe algoritmo polinomial.
� Problema intratável: Não existe algoritmo 
polinomial para resolvê-lo.
Algoritmo exponencial- Problema
do Caixeiro Viajante
Algoritmo exponencial- Problema
do Caixeiro Viajante
Análise de Tempo de Execução
• Comando de atribuição, de leitura ou de escrita: O(1)
• Seqüência de comandos: determinado pelo maior tempo 
de execução de qualquer comando da seqüência
• Comando de decisão: tempo dos comandos dentro do
comando condicional, mais tempo para avaliar a condição,
que é O(1)
• Anel: soma do tempo de execução do corpo do anel 
mais o tempo de avaliar a condição para terminação 
(geralmente O(1)), multiplicado pelo número de 
iterações
Análise de Tempo de Execução
• Quando o programa possui procedimentos não 
recursivos, o tempo de execução de cada 
procedimento deve ser computado separadamente um a 
um, iniciando com os procedimentos que não chamam 
outros procedimentos. A seguir devem ser avaliados os 
procedimentos que chamam os procedimentos que não 
chamam outros procedimentos, utilizando os tempos 
dos procedimentos já avaliados. Este processo é
repetido até chegar no programa principal.
• Quando o programa possui procedimentos 
recursivos, para cada procedimento é associada uma 
função de complexidade f (n) desconhecida,onde n 
mede o tamanho dos argumentos para o procedimento.
Exemplo
public static void ordena ( int v [ ] , int n) {
(1) for ( int i = 0; i < n − 1; i ++) {
(2) int min = i ;
(3) for ( int j = i + 1; j < n; j++)
(4) i f (v[ j ] < v[min] )
(5) min = j ;
/ Troca v[min] e v[i] /
(6) int x = v[min] ;
(7) v[min] = v[ i ] ;
(8) v[ i ] = x;
}
}
Exemplo-Anel Interno (linhas 3,4,e 
5)
• Contém um comando de decisão (O(1)) que contém apenas um 
comando de atribuição (O(1)). Quanto ao corpo do comando de 
decisão(linha 5), devemos considerar o pior caso, assumindo que 
será sempre executado
• O tempo para incrementar o índice do anel e avaliar sua condição
de terminação é O(1)
• O tempo combinado para executar uma vez o anel (linhas 3,4 e 5)
é O(max(1, 1, 1)) = O(1), conforme regra da soma para a notação O
• Como o número de iterações é n−i, o tempo gasto no anel é
O((n−i)×1) = O(n − i), conforme regra do produto para a notação O
Exemplo-Anel externo (linhas 1 a 
8)
• Contém, além do anel interno, quatro comandos de
atribuição nas linhas 2, 6, 7 e 8. Logo o tempo de 
execução das linhas 2 a 8 é O(max(1,(n − i),1,1,1)) = 
O(n − i)
• A linha (1) é executada n − 1 vezes. Assim, o tempo 
total para executar o programa é o somatório de (n-1) 
termos (n-i):
• Se considerarmos o número de trocas, o programa 
realiza exatamente n − 1 trocas
Procedimentos Recursivos
� Equação de recorrência:
� Um termo T(n) é especificado em função dos 
anteriores
� Para o fatorial:
− T(0) = 1
− T(n) = 1 + T(N-1)
T(n-1): é a mesma função 
executada em uma entrada 
uma unidade menor
O(1)
Resolver recorrências de 
procedimentos recursivos
Substituir os termos T(k) até que sejam reduzidos a T(0):
• T(n) = 1 + T(n-1)
• T(n-1) = 1 + T(n-2)
• ….
• T(2) = 1+T(1)
• T(1) = 1 + T(0)
• T(0) = 1
• Somando membro a membro, teríamos, ao final:
• T(n) = n + 1, ou seja, O(n)
Outro exemplo
O(1)
O(1)
n vezes
O(n)
T(n/3)
T(1) = 1
T(n) = n + T(n/3)
Torres de Hanói - solução
• Se existe só um disco,
• Passar o disco para a torre de destino
• Caso contrário,
• Passar (n-1) discos para a torre auxiliar
• Passar o maior disco para torre de destino
• Passar (n-1) discos para torre de destino
– Recorrência:
– T(n) = 1, se n=1
– T(n) = 2T(n-1)+1, se n>1
O(1)
O(1)
T(n-1)
T(n-1)
Torres de Hanói - Solução
• Expandindo:
– T(n)=2T(n-1)+ 1 T(n-1) = 2T(n-2) +1
– T(n)=4T(n-2) + 1 + 2 T(n-2) = 2T(n-3) + 1
– T(n)=8T(n-3) + 1 + 2 + 4
– Forma geral: T(n) = 2iT(n-i) + 2i – 1
– Para T(2) = T(n-i) → i = n-2
– Temos 2n-2 T(2) + 2n-2 – 1 e sabemos que 
– T(2) = 2T(1) +1 = 2+1 = 3
– Então, temos 3.2n-2 + 2n-2 – 1 = 4.2n-2 – 1Torres de Hanói - solução
• Continuando
• T(n) = 4. 2n-2 – 1 = 22. 2n-2 – 1 = 2n – 1
• Ou seja, a solução recursiva para as Torres de 
Hanói tem custo T(n) = 2n – 1 e é O(2n).