aula3-assintotica

Prévia do material em texto

Algoritmos e Estruturas de Dados I 
Complexidade Assintótica
Notação Assintótica
Classes de Complexidade
Cristina Duarte Murta
2013/2
   
Conteúdo
 Relembrando
 Análise de complexidade de algoritmos
 Melhor caso, pior caso, caso médio
 Complexidade assintótica
 Notação assintótica
 Classes de complexidade
 Um problema intratável
   
Análise de Algoritmos
 Analisar um algoritmo é estimar os recursos que ele necessita para 
sua execução em termos de 
 Tempo de execução
 é proporcional ao número de comandos ou operações relevantes 
executadas
 calculado a partir do número de instruções executado para um 
algoritmo com uma dada entrada de dados
 Espaço em memória
 quantidade de memória requerida
 medido também em relação ao tamanho da entrada
   
Complexidade de tempo
 o número de passos executados por um algoritmo é uma medida da 
complexidade de tempo do algoritmo
 O número de passos executados depende do tamanho da entrada 
 e pode depender também do arranjo específico dos dados na entrada, isto 
é, de como os dados estão combinados entre si para uma entrada de 
mesmo tamanho
   
Definição de casos de complexidade
 Para uma mesma entrada de tamanho n podemos identificar os 
seguintes casos quanto ao número de instruções e, consequentemente, 
o tempo de execução:
 melhor caso
 menor tempo de execução sobre todas as entradas de tamanho n
 é a entrada para a qual o algoritmo executa menos comandos, ou seja, é mais 
rápido, comparando com todas as entradas de tamanho n
 pior caso
 maior tempo de execução sobre todas as entradas de tamanho n
 é a entrada para a qual o algoritmo executa mais passos, isto é, demora mais, 
comparado com todas as entradas de tamanho n
 caso médio ou esperado
 corresponde à média dos tempos de execução para TODAS as entradas de 
tamanho n 
   
Importância dos casos
 Pior caso
 muitas vezes é considerada a medida mais importante
 fornece um limite superior para o número de passos que o algoritmo pode 
efetuar, para qualquer entrada de tamanho n
 Caso médio
 é o caso esperado
 é uma medida da maioria dos casos
 considerada muito importante
 a análise do caso médio pode ser complexa
 Melhor caso
 uso menos freqüente, para situações específicas
   
Exemplos 
 Pesquisa com sucesso em vetor não ordenado
 Melhor caso: 1
 Pior caso: n
 Caso médio: (n+1)/2
 Quicksort
 Melhor caso: n log n
 Pior caso: n2 
 Caso médio: n log n
Observem que o caso 
médio não é a média 
entre o melhor e o 
pior caso
   
Técnicas de Análise de Algoritmos
 a análise de algoritmos utiliza técnicas de matemática discreta:
 manipulação de somas e produtos
 contagem e enumeração dos elementos de um conjunto
 permutações 
 fatoriais e coeficientes binomiais
 solução de equações de recorrência
 determinar o tempo de execução de um programa pode ser uma 
tarefa matematicamente complexa
 determinar a ordem do tempo de execução pode ser uma tarefa 
mais simples
 neste caso, não estamos preocupados em determinar de forma exata a 
função de complexidade
   
Comportamento Assintótico das funções de custo
 o custo de um algoritmo é função do tamanho n do problema
 o custo aumenta quando n aumenta
 para valores pequenos de n qualquer algoritmo custa pouco para ser 
executado
 inclusive os algoritmos ineficientes
 para problemas de tamanho pequeno a escolha do algoritmo não é um 
problema crítico
 logo, a análise de algoritmos é importante para valores grandes de n
 assim, é importante considerar o comportamento das funções de custo 
para valores grandes de n
   
Comportamento Assintótico
 Comportamento assintótico das funções de custo
 representa o comportamento das funções para n grande, isto é, o limite de 
f(n) quando n cresce
 quando o tamanho da entrada é muito grande, apenas a ordem de 
crescimento das funções de custo é relevante
 eficiência assintótica
 Análise assintótica
 como o algoritmo se comporta quando o tamanho do problema é 
muito grande?
 Tempo de execução
 Espaço em memória
   
Notação Assintótica
 Para expressar o comportamento assintótico de uma função de 
custo utilizamos algumas notações:
 Notação O (O grande - Big Oh)
 Limite assintótico superior
 Notação Θ (Theta)
 Limite assintótico justo (restrito, firme)
 Notação Ω (Omega)
 Limite assintótico inferior
   
Limite superior - Notação O
 Definição: uma função f(n) é 
