Análise de complexidade de algorítmos

Prévia do material em texto

Análise de Complexidade de Algoritmos
Estrutura de Dados
Prof. Carla Koike - CIC
 
Porque Analisar um algoritmo?
● Para avaliar sua performance e comparar 
diferentes algoritmos
● Mas analisar o que?
– tempo de execução e uso de memória
– pior caso e caso típico, dependendo das entradas
● Análise de algoritmos compara ALGORITMOS 
e não programas
 
Tipos de problemas na análise de 
algoritmos
● Análise de um algoritmo particular
Qual é o custo de usar um dado algoritmo na 
solução de um problema específico?
● Características que devem ser investigadas:
– número de vezes que cada parte do algoritmo deve 
ser executada (ou o tempo de execução)
complexidade do tempo
– quantidade de memória necessária
complexidade de espaço
 
Tipos de problemas na análise de 
algoritmos, cont.
● Análise de uma classe de algoritmos.
Qual é o algoritmo de menor custo possível para 
resolver um problema particular?
● Toda uma família de algoritmos é investigada, e 
procura-se identificar um que seja o melhor 
possível.
● Colocam-se limites para a complexidade 
computacional dos algoritmos pertencentes à 
classe
 
Executando um algoritmo
● A complexidade de um algoritmo pode ser analisada a partir 
de uma implementação executando em um computador.
– A eficiência do programa depende da linguagem (compilada ou 
interpretada)
– depende do sistema operacional
– depende do hardware (quantidade de memória, velocidade do 
processador e arquitetura)
● útil nas comparações entre programas em máquinas 
específicas, logo não somente os custos do algoritmo são 
comparados mas também os custos não aparentes 
(alocação de memória, indexação, carga de arquivos, etc)
 
Análise pelo modelo matemático
● Não depende do computador nem da 
implementação
● O custo das operações mais significativas deve 
ser especificado, e algumas operações são 
desprezadas.
● É possível analisar a complexidade do 
algoritmo dependendo dos dados de entrada
 
Exemplo 1
● Qual o custo do algoritmo?
soma <- 0
para i de 0 até n faça soma <- soma + i
● Somente atribuições são operações relevantes:
– duas atribuições (soma e i recebem zero)
– duas atribuições a cada laço ( soma recebe soma + 
i, e i recebe i+1)
– Total de atribuições: 2 + 2n
● Função que define a complexidade de tempo 
do algoritmo é g(n) = 2 + 2n
 
Exemplo 2
● Algoritmo: dividir elementos de uma matriz quadrada por 
uma constante k
soma <- 0
para i de 0 ate n faça
para j de 0 ate n faça
a[i,j] <- a[i,j]/k
● Número de atribuições:
– duas atribuições (soma e i recebem 0)
– para o laço externo: uma atribuição (i recebe i+1), n vezes
– para o laço interno: duas atribuições (a e j ), n2 vezes
● Complexidade de tempo: g(n) = 2 + n + 2n2
 
Análise da função complexidade
● Considere a função:
– g(n) = 2 + n + 2n2
● Crescimento dos termos em função de n:
– para n= 1, g(n) = 2 + 1 + 2, todos os termos tem o mesmo 
peso
– para n = 1000, g(n) = 2 + 1000 + 2000000, o último termo é 
dominante, portanto os dois primeiros podem ser 
desprezados
 
O melhor, o médio e o pior caso
● Melhor caso: função definida pelo menor número 
de passos executados para qualquer instância de 
tamanho n.
● Pior caso: função definida pelo maior número de 
passos executados para qualquer instância de 
tamanho n.
● Caso médio: função definida pela média do 
número de passos executados para qualquer 
instância de tamanho n.
 
O melhor caso, o caso médio e o 
pior caso
 
Complexidade Assintótica
● Para pequenos valores de n, a maioria dos 
algoritmos não representa problemas
● Estuda-se a complexidade somente para 
grandes valores de n, e essa complexidade é 
chamada assintótica
● O comportamento assintótico de g(n) 
representa o limite do comportamento do custo 
quando n cresce
 
Dominância assintótica
● Definição: Uma função f(n) domina 
assintoticamente outra função g(n) se existem 
duas constantes positivas c e m tais que, para 
n ≥ m, temos |g(n)| ≤ c x |f(n)|.
 
Notação O-Grande
● Escrevemos g(n) é O(f(n)) ( ou ainda g(n) = 
O(f(n)) ) para expressar que f(n) domina 
assintoticamente g(n). Lê-se “g(n) é da ordem 
no máximo f(n)”
● Exemplo:
– Sejam g(n) = (n + 1)2 e f(n) = n2. 
– As funções g(n) e f(n) dominam assintoticamente 
uma a outra, desde que |(n + 1)2| ≤ 4|n2| para n ≥ 1 
e |(n+1)2| ≥ |n2| para n ≥ 0
 
