Aula 1 Análise de Algoritmo

Prévia do material em texto

1 
Análise
de
Algoritmos

Rohit
Gheyi

rohit@dsc.ufcg.edu.br

• 1 • 2 
A
eficiência
de
um

algoritmo
é
relevante?

Exemplo
1:
Supermercado

• 3 
Exemplo
2:
Avião

• 4 
Outras
CaracterísHcas


•  Que
outras
caracterísHcas
são
mais

importantes
que
eficiência?

– Corretude

– Modularidade

– Usabilidade

– Simplicidade

– Estensabilidade

– Manutenabilidade

• 5 
Por
que
Estudar
Eficiência?

•  Os
algoritmos
ajudam
a
estudar
a
escalabilidade

•  A
eficiência
geralmente
descreve
a
linha
entre:

–  Tratável,
intratável,
insolúvel

•  É
a
“moeda”
da
computação

•  Qual
é
o
melhor
algoritmo
para
a
solução
de
um

problema?

• 6 
Complexidade X Eficiência 
2 
Exercício


•  Como
saber
se
um
dado
anel
é
de
ouro
puro?

• 7 • 8 
Como
comparar
a
eficiência

de
dois
algoritmos?

Abordagem
Experimental

•  Executar
os
dois
algoritmos

– Medir
o
tempo

• 9 
public static int arrayMax(int[] A) { .. } 
long antes = System.nanoTime(); 
int x = arrayMax(new int [] {4,5,6,1}); 
long depois = System.nanoTime(); 
long tempo = depois – antes; 
Gráfico

• 10 
1 
1 
1 
1 
1 
11111111 
t (ms) 
n 
Algoritmo 1 
Tamanho 
da entrada 
+- 50 
medições 
• 11 
Quais
fatores


influenciam?

Fatores

•  Tamanho
da
entrada
(n)

•  Hardware

– Processador

– Memória

•  So^ware

– Sistema
Operacional

– Linguagem
de
Programação

– Compilador

• 12 
C/C++ 
3 
Limitações
(Experimento)

•  Os
experimentos
são
realizados
em
um

número
limitado
de
testes.

– Os
dados
podem
não
indicar
a
tendência
dos

valores
não
testados

•  Os
dois
algoritmos
devem
ser
testados
no

mesmo
ambiente
(hardware
e
so^ware)

•  Para
analisar
o
tempo
de
execução,

precisamos
executar
o
algoritmo

• 13 • 14 
Quais
as

limitações?

• 15 
Propor
uma
metodologia


para
analisar
o
tempo
de


execução
dos
algoritmos

Metas

•  Considerar
todas
as
entradas

•  Analisar
algoritmos
independentemente
de

hardware
e
so^ware

•  Avaliar
sem
precisar
rodar
experimentos

• 16 
• 17 
Analisar
o
algoritmo
em


alto
nível
(pseudocódigo)

O
que
iremos
fazer?
Intuição

• 18 
public boolean XYZ(int n, …) { 
 … 
 … 
} 
f(n) 
Algoritmos 
Matemática Análises 
4 
Considerações

•  O
tempo
de
execução
de
cada
operação

primiHva
depende
do
hardware
e
so^ware,

mas
de
todo
modo
é
constante

•  Hipótese

• 19 
O tempo de cada operação 
primitiva é praticamente o mesmo 
Operações
PrimiHvas

•  Atribuição:
a
=
x

•  Operação
aritméHca:
a+1

•  Comparação
de
números:
a>b

•  Indexar
array:
a[i]

•  Retorno
de
método:
return
x;

• 20 
Custo unitário 
Custo
das
Operações

•  Instruções
ConsecuHvas

•  If
then
else

• 21 
Cmd1; 
Cmd2; custo(Cmd1) + custo(Cmd2) 
if (teste) { 
 ... // CustoIf 
} else { 
 ... // CustoElse 
} 
custo(teste) + max[custo(if),custo(else)] 
Custo
de
outras
Operações

•  Laço

•  Aninhamento
de
Laços

–  tempo
do
laço
interno
x
tempo
do
laço
externo

•  Recursão

– Mais
complexo

– Veremos
dois
métodos
(iteraHvo
e
mestre)

• 22 
for (...) { 
 ... // CustoFor 
} 
n * custoFor 
Número de Iterações 
Exercício
1

•  Qual
o
número
de
primiHvas
do
algoritmo
a

seguir?

• 23 
public int max(int x, int y) { 
 if (x > y) 
 return x; 
 else return y; 
} 
Exercício
2

•  Qual
o
número
de
primiHvas
do
algoritmo
a

seguir?

• 24 
long potencia(int n) { 
 long r = 1; 
 for (int i=1; i<=n; i++) 
 r=2*r; 
 return r; 
} 
5 
Exercício
3

•  Qual
o
número
de
primiHvas
do
algoritmo
a

seguir?

• 25 
public static int arrayMax(int[] A) { 
 int maximo = A[0]; 
 for(int i=1;i<A.length;i++) 
 if(maximo<A[i]) 
 maximo = A[i]; 
 return maximo; 
} 
1 1 
1 
2n 2(n-1) 
2(n-1) 
2(n-1) – pior 
0 – melhor 
Pior caso: 1+1+1+2n+2(n-1)+2(n-1)+2(n-1)+1 = 8n-3 
Melhor caso: 1+1+1+2n+2(n-1)+2(n-1)+1 = 6n-1 
1 
Tipos
de
Análises

• 26 
Pior caso 
Melhor caso Tempo médio 
  Que tal calcularmos o tempo médio? 
Melhor,
Pior
e
Caso
Médio

•  Pior
Caso


–  Mais
comum

–  T(n)
=
tempo
máximo
para
um
algoritmo
com
qualquer
entrada
de

tamanho
n

–  Fácil
de
calcular
(sem
probabilidade)

•  Caso
Médio

–  T(n)
=
tempo
esperado
sobre
todas
as
entradas
de
tamanho
n

–  Precisa
de
uma
hipótese
da
distribuição
estaksHca
das
entradas

•  Melhor
Caso

–  Não
acrescenta
muita
informação

–  Raramente
ocorre
na
práHca

•  Logo,
não
é
uma
boa
medida

• 27 
Exercício
4

•  Qual
o
número

de
operações

primiHvas
em

cada
algoritmo?

• 28 
boolean primo(int n) { 
 if (n==2) return true; 
 for (int i=2; i<n; i++) 
 if (n%i==0) 
 return false; 
 return true; 
} 
boolean primo(int n) { 
 if (n==2) return true; 
 for (int i=2; i<=n/2; i++) 
 if (n%i==0) 
 return false; 
 return true; 
}