PCS-3110
Algoritmos e Estrutura de Dados
para Engenharia Elétrica
Módulo 2: Análise de Algoritmos
vídeo 1 - Introdução
Escola Politécnica da Universidade de São Paulo
Análise de algoritmos
[Link]
2
Análise de algoritmos
[Link]
3
Análise de algoritmos
A análise de algoritmos estuda a correção e o
desempenho de algoritmos. Em outras
palavras, a análise de algoritmos procura
respostas para perguntas do seguinte tipo:
• Este algoritmo resolve o meu problema?
• Quanto tempo o algoritmo consome para processar
uma 'entrada' de tamanho n?
[Link]
4
Análise de algoritmos: introdução
Para responder a pergunta grifada no slide
anterior é importante saber
• Como calcular o tempo de execução do algoritmo?
iconicbestiary - [Link] 5
Análise experimental
"Cronômetro"
Fatores que afetam o tempo
• Complexidade do algoritmo
• Entrada do programa
• Tipos usados (Ex: int ou double, lista ligada ou vetor)
• Tipo das instruções usadas
• Código gerado pelo compilador
• Sistema operacional
• Programas em execução
• Hardware considerado (Ex: 486 ou um i7)
6
Exemplo
Ambiente
• Windows 8.1
• Intel i5 (3ª geração) com 8GB
• Implementação em C++ usando MinGW
Analisando experimentalmente o tempo de
execução dos algoritmos
• Selection-Sort(A)
• Insertion-Sort(A)
7
Exemplo
8
Exemplo
Entradas são vetores aleatórios de tamanhos
diversos e o tempo de execução é dado em
segundos
Tamanho Insertion-Sort (s) Selection-Sort (s)
1000 0,001 0,002
5000 0,020 0,030
10000 0,060 0,119
50000 1,479 3,017
100000 6,016 11,870
9
Conclusões a partir do exemplo
Parece que Insertion-Sort ordena mais rápido
que Selection-Sort...
Pergunta:
• Como analisar tempo de execução de algoritmo sem
fazer análise experimental????
10
PCS-3110
Algoritmos e Estrutura de Dados
para Engenharia Elétrica
Módulo 2: Análise de Algoritmos
vídeo 2 – Modelo de análise
Escola Politécnica da Universidade de São Paulo
Análise de algoritmos
Motivação
• Facilita a comparação de algoritmos
• Permite predizer o desempenho em novos ambientes
• Facilita a definição de valores de parâmetros para o
algoritmo
Quando usar o algoritmo
2
Análise de algoritmos
Usa-se um modelo de análise
• Ideia de Donald Knut
Base: número de passos executados
Abstração
• Passos com o mesmo custo
• Independente de compilador, SO, hardware, etc.
Baseado no tamanho da entrada
Considera o melhor, o pior e o caso médio
• Em geral a ênfase é no pior caso
3
Exemplo
Soma dos elementos de um vetor
• Considerando [Link] == N
Soma(A) # vezes que o passo é executado
1 soma = A[1] 1
2 for i = 2 to [Link] (N – 2 + 1) + 1 = N
3 soma = soma + A[i] N-1
T(N) = c(1 + N + (N – 1))
T(N) = 2cN
4
Modelando o tempo de execução
Ordenação por inserção
Quantas vezes cada linha é executada?
5
Modelando o tempo de execução
Ordenação por inserção # vezes que o passo
é executado
(N – 2 + 1) + 1 = N
N-1
N-1
para cada j pode ser ≠
(# linha 5) - 1
# linha 6
N-1
Linha 5 é executada tj vezes para cada j
Linha 5 é executada t2 + t3 + ... + tN vezes
Linha 6 é executada (tj – 1) vezes para cada j
Linha 6 é executada (t2 -1) + (t3 -1) + ... + (tN -1) vezes
6
Modelando o tempo de execução
Ordenação por inserção # vezes que o passo
é executado
(N – 2 + 1) + 1 = N
N-1
N-1
para cada j pode ser ≠
(# linha 5) - 1
# linha 6
N-1
𝑁
Linha 5 é executada 𝑗=2 𝑡𝑗 vezes
𝑁
Linha 6 é executada 𝑗=2(𝑡𝑗 −1) vezes
𝑁
(𝑡𝑗 −1) = 𝑁
𝑗=2 𝑡𝑗 −
𝑁
𝑗=2 1 = 𝑁
𝑗=2 𝑡𝑗 − (𝑁 − 1)
𝑗=2 7
Modelando o tempo de execução
Ordenação por inserção # vezes que o passo
é executado
(N – 2 + 1) + 1 = N
N-1
N-1 𝑁
𝑡𝑗 𝑁
𝑗=2 𝑡𝑗 − (𝑁 − 1)
𝑁
𝑗=2
𝑡𝑗 − (𝑁 − 1)
𝑗=2
N-1
Somando tudo temos:
𝑁
𝑇 𝑁 = 𝑐(2𝑁 − 1 + 3 𝑡𝑗 )
𝑗=2
8
Modelando o tempo de execução
𝑁
𝑇 𝑁 = 𝑐(2𝑁 − 1 + 3 𝑡𝑗 )
𝑗=2
• Melhor caso: tj = 1
𝑁
𝑇 𝑁 = 𝑐 2𝑁 − 1 + 3 1 = 𝑐 2𝑁 − 1 + 3 𝑁 − 1
𝑗=2
𝑇 𝑁 = 𝑐(5𝑁 − 4)
9
Modelando o tempo de execução
𝑁
𝑇 𝑁 = 𝑐(2𝑁 − 1 + 3 𝑡𝑗 )
𝑗=2
• Pior caso: tj = j
𝑁
𝑁(𝑁 + 1)
𝑇 𝑁 = 𝑐(2𝑁 − 1 + 3 𝑗) = 𝑐(2𝑁 − 1 + 3 −1 )
2
𝑗=2
n(n 1)
j 2 j
n
1
2
𝑁2 + 𝑁 − 2 4𝑁 − 2 + 3𝑁 2 + 3𝑁 − 6
𝑇 𝑁 = 𝑐 2𝑁 − 1 + 3 = 𝑐
2 2
3𝑁 2 + 7𝑁 − 8
𝑇 𝑁 =𝑐
2
10
Modelo de análise
É importante saber exatamente qual é o modelo
(ou função) do tempo de execução?
Pior caso
𝑇 𝑁 = 𝑐(5𝑁 − 4)
3𝑁 2 + 7𝑁 − 8
𝑇 𝑁 =𝑐
2
Melhor caso
11
Notação assintótica
[Link]
12
PCS-3110
Algoritmos e Estrutura de Dados
para Engenharia Elétrica
Módulo 2: Análise de Algoritmos
vídeo 3 – Notação assintótica
Escola Politécnica da Universidade de São Paulo
Análise de algortimos
Modelamos o tempo de execução do Insertion-
Sort seguindo o modelo de análise do Knut.
• Melhor caso 𝑇 𝑛 = 𝑐 5𝑛 − 4
3𝑛2 + 7𝑛 − 8
• Pior caso 𝑇 𝑛 =𝑐
2
2
Análise de algoritmos
Se calcularmos o modelo de análise de
Selection-Sort teremos:
• Melhor caso: 𝑇 𝑛 = 𝑐 𝑛2 + 5𝑛 − 1
3𝑛2 + 9𝑛 + 4
• Pior caso: 𝑇 𝑛 =𝑐
2
3
Análise de algoritmos
Comportamento assintótico – taxa de crescimento
• Pior caso
Algoritmo de seleção
700
600
500 Algoritmo de inserção
400
Tempo
300
200
Outro algoritmo
100
0
0 5 10 15 20
Tamanho da Entrada (n)
4
Taxa de crescimento
Algumas ordens de crescimento comuns
1048576
Ordem de Nome
crescimento
65536
1 Constante
Complexidade
lgn Logarítmica
crescente
4096
n Linear
n*lgn Linearitmica
256
n2 Quadrática
16 n3 Cúbica
Constante 2n Exponencial
1
1 16 256 4096 65536 1048576 n! Fatorial
5
Notação assintótica
Representa como o tempo aumenta com o
tamanho da entrada no limite
• Lembra como calculava lim 𝑓 𝑛 ?
𝑛→∞
Ênfase na ordem de grandeza
• Abstrai constantes e fatores de menor ordem
• Forma simples de mostrar as características de
desempenho do algoritmo
Concisa e manipulável
Comparação simples
6
Notação assintótica
[Link]
7
Big-O
Sejam f(n) e g(n) duas funções, n ℕ
f(n) O(g(n)) se existem constantes positivas c e n0
tal que
0 ≤ f(n) ≤ c g(n)
para todo n ≥ n0
cg(n)
f(n)
n
n0
• f(n) é no máximo c g(n) para um n ≥ n0
8
Big-O
c g(n)
f(n) = O(g(n))
f(n)
n
n0
Exemplo
• Se o tempo de execução no pior caso de um algoritmo
é 1 n2 3n então ele é O(n2)
2
9
Big-O
Exemplo
• Se o tempo de execução no pior caso de um algoritmo
1 2
é n 3n então ele é O(n2)
2
• Observe que encontrar as constantes c e n0 que
safisfazem 0 ≤ f(n) ≤ c g(n) para todo n maior que n0 é
exatamente dizer que a função g(n) limita
superiormente a função f(n).
Neste caso, em particular, f(n) > 0 se n > 6. Mas e a constante c?
1 1
Como n > 6, teremos sempre que 𝑛2 − 3𝑛 < 𝑛2
2 2
Daí, n0 = 7 e c = ½ satisfazem a condição!
10
Big-O
Em geral se fala que f(n) = O(g(n)) ou f(n) é
O(g(n)) quando f(n) O(g(n))
É importante escolher a função mais próxima
possível
• Apesar de válido, é estranho dizer que f(n) = n =
O(n2) faz mais sentido dizer que é O(n)
11
Big-O
Algumas operações básicas
1. f(n) = O(f(n))
2. c * O(f(n)) = O(f(n))
3. O(f(n)) + O(f(n)) = O(f(n))
4. O(O(f(n))) = O(f(n))
5. O(f(n)) * O(g(n)) = O(f(n) * g(n))
6. O(f(n) * g(n)) = f(n) * O(g(n))
12
Big-Ω
Sejam f(n) e g(n) duas funções, n ℕ
f(n) Ω(g(n)) se existem constantes positivas c e n0
tal que
0 ≤ cg(n) ≤f(n)
para todo n ≥ n0
f(n)
cg(n)
n
n0
• f(n) é no mínimo cg(n) para um n ≥ n0
13
Big-Ω
f(n) = Ω(g(n))
f(n)
cg(n)
n
n0
Exemplo
• Se o tempo de execução no melhor caso de um
algoritmo é 6n - 3 então ele é Ω(n)
14
Big-Ω
Exemplo
• Se o tempo de execução no melhor caso de um
algoritmo é 6n - 3 então ele é Ω(n)
• Observe que encontrar as constantes c e n0 que
safisfazem 0 ≤ cg(n) ≤ f(n) para todo n maior que n0 é
exatamente dizer que a função g(n) limita
inferiormente a função f(n).
Neste caso, em particular, g(n) > 0 se n > 0. Mas e a constante c?
Como n > 0, podemos usar a seguinte estratégia:
1 1 3 𝑛=1
𝑐𝑛 < (6𝑛 − 3) → 𝑐𝑛 < (6𝑛 − 3) → 𝑐 < 6 − 𝑐 < 6−3
𝑛 𝑛 𝑛
Daí, n0 = 1 e c = 2 satisfazem a condição!
15
Big-Θ
Limita a função assintoticamente
• Limite assintótico firme
Sejam duas funções f(n) e g(n), com n ℕ
f(n) Θ(g(n)) se existem constantes positivas c1, c2 e n0 tal
que
0 ≤ c1g(n) ≤ f(n) ≤ c2g(n)
para todo n ≥ n0
• Ou seja, f(n) está limitada por g(n) para um n ≥ n0
16
Big-Θ
f(n) = Θ(g(n))
c2g(n)
f(n)
c1g(n)
n
n0
Exemplo
• Se o tempo de execução no pior caso de um
algoritmo é 1 n2 3n então ele é Θ(n2)
2
17
Big-Θ
Exemplo
• Se o tempo de execução no pior caso de um
1 2
algoritmo é 𝑛 − 3𝑛 então ele é Θ(n2)
2
• De fato, já vimos que se n > 6,
1 2 1 2
0≤ 𝑛 − 3𝑛 < 𝑛 ,
2 2
• Por outro lado, para calcular a outra constante c:
1 2 𝑛>0 1 1 1 2 1 3
c𝑛2 ≤ 𝑛 − 3𝑛 2
c 2 𝑛 ≤ 2 ( 𝑛 − 3𝑛) → c ≤ −
2 𝑛 𝑛 2 2 𝑛
𝑛>6 1 3 1
c≤ − =
2 7 14
18
Big-Θ
Exemplo
• Se o tempo de execução no pior caso de um
1 2
algoritmo é 𝑛 − 3𝑛 então ele é Θ(n2), pois,
2
para todo n > 6 vale:
1 2 1 2 1 2
𝑛 ≤ 𝑛 − 3𝑛 ≤ 𝑛
14 2 2
19
Big-Θ
Teorema
Para duas funções f(n) e g(n), temos que f(n) = Θ(g(n)) se
e somente se f(n) = O(g(n)) e f(n) = Ω(g(n))
f(n) = O(g(n)) f(n) = Ω(g(n)) f(n) = Θ(g(n))
c2g(n) c2g(n)
f(n) f(n) f(n)
c1g(n) c1g(n)
n n n
n0 n0 n0
20
Notação assintótica
Teorema
Seja p(n) i aini um polinômio com ad > 0
d
Então p(n) = Θ(nd)
21
Notação assintótica
Ao usar as notações O, Ω e Θ é necessário
dizer qual o caso: pior, melhor e médio
Em geral analisaremos o pior caso
• Define o limite superior para uma entrada
• Em alguns algoritmos, o pior caso é frequente
• O caso médio é similar ao pior caso
Para tratar do caso médio, é necessária uma análise
probabilística
22
Notação assintótica
É possível fazer algumas generalizações
• Se um algoritmo é no pior caso O(g(n)), então ele
será O(g(n)) para qualquer entrada
• Se um algoritmo é no melhor caso Ω(h(n)), então ele
é Ω(h(n)) para qualquer entrada
O(g(n))
Pior caso
Melhor caso
Ω(h(n))
23
Bibliografia
Cormen, T.; Leiserson, C.E.; Rivest, R.L.; Stein,
C. Introduction to Algorithms. The MIT Press, 3rd
ed. 2009. Seções 2.1 e 2.2
Feofiloff, P. Algoritmos em linguagem C.
Campus, 2009. Capítulos 7 e 8.
Auxiliar
• Sedgewick, R.; Wayne, K. Algorithms. Addison-
Wesley, 4th ed. 2011. Seção 1.4 e 2.1.
• Knuth, D. The Art of Computer Programming:
Fundamental Algorithms. Vol. 1. Addison-Wesley, 3rd
ed. 1998. Seção 1.2.10.
24