O(g(n)) se existem duas 
constantes c, n
0 
>= 0 tais que 
0 ≤ f(n) ≤ c·g(n) 
para todo n ≥ n
0
significado: c·g(n) é um limite superior 
de f(n) para valores grandes de n
 f(n) = O(g(n))
dizemos que g(n) domina assintoticamente f(n)
   
Análise de algoritmos: Notação O
 Exemplo 1
 f(n) = 3n2+2n+1 é O(n2)
3n2+2n+1 ≤ c.n2 dividindo ambos os lados por n2 
3 + 2/n + 1/n2 ≤ c verdadeiro para n
0
 = 1 e c = 6
 Exemplo 2
 f(n) = 2n é O(n2) 
2n ≤ c.n2 dividindo ambos os lados por n2 
2/n ≤ c verdadeiro para n
0
 = 1 e c = 2
   
Análise de algoritmos: Notação O
 Exemplo 3
 f(n) = 2n é O(n) 
2n ≤ cn dividindo ambos os lados por n 
2 ≤ c verdadeiro para n
0
 = 0 e c = 2
 Exemplo 4
 f(n) = 1000n3 é O(n10)
1000n3 ≤ cn10 verdadeiro para n
0
 = 3 e c = 1
   
Análise de algoritmos: Notação O
 Exemplo 5
 Seja g(n) = n e f(n) = n2
 g(n) = O(f(n)) ?
 Para responder: encontrar 2 constantes positivas c e n
0
 tais que 
g(n)≤ c·f(n) para todo n ≥ n
0
 Fazendo c = 1 e n
0
= 0 => g(n) é O ( f(n) ) 
 g(n) domina assintoticamente f(n)? 
 f(n) é O(g(n))? Não... 
   
Análise de algoritmos: Notação O
 Notação O: indica um limite superior para a ordem de 
crescimento da função de custo
 Considerações
 constantes aditivas e multiplicativas não são importantes: podem 
ser desprezadas
 um polinômio de grau k é O(nk) 
 o termo de maior ordem da função é que conta
 isto é análise assintótica
 à medida que a entrada cresce, o termo de maior ordem domina a 
função de custo
   
Análise de algoritmos: Notação O
 Notação O 
 Expressa o limite superior do custo: upper bound
 Mais exemplos
 f(n) = 3n3 + 2n2 + n+1 é O(n3)
 f(n) = 7n2 é O(n4) 
 f(n) = 8n3 + 5 log n + 2 é O(n3)
 f(n) = 2log2 n + log n + 3 é O(log2 n)
 F(n) = 5.2n + 5n10 é O(2n)
   
Notação O: perguntas
 O problema de encontrar o maior elemento de um conjunto de n 
elementos
 é O(n)?
 é O(n3)?
 é O(log n)?
 é O(2n)?
 Para resolver um problema P são conhecidos dois algoritmos
 Algoritmo A com custo 100n
 Algoritmo B com custo 2 n2
 Qual é o melhor algoritmo? 
   
Notação Assintótica
 Para expressar o comportamento assintótico de uma função de custo 
utilizamos algumas notações que indicam a taxa de crescimento do tempo de 
execução quando o tamanho da entrada cresce
 Notação O (O grande - Big Oh)
 Limite assintótico superior
 Notação Θ (Theta)
 Limite assintótico justo (restrito, firme)
 Notação Ω (Omega)
 Limite assintótico inferior
   
Notação Omega - limite inferior
 Uma função f(n) é Ω(g(n)) se 
existem constantes positivas c, 
n
0
 tais que 
f(n) ≥ c·g(n) para n ≥ n
0
 
 Significado 
 c·g(n) é um limite inferior de 
f(n) para n grande
 lower bound
 Exemplo
 f(n) = n2 é Ω(n)
 basta fazer c = 1 e n0 = 1 
   
Notação Theta - limite estrito, justo, firme
 Uma função f(n) é Θ(g(n)) se é 
O(g(n)) e Ω(g(n)), isto é:
 se existem constantesc
1
, c
2
, n
0 
> 0 tais que 
 0 ≤ c1 g(n) ≤ f(n) ≤ c2g(n) 
 
 para todo n≥ n
0
 Significado
 f(n) e g(n) tem a mesma ordem 
de crescimento 
 Θ indica um limite firme
 tight bound
   
Notação Theta – limite firme
 Exemplo: mostrar que 
 f(n) = 2n+1 é Θ(n)
 Encontrar constantes c
1
, c
2
, n
0 
> 0 tais que 
0 ≤ c1 n ≤ 2n + 1 ≤ c2n para todo n≥n0
 primeira parte da equação: c1 n ≤ 2n + 1
verdadeiro para c1 = 1 e n0 = 1
 segunda parte da equação: 2n + 1 ≤ c2n 
verdadeiro para c2 = 3 e n0 = 1
Portanto, 2n+1 = Θ(n)
   
Limites assintóticos
justo superior inferior
   
Outras notações assintóticas: o e ω
 mais duas notações complementares: o minúsculo e ω
 Uma função f(n) é o(g(n)) se, para qualquer constante c > 0 existe 
uma constante n
0
 > 0 tal que 
 
f(n) < c g(n) ∀ n ≥ n
0
 
 exemplo: 2n = o(n2) para n
0
 = 1 
 exemplo: 2n2 = O(n2) mas 2n2 ≠ o(n2) 
Denota limite 
superior não 
assintoticamente 
restrito
   
Outras notações assintóticas: o e ω
 mais duas notações complementares: o minúsculo e ω
 Uma função f(n) é ω(g(n)) se, para qualquer constante c > 0 existe 
uma constante n
0
 > 0 tal que 
 c g(n) < f(n) ∀ n ≥ n
0
 
 exemplo: n2/2 = ω(n) para n
0
 = 1
 exemplo: n2/2 = Ω(n2) mas n2/2 ≠ω(n2) 
Denota limite 
inferior não 
assintoticamente 
restrito
   
Propriedades e características
● O, Θ, Ω são transitivas e reflexivas 
● f(n) = O(g(n)) e g(n) = O(h(n)) então f(n) = O(h(n))
● f(n) = O(f(n))
● Θ é simétrica
● f(n) = Θ(g(n)) sse g(n) = Θ(f(n))
● f(n) = O(g(n)) sse g(n) = Ω(f(n))
● analogia com 2 números reais a e b
 f(n) = O(g(n)) ≈ a ≤ b
 f(n) = o(g(n)) ≈ a < b
 f(n) = Ω(g(n)) ≈ a ≥ b
 f(n) = ω(g(n)) ≈ a > b
 f(n) = Θ(g(n)) ≈ a = b
   
Operações com a Notação O
 Sejam f, g funções reais positivas e k uma constante
 Então, temos:
f(n) = O(f(n))
O(f(n)) + O(f(n)) = O(f(n)) 
O(O(f(n))) = O(f(n)) 
O(k.f(n)) = k.O(f(n)) = O(f(n)) 
O(f(n) + g(n)) = O(g(n)) + O(f(n))
O(g(n)) + O(f(n)) = O(max(f(n), g(n)))
O(g(n)) * O(f(n)) = O(f(n) * g(n)) 
f(n)*O(g(n)) = O(f(n) * g(n)) 
   
Notação assintótica em equações
 notação assintótica em fórmulas: como interpretar
 exemplo:
 significado: a notação está substituindo uma função que não é 
importante definir precisamente
 é equivalente a: 
 em que f(n) = θ (n), por exemplo, f(n) = 4n + 5
   
Notação assintótica em equações
 Atenção quanto ao uso da notação O
 e outras notações que envolvem quantidades não precisas
=> o sinal de igualdade é unidirecional
a igualdade significa "pertence" ou "está contido"
 Exemplo:
 Válido: n = O(n2)
 Inválido: O(n2) = n
 Assim:
 nunca devemos escrever uma igualdade onde a notação O aparece 
sozinha do lado esquerdo
 se não poderíamos concluir um absurdo tal como n2 = n
   
Classes de Complexidade
 Classificação dos problemas segundo seu comportamento 
assintótico especificado pela notação O
 complexidade constante: f(n) é O(1)
 complexidade logarítmica: f(n) é O(log n)
 complexidade linear: f(n) é O(n)
 complexidade linear logarítmica: f(n) é O(nlog n)
 complexidade quadrática: f(n) é O(n2)
 complexidade cúbica: f(n) é O(n3)
 complexidade exponencial: f(n) é O(2n)
   
Crescimento das funções de custo
0
250
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
f(n) = n
f(n) = log(n) 
f(n) = n log(n)
f(n) = n^2
f(n) = n^3
f(n) = 2^n
   
Crescimento das funções de custo
0
500
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
f(n) = n
f(n) = log(n) 
f(n) = n log(n)
f(n) = n^2
f(n) = n^3
f(n) = 2^n
   
Crescimento das funções de custo
0
1000
1 3 5 7 9 11 13 15 17 19
f(n) = n
f(n) = log(n) 
f(n) = n log(n)
f(n) = n^2
f(n) = n^3
f(n) = 2^n
   
Crescimento das funções de custo
0
1000
2000
3000
4000
5000
1 3 5 7 9 11 13 15 17 19
f(n) = n
f(n) = log(n) 
f(n) = n log(n)
f(n) = n^2
f(n) = n^3
f(n) = 2^n
   
Análise de complexidade
 A análise de complexidade dos algoritmos revela a importância de 
encontrar algoritmos com a menor taxa de crescimento possível para a 
resolução dos problemas
 Em última análise a taxa de crescimento dos algoritmos determina qual 
é o maior problema que pode ser resolvido por um computador 
   
Algoritmos exponenciais x polinomiais
 algoritmo com tempo de execução exponencial: O(2n) ou superior
 algoritmo com tempo de execução polinomial: O(p(n)) onde p(n) é um 
polinômio
 o tempo de execução destas duas classes é muito distinto quando n cresce
 algoritmos exponenciais estão relacionados a
 algoritmos de pesquisa exaustiva
 solução por força bruta
 problemas intratáveis
 algoritmos polinomiais: resultado de uma boa solução para o problema
 Um problema é considerado
 bem resolvido: se existe um algoritmo polinomial para resolvê-lo
 intratável: se não existe um algoritmo polinomial para resolvê-lo
   
Exemplo de um problema intratável
 O problema do caixeiro viajante
 Um caixeiro viajante deseja visitar n cidades de tal forma que sua viagem 
inicie e termine em uma mesma cidade e cada cidade é visitada apenas 
uma vez; supondo que exista sempre um caminho entre duas cidades 
quaisquer, o problema é encontrar a menor rota que o caixeiro viajante 
pode utilizar na sua viagem
 Qual é o custo para encontrar a menor rota?
   
Problema do caixeiro viajante
Para 4 cidades
C1
C2
C3
C4
8
8
9
5 3
4
Solução: enumerar as rotas; 
calcular a distância para cada rota; 
escolher a menor 
   
Problema do caixeiro viajante
Para 4 cidades
C1
C2
C3
C4
Rotas possíveis
C1 C2 C3 C4 C1 = 25
C1 C2 C4 C3 C1 = 24
C1 C3 C2 C4 C1 = 25
C1 C3 C4 C2 C1 = 24
C1 C4 C2 C3 C1 = 25
C1 C4 C3 C2 C1 = 25
8
8
9
5 3
4
Solução: enumerar as rotas; 
calcular a distância para cada rota; 
escolher a menor 
   
Problema do caixeiro viajante
 Para 4 cidades
 número de rotas = 6 
 número de adições por rota
 C1C3 + C3C4 + C4C2 + 
C2C1 : 3 adições
 número total de adições
 6*3 = 18
 Para n cidades
 número de rotas = (n-1)!
 número de adições = n -1
 Número total de adições = 
 (n-1)! * (n -1) = n! – (n-1)!
 Para n = 50 => número de 
adições = ?
Calcular o tempo é necessário para obter a solução do problema
   
Problema do caixeiro viajante
 Para 4 cidades
 número de rotas = 6 
 número de adições por rota
 C1C3 + C3C4 + C4C2 + 
C2C1 : 3 adições
 número total de adições
 6*3 = 18
 Para n cidades
 número de rotas = (n-1)!
 número de adições = n -1
 Número total de adições = 
 (n-1)! * (n -1) = n! – (n-1)!
 Para n = 50 
 número de adições = 1064
Quanto tempo é necessário apenas para executar as adições?
Em um computador que faz 109 adições por segundo
=> 1045 séculos apenas para calcular as rotas
   
Bibliografia
 Knuth, volume 1
 págs 94-107
 Cormen, Leiserson, Rivest, Stein
 Algoritmos: teoria e prática - 2ª. Edição – tradução
 Cap1: págs 3 a10
 Cap2: págs 11 a 20
 Cap3: págs 32 a 40
 Nivio Ziviani
 Projeto de Algoritmos, segunda edição
 Cap. 1
	Complexidade Assintótica Notação Assintótica Classes de Complexidade
	Conteúdo
	Análise de Algoritmos
	Complexidade de tempo
	Slide 5
	Importância dos casos
	Exemplos 
	Slide 8
	Comportamento Assintótico das funções de custo
	Comportamento Assintótico
	Notação Assintótica
	Limite superior - NotaçãoO
	Análise de algoritmos: Notação O
	Slide 14
	Slide 15
	Slide 16
	Slide 17
	Notação O: perguntas
	Slide 19
	Notação Omega - limite inferior
	Notação Theta - limite justo
	Slide 22
	Limites assintóticos
	Outras notações assintóticas 
	Slide 25
	Propriedades e características
	Slide 27
	Slide 28
	Slide 29
	Classes de Complexidade
	Crescimento das funções de custo
	Slide 32
	Slide 33
	Slide 34
	Análise de complexidade
	Algoritmos exponenciais x polinomiais
	Exemplo de um problema intratável
	Problema do caixeiro viajante
	Slide 39
	Slide 40
	Slide 41
	Bibliografia