08. Complexidade de Algoritmos

Prévia do material em texto

Ju
d
so
n
 S
an
to
s 
S
an
ti
ag
o
COMPLEXIDADE DE ALGORITMOS
Estrutura de Dados I
Algoritmo
 Seqüência de passos computacionais que 
transformam a entrada em uma saída
 Uma ferramenta para resolver um problema
computacional
 Exemplo: Ordenar uma seqüência de 
números em ordem crescente
Algoritmo
Entrada Saída
Algoritmo
 Entrada: Uma seqüência de n números 
<a1, a2, …, an>
 Saída: Uma permutação (reordenação) 
<a1’, a2’, …, an’> da seqüência de entrada, tal 
que a1’ ≤ a2’ ≤ … ≤ an’
 Instância de um problema de ordenação:
 Entrada: <31,41,59,26,41,58>
 Saída: <26,31,41,41,58,59>
Problemas Computacionais
 Comércio eletrônico: manter privativa 
informações em uma transação
 Alocação de recursos: designar tripulações 
para vôos da forma mais econômica possível
 Roteamento: escolher a melhor rota (mais 
rápida ou mais barata) entre dois pontos no 
mapa
 Classificação: retornar as páginas internet 
mais relevantes para uma determinada 
pesquisa
Analisar Algoritmos
 Analisar um algoritmo compreende:
 Corretude
 Existem várias técnicas para verificar se um 
programa dá sempre a saída correta:
 Verificação Formal 
 Provadores de teorema
 Eficiência
 Obter uma medida de desempenho do algoritmo:
 Tempo de execução
 Análise de complexidade
Resultados da Análise
 Tratabilidade de um problema
 O problema do caixeiro viajante é NP-Completo, não 
possui uma solução eficiente
 Problemas NP-Completos surgem com bastante 
freqüência em aplicações reais
 Comparativo de eficiência
 Ordenação por inserção: c1n
2
 Ordenação por intercalação: c2 lg n
 Com c1=2 e c2=50, para ordenar um milhão de números 
a inserção demora 200.000 segundos e a intercalação 
100 segundos (máquina processando 10 milhões/seg.) 
Ordenação Por Inserção
 Um algoritmo eficiente para ordenar uma 
pequena quantidade de elementos
 Funciona da mesma forma que ordenamos as 
cartas de uma baralho na mão
 Entrada: Arranjo A[1..n] contendo uma 
seqüência de comprimento n
 Algoritmo: Os elementos são reordenados 
dentro do próprio arranjo
 Saída: Arranjo A[1..n] reordenado 
Ordenação por inserção
INSERTION-SORT(A)
1 para j = 2 até comprimento[A] faça
2 chave = A[j]
3 i = j-1
4 enquanto i > 0 e A[i] > chave faça
5 A[i+1] = A[i]
6 i = i – 1
7 A[i+1] = chave
Exemplo:
5 2 4 6 1 3
1 2 3 4 5 6
Análise de Algoritmos
 Analisar a eficiência de um algoritmo significa 
prever o tempo de computação
 O tempo de computação varia: 
 A velocidade da máquina utilizada
 O compilador empregado
 As habilidades do programador
 É preciso abstrair a máquina
 O modelo RAM (Random Access Machine) 
vem sendo usado com sucesso desde o final 
da década de 60
O Modelo RAM
Simula o funcionamento de um computador 
elementar
Memória
Unidade de 
Controle e 
Processamento
Unidade de 
Entrada
Unidade de 
Saída
O Modelo RAM
 Um programa é um conjunto de instruções I
 Cada instrução I possui um tempo de 
execução associado t(I)
 Se um programa P contém r1 instruções do 
tipo I1, r2 instruções do tipo I2, até rm
instruções do tipo Im, o tempo para executar 
P será:



m
j
jj ItrT
1
)(
O Modelo RAM
 Para simplificar o problema, o modelo RAM 
considera sempre t(I)=1
 Assim o valor do tempo de execução é o 
número total de instruções computadas



m
j
jrT
1
Análise pelo Modelo RAM
Algoritmo: Repetição Simples vezes (rj)
1 para i = 1 até n faça n+1
2 imprimir "Complexidade" n
  12)1(  nnnnT



m
j
jrT
1
Análise pelo Modelo RAM


















4
8
10
3
3
5
6
1
1
3
4
2
Algoritmo: Soma de matrizes vezes
1 para i = 1 até n faça n+1
2 para j = 1 até n faça n*(n+1)
3 cij = aij + bij n
*n
  122)()1( 222  nnnnnnnT
Análise pelo Modelo RAM


















23
19
10
20
3
5
6
1
*
1
3
4
2
Algoritmo: Multiplicação de matrizes vezes
para i = 1 até n faça n+1
para j = 1 até n faça n*(n+1)
cij = 0 n*n
para k = 1 até n faça n*n*(n+1)
cij = cij + aik . bkj n*n*n
  1232)()()1( 2332322  nnnnnnnnnnnT
Análise pelo Modelo RAM
Algoritmo: Seqüência de Instruções vezes (rj)
1 ler num 1
2 imprimir num 1
  2)11( nT
m
j
jrT
1
Análise do INSERTION-SORT
INSERTION-SORT(A) custo vezes
1 para j = 2 até comprimento[A] faça 1 n
2 chave = A[j] 1 n-1
3 i = j-1 1 n-1
4 enquanto i > 0 e A[i] > chave faça 1
5 A[i+1] = A[i] 1
6 i = i – 1 1
7 A[i+1] = chave 1 n-1
Seja tj o número de vezes que o teste da linha 4 é executado 
para esse valor de j

n
j j
t
2
)1(
2 
n
j j
t
 
n
j j
t
2
)1(
Análise do INSERTION-SORT
INSERTION-SORT(A) custo vezes
1 para j = 2 até comprimento[A] faça 1 n
2 chave = A[j] 1 n-1
3 i = j-1 1 n-1
4 enquanto i > 0 e A[i] > chave faça 1
5 A[i+1] = A[i] 1
6 i = i – 1 1
7 A[i+1] = chave 1 n-1

n
j j
t
2
)1(
2 
n
j j
t
 
n
j j
t
2
)1(
  


n
j
j
n
j
j
n
j
j ntttnnnnT
222
)1()1()1()1()1(
Tempo de Execução
 O tempo de execução depende:
 Do tamanho da entrada 
 De quão ordenados os números já estão na 
seqüência de entrada
 Melhor caso: entrada ordenada
 Pior caso: entrada invertida
 Caso médio: situação intermediária
  


n
j
j
n
j
j
n
j
j ntttnnnnT
222
)1()1()1()1()1(
Análise do Melhor Caso
  )1(00)1()1()1(  nnnnnnT
INSERTION-SORT(A) custo vezes
1 para j = 2 até comprimento[A] faça 1 n
2 chave = A[j] 1 n-1
3 i = j-1 1 n-1
4 enquanto i > 0 e A[i] > chave faça 1
5 A[i+1] = A[i] 1
6 i = i – 1 1
7 A[i+1] = chave 1 n-1
Melhor caso ocorre quando o arranjo já está ordenado: 
tj=1

n
j j
t
2
)1(
2 
n
j j
t
 
n
j j
t
2
)1(
Análise do Melhor Caso
INSERTION-SORT(A) custo vezes
1 para j = 2 até comprimento[A] faça 1 n
2 chave = A[j] 1 n-1
3 i = j-1 1 n-1
4 enquanto i > 0 e A[i] > chave faça 1
5 A[i+1] = A[i] 1
6 i = i – 1 1
7 A[i+1] = chave 1 n-1
Tempo de execução é uma função linear de n

n
j j
t
2
)1(
2 
n
j j
t
 
n
j j
t
2
)1(
  45  nnT
Análise do Pior Caso
INSERTION-SORT(A) custo vezes
1 para j = 2 até comprimento[A] faça 1 n
2 chave = A[j] 1 n-1
3 i = j-1 1 n-1
4 enquanto i > 0 e A[i] > chave faça 1
5 A[i+1] = A[i] 1
6 i = i – 1 1
7 A[i+1] = chave 1 n-1
Pior caso ocorre quando o arranjo está em ordem inversa:tj=j

n
j j
t
2
)1(
2 
n
j j
t
 
n
j j
t
2
)1(
1
2
)1(
2




nn
j
n
j 2
)1(
)1(
2



nn
j
n
j
Análise do Pior Caso
INSERTION-SORT(A) custo vezes
1 para j = 2 até comprimento[A] faça 1 n
2 chave = A[j] 1 n-1
3 i = j-1 1 n-1
4 enquanto i > 0 e A[i] > chave faça 1
5 A[i+1] = A[i] 1
6 i = i – 1 1
7 A[i+1] = chave 1 n-1
O tempo de execução é uma função quadrática de n

n
j j
t
2
)1(
2 
n
j j
t
 
n
j j
t
2
)1(
  4
2
7
2
3 2  nnnT
Análise do Caso Médio
 No caso médio a entrada está parcialmente 
ordenada com tj=j/2
 T(n) continua sendo uma função quadrática 
de n  caso médio é igual ao pior caso
 Para alguns problemas pode não ser trivial 
descobrir a entrada "média"
 Existem problemas para os quais asentradas 
não têm a mesma probabilidade de acontecer
Ordem de Crescimento
 Usamos abstrações para analisar o 
procedimento INSERTION-SORT
 Ignoramos o custo real de cada instrução ao 
considerá-lo constante e expressar o tempo de 
execução como an2+bn+c
 A ordem de crescimento é mais uma abstração
 O que nos interessa é apenas a taxa de crescimento do 
algoritmo e não sua T(n)
 Consideramos apenas o termo de maior ordem
 A ordenação por inserção tem um tempo de 
execução de pior caso igual a O(n2)
Ordem de Crescimento
 Usamos abstrações para analisar o 
procedimento INSERTION-SORT
 Ignoramos o custo real de cada instrução ao 
considerá-lo constante 
 A ordem de crescimento é mais uma 
abstração
 O que nos interessa é apenas a taxa de 
crescimento do algoritmo e não sua T(n)
 Consideramos apenas o termo de maior ordem
Ordem de Crescimento
 O pior caso da ordenação por inserção tem 
uma taxa de crescimento da ordem de n2
 A complexidade de pior caso do algoritmo de 
ordenação por inserção é O(n2)
  4
2
7
2
3 2  nnnT
Ordem de Crescimento
 Taxas de crescimento comuns
Grande-O Nome
O(1) Constante
O(log n) Logariítmica
O(n) Linear
O(n log n) Log-linear
O(n2) Quadrática
O(n3) Cúbica
O(2n) Exponencial
O(n!) Fatorial
Ordem de Crescimento
 Taxas de crescimento comuns
Ordem de Crescimento
 A notação O é chamada de notação assintótica
 A complexidade de um algoritmo é uma medida 
de tendência: quando o tamanho da entrada 
tende ao infinito, um algoritmo O(n2) será mais 
rápido que um O(n3)
 A avaliação da ordem de crescimento pode ser 
incorreta para entradas pequenas
 Para arranjos de comprimento inferior a 44, a 
ordenação por inserção O(n2) é mais rápida que a 
ordenação por intercalação O(n lg n).
Conclusão
 É importante analisar um algoritmo e obter 
uma medida de sua complexidade para poder 
compará-lo com outros algoritmos 
 No modelo RAM o custo de cada instrução é 
unitário e tempo de execução é o número 
total de instruções executadas
 A notação assintótica fornece uma medida de 
desempenho independente da velocidade da 
máquina, do compilador ou da habilidade do 
programador