Notação O-Grande, cont.
● Definição:
– Uma função g(n) é O(f(n)) se existem duas 
constantes positivas c e m tais que |g(n)| ≤ |cf(n)|, 
para todo n ≥ m.
● Exemplos:
– g(n) = (n + 1)2.
– g(n) é O(n2), quando m = 1 e c = 4.
– Isto porque (n + 1)2 ≤ 4n2 para n ≥ 1.
 
Notação O-Grande, cont.
● g(n) = 3n3 + 2n2 + n é O(n3)
– Basta mostrar que 3n3 + 2n2 + n ≤ 6n3, para n ≥ 0.
– A função g(n) = 3n3 + 2n2 + n é também O(n4), 
entretanto esta afirmação é mais fraca do que dizer 
que g(n) é O(n3).
● g(n) = log
5
 n é O(log n)
n=10log10n
log5n=log510
log10n
log5n=log10 n×log510
Constante!
 
Operações com O-grande
● O(f(n)+g(n)) = O(max(f(n),g(n))
– Suponha três trechos de programa com 
complexidades O(n), O(n2) e O(nlogn),
– A complexidade dos três trechos é O(n2)
 
Notação Ω
● Definição:
– Uma função g(n) é Ω(f(n)) se existem duas 
constantes positivas c e m tais que |g(n)| ≥ |cf(n)|, 
para todo n ≥ m.
● Enquanto O(f(n)) oferece um limite superior 
para a taxa de crescimento de g(n), Ω(f(n)) 
seria um limite inferior
● Exemplo:
– g(n) = 3n3 + 2n2 é Ω(n3) basta fazer c = 1, e então 
3n3 + 2n2 ≥ n3 para n ≥ 0
 
Notação Ω, Limite Inferior 
 
Notação Θ
● Definição:
– Uma função g(n) é Θ(f(n)) se existirem constantes positivas 
c1, c2 e m tais que 0 ≤ c1f(n) ≤ g(n) ≤ c2f(n), para todo n≥ m. 
● A notação Θ é um limite assintótico firme (ou exato) de g(n)
 21
Diferenciando O e Ω
T(n)
T(n)  O(g(n))

 constantes c,n0 > 0
tais que 
 nn0, T(n)  cg(n)
cg(n)
n0
T(n)  Ω(g’(n))

 constantes c’,n’0 > 0
tais que 
 nn’0, T(n)  c’g’(n)
c’g’(n)
n’0
 
Exercícios
● Encontre o número de passos e a 
complexidade dos seguintes algoritmos:
para i de 0 a n-1 faça
 para j de 0 a n-1 faça
 a[i][j] = b[i][j] + c[i][j]
para i de 0 a n-2 faça
 para j de i+1 a n-1 faça
 temp = a[i][j]
 a[i][j] = a[j][i]
 a[j][i]=temp
 
Solução
para i de 0 a n-1 faça
 para j de 0 a n-1 faça
 a[i][j] = b[i][j] + c[i][j]
1 atribuição feita uma única vez: i=0
1 subtração feita uma única vez: n-1
1 soma feita n vezes: i+1
1 atribuição feita n vezes: i= i+1
1 atribuição feita n vezes: j=0
1 soma feita n*n vezes: j+1
1 atribuição feita n*n vezes: j = j+1
1 soma feita n*n vezes: b[i][j]+c[i][j]
1 atribuição feita n*n vezes: a[i][j]= b[i][j]+c[i][j]
2+3n+4n2=O(n2) e Ω(n2)
 
Solução
para i de 0 a n-2 faça
 para j de i+1 a n-1 faça
 temp = a[i][j]
 a[i][j] = a[j][i]
 a[j][i]=temp
1 atribuição feita uma única vez: i=0
1 subtração feita uma única vez: n-2
1 soma feita n-1 vezes: i+1
1 atribuição feita n-1 vezes j=i+1
4 atribuições e uma soma dentro realizadas no laço j:
j = j+1, temp = a[i][j], a[i][j] = a[j][i], a[j][i] = temp
feitas (n-1)+(n-2)+(n-3)+...1 vezes, ou seja 5* (Σ n-k), k=1 até n-1, = 5*n2/2 - 5/2
2+2*(n-1)+2.5n2-2.5
2.5n2+2n-2.5 = O(n2) e Ω(n2) 
 
Exercícios
● Mostre que:
– 2(n+a) = O(2n)
● Suponha que um algoritmo A e um algoritmo B, com 
funções de complexidade de temp a(n) = n2 – n + 549, e 
b(n) = 49n+49, respectivamente. Determine quais valores 
de n pertencentes ao conjunto dos números naturais para 
os quais A leva menos tempo para executar do que B.
   
Análise de Complexidade de AlgoritmosEstrutura de Dados
Profa. Carla Koike ­ CIC
   
Principais Classes de Problemas
● f(n) = O(1): complexidade constante
● f(n) = O(log n): complexidade logarítmica
● f(n) = O(n): complexidade linear
● f(n) = O(n log n): ene log de ene
● f(n) = O(n2): complexidade quadrática
● f(n) = O(n3): complexidade cúbica.
● f(n) = O(2n): complexidade exponencial
● f(n) = O(n!): complexidade fatorial
   
Se 1 instrução = 1μs ...
   
Exemplo: Caixeiro Viajante
● Um caixeiro viajante precisa visitar n cidades de tal forma que 
sua viagem inicie e termine em uma mesma cidade, e cada 
cidade deve ser visitada uma única vez. Supondo que sempre 
há uma rota entre duas cidades quaisquer, encontre a menor 
rota que o caixeiro viajante pode utilizar na sua viagem.
● Algoritmo simples: verificar todas as rotas e escolher a menor 
delas. Existe (n­1)! rotas possíveis, e cada rota envolve n 
adições para determinar a distância total: n! total de adições!
● Computador realiza 109 adições por segundo, resolver esse 
problema para 50 cidades levaria 1045 séculos de cálculo!
   
Algoritmos
● Algoritmo exponencial
– tempo de execução tem função de complexidade O(cn); 
c > 1.
●  Algoritmo polinomial:
– tempo de execução tem função de complexidade 
O(p(n)), onde p(n) é um polinômio.
● Algoritmos exponenciais: simples variações de pesquisa 
exaustiva.
●  Algoritmos polinomiais: obtidos mediante entendimento 
aprofundado da estrutura do problema.
   
Mas, tudo depende de n...
● Existem valores de n onde um algoritmo 
exponencial é mais rápido que um polinomial:
– f(n) = 2n e g(n) = n5, para n < 20, o algoritmo 
exponencial é mais rápido.
   
Técnicas de Análise de Algoritmos
● Considerar memória infinita
● Não considerar o sistema operacional nem o 
compilador
● Analisar de preferência o algoritmo e não o programa, 
e levar em conta o tamanho das entradas
● Somente alguns comandos são considerados: 
atribuição, adição, multiplicação e comparação, e eles 
executam em um único passo de tempo
   
Algumas dicas...
● A complexidade de um laço é igual ao número de 
comandos internos vezes o número de vezes que ele é 
executado
● Exemplo:
– para i de 1 até n faça soma <­ soma+1
– 1 atribuição externa ao laço
– comandos internos do laço: 1 atribuição, 1 soma, 1 
incremento
– laço é executado n vezes
– Complexidade g(n) = 3n + 1, O(n)
   
Algumas dicas ...
● Laços Aninhados: a complexidade  de laços 
aninhados é o produto dos tamanhos dos laços
● Exemplo:
– para i de 1 até n faça
–    para j de 1 até m faça
–          soma <­ soma + i + j
– Fora dos laços: 1 atribuição
– Dentro somente do laço i: 1 atribuição
– Dentro dos dois laços: 1 atribuição e 2 somas
– g(n) = 1 + n + 3(nm), O(nm)
   
Algumas dicas ...
● Para uma seqüência de laços do algoritmo:
– para i de 1 até n faça soma <­ soma+1
– para i de 1 até n faça
–    para j de 1 até n faça
–          soma <­ soma + i + j
– A primeira parte é O(n) e a segunda parte é O(n2)
– Portanto esse trecho de algoritmo é O(n2)
   
Algumas dicas ...
● No caso de testes condicionais, a complexidade é a maior das duas 
partes do teste
● Exemplo:
– Se teste = 1 então
–     para i de 1 até n faça soma <­ soma +i
– senão 
–    para i de 1 até n faça
–       para i de 1 até n faça
–           soma <­ soma + i + j
● “Se” é O(n) e “Então” é O(n2), portanto complexidade é O(n2)
   
Algumas dicas ...
● Funções não recursivas
– O tempo de execução de cada procedimento deve ser 
computador separadamente, um a um, iniciando com 
os procedimentos que não chamam outros 
procedimentos.
– A seguir, avalia­se os procedimentos que chamam os 
procedimentos que não chamam outros procedimentos, 
usando os tempos já avaliados
– Continua sucessivamente até chegar ao programa 
principal.
   
Algumas dicas ...
● Funções Recursivas
– Associamos a complexidade da função recursiva uma 
equação de recorrência.
– Uma equação de recorrência é uma equação ou inequação 
que descreve uma função em termos do seu valor para 
entradas menores.
– Resolvendo a equação de recorrência é possível avaliar a 
classe do algoritmo
– Existem técnicas para resolver equações de recorrência...
   
Exercícios 1
● Encontre a complexidade computacional para o 
seguinte laço:
for (cnt1 =0,i=1;i<=n;i++)
for (j=1;j<=n;j++)
cnt++;
   
Exercícios 2
● Encontre a complexidade computacional para o seguinte 
algoritmo de ordenação:
inteiro i,j,min,x
inicio
 para i de 1 ate n­1 faca
inicio
    min = 1
para j de i+1 ate n faca
se A[j] < A[min] entao min = j
    x = A[min]
    A[min] = A[i]
    A[i] = x
    fim
fim
	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