Estruturas de Dados e Algoritmos
O que veremos nesta aula?
A relevância da eficiência dos algoritmos
Notação e Análise
Assintótica
Formalização da notação assintótica
Dalton Serey
Departamento de Sistemas e Computação
Universidade Federal de Campina Grande
Análise assintótica de algoritmos
© Dalton Serey DSC/UFCG
© Dalton Serey DSC/UFCG
Pra que algoritmos eficientes?
Por que fazer algoritmos eficientes?
“Se o algoritmo vai ser usado para pequenos
Suponha que você tenha no máximo 1000s para
problemas e por pequenos usuários... não há
porque se preocupar com eficiência.”
resolver certo problema... (+/-17 minutos)
Qual o maior problema que podemos resolver
nesse tempo se o algoritmo é T(n)?
“Se o algoritmo vai ser usado para resolver
T(n)
100n
5n^2
0.5n^3
2^n
grandes problemas, certamente será usado por
grandes usuários! Nesse caso, dá pra resolver o
problema da eficiência comprando hardware
mais rápido...”
1.000s
10
14
12
10
© Dalton Serey DSC/UFCG
© Dalton Serey DSC/UFCG
Por que fazer algoritmos eficientes?
Por que fazer algoritmos eficientes?
Podemos tratar problemas maiores se usarmos um
Eis a tabela com os dados
Por exemplo, qual passará a ser o maior problema
T(n)
100n
5n^2
0.5n^3
2^n
hardware mais rápido?
se usarmos uma máquina 10 vezes mais rápida?
Certamente, a máquina mais lenta resolveria o
mesmo problema em 10x o tempo disponível
em nosso exemplo, isso dá 10.000 segundos
© Dalton Serey DSC/UFCG
1.000s
10
14
12
10
10.000s
100
45
27
13
"!$#% & ' () *!+#+%, -+./ 0 1&2
© Dalton Serey DSC/UFCG
Por que fazer algoritmos eficientes?
Vejamos mais dados...
3 Que ganho tivemos com a mudança?
3 Tempos para problemas de vários tamanhos...
T(n)
100n
5n^2
0.5n^3
2^n
1.000s
10
14
12
10
10.000s
100
45
27
13
T(n)
1000 log n
100 n
5n^2
n^4/100
2^n/1000
Ganho
10.0
3.2
2.3
1.3
457689:57;<=> 8? @5BA/C D>5
<:E&F&5G&<G&6C 8? HI5@8GJ57K;<
LIMIN F&8&A8*=>8><? J&5AOC 8G&8
5
A ;<>P;<7Q MIMMIN ;<J:R STT T
10
3322
1000
500
100
1
25
4644
2500
3125
3906
33554
50
75
100
1000
10000
5644
6229
6644
9966
13288
5000
7500
10000 100000 1000000
12500 28125 50000 5000000 ###
62500 316406 1000000 ###
###
1.1E+12 3.8E+19 1.3E+27 1.1E+298
-
3 Assuma que cada unidade de tempo na tabela
acima corresponde a um milissegundo...
© Dalton Serey DSC/UFCG
Mais argumentos...
Notação Assintótica
3 Os tempos não são nada animadores...
T(n)
1000 log n
100 n
5n^2
n^4/100
2^n/1000
10.0
3.3
1.0
0.5
0.1
0
25.0
4.6
2.5
3.1
3.9
34
50.0
60.0
100
5.6
5.9
6.6
5.0
6.0
10.0
12.5
18.0
50.0
10m25s 21m36s 2h46m
>35anos >300séc
© Dalton Serey DSC/UFCG
3 Definimos O(g(n)) como o conjunto das funções
1000
10000
10.0
13.3
1m40s 16m40s
1h23m >3anos
>3anos >300séc
assintoticamente limitadas por g(n). Formalmente,
O g n U
V
f n : W c , n 0 X 0 : 0 Y f n Y cg n , Z n [ n 0 \
3 Usada para indicar limites assintóticos superiores.
3 Observe que na prática, escrevemos
f(n) = O(g(n))
para denotar que f(n) pertence a O(g(n))
© Dalton Serey DSC/UFCG
© Dalton Serey DSC/UFCG
Notação Assintótica
Notação Assintótica
3 Exemplos positivos:
] 5n + 2 = O(n), pois 5n + 2 <= n, para n > 0
] n = O(5n + 2), pois n <= (5n + 2)/5, para n > 0
] 3n2 + 5n = O(n2), pois 3n2 + 5n <= 3n2, para n > 5
3 Para encontrar c e n , devemos encontrar soluções
0
3 Exemplos negativos:
] 3n2 + 5n não é O(n), pois não há constantes positivas
c e n0 tais que 3n2 + 5n <= cn, a partir de n0
para a inequação obtida da definição...
3 Por exemplo,
] 3n2 + 5n <= cn2, para valores de n > n0
] pelos métodos convencionais, podemos verificar que
as soluções para a inequação são tais que
n >= 5/(c-3), para valores de c > 3
] logo, uma solução é c = 4 e n0 = 5
3 Exercício: prove o último resultado!
© Dalton Serey DSC/UFCG
© Dalton Serey DSC/UFCG
Notação Assintótica
Notação Assintótica
^ Se não houver soluções, então f(n) não é O(g(n)).
^ Definimos j
^ Por exemplo, não há solução para
_ 3n2 + 5n <= cn, para valores de n > n0
_ para se convencer disso, perceba que a derivada de
`
g n acb f n : d c , n 0 e 0 : 0 f cg n f f n , g n h n 0 i
^ Usada para indicar limites assintóticos inferiores
3n2 + 5n – cn é sempre positiva na faixa de valores
permitida...
^ É a definição complementar de O(g(n)).
^ Exemplo: 3n 2 k 5n l j n 2
_ logo, não é possível que 3n2 + 5n – cn <= 0, que é
equivalente à inequação dada...
^
g n como o conjunto das funções
inferiormente limitadas por g(n). Formalmente,
Portanto, 3n2 + 5n não é O(n)!
© Dalton Serey DSC/UFCG
Notação Assintótica
m Definimos n
g n como o conjunto das funções
para as quais g(n) é tanto limite superior quanto
limite inferior. Formalmente,
o
g n
pcq f n : f n p O g n e f n psr
g n
t
m É usada para indicar limites assintóticos estritos.
m Por exemplo, 2 k
3n 5n lvu n 2
© Dalton Serey DSC/UFCG
© Dalton Serey DSC/UFCG