Cap. 2 Fundamentos da Análise de Eficiência

Prévia do material em texto

FUNDAMENTOS DA 
ANÁLISE DA EFICIÊNCIA 
DO ALGORITMO
Capítulo II
Análise de algorítimo
 Assuntos: 
◦ Correcto (exatidão),
◦ Eficiência de tempo,
◦ Eficiência de espaço
◦ Optimização
 Abordagens: 
◦ análise teórica
◦ análise empírica
Análise teórica da eficiência de tempo
 A eficiência do tempo é analisada através da 
determinação do número de repetições da 
operação básica do algoritmo em função do 
tamanho da entrada.
tamanho de 
entrada
tempo de execução
tempo de execução 
para a operação 
básica
nº de vezes que a operação 
básica é executada
Nota:
 Entrada:
◦ Dados fornecidos
 Tamanho de entrada
◦ pode ser dado como número de valores num vector, o 
número de registos num ficheiro, enfim, um certo 
número de elementos que constituem a entrada de 
dados para o algoritmo. De modo que o tempo de 
execução de um algoritmo pode ser dado como uma 
função T(n) do tamanho n da sua entrada. 
 Operação básica: 
◦ a operação que mais contribui para o tempo de 
execução do algoritmo.
Exemplos de tamanho da entrada e operação 
básica
Problema medida de tamanho da 
entrada
Operação Básica
busca de chave em uma 
lista de n itens
número de itens da lista, i. e. 
n
comparação de chave
Multiplicação de duas 
matrizes
A dimensão da matriz ou o nº 
total dos elementos
Multiplicação de dois 
números
problema de grafo típico Nº de vértice e/ou arcos Visita a vértice ou 
travessia nos arcos.
Análise empírica de eficiência de tempo
 Selecciona uma amostra específica (típico) de entradas
 Use unidade física de tempo (por exemplo, milissegundos) 
ou
 Contar número real de execuções da operação básica
 Analisar os dados empíricos
Melhor-caso, Caso médio e Pior-caso
Para alguns algoritmos eficiência depende de dados fornecidos:
 Pior caso: Cpior(n) – máximo sobre as entradas de tamanho n
 Melhor caso: Cmelhor(n) – mínimo sobre as entradas de 
tamanho n
 Caso médio: Cmedio(n) – "Média" com entradas de tamanho n
◦ Número de vezes que a operação básica será executada na 
entrada típica.
◦ Não a média de pior e melhor casos.
◦ Número esperado de operações básicas consideradas 
como uma variável aleatória sob alguma suposição sobre a 
distribuição de probabilidade de todas as entradas 
possíveis
Casos de Eficiências
 Anteriormente vimos que era importante analisar a eficiência de algoritmos 
como sendo uma função de parâmetro n, o tamanho de entrada. Existem 
muitos algoritmos que o seu tempo de execução depende não só do tamanho 
da entrada mas sim, um especifico valor de entrada.
 Ex: Considere o algoritmo de busca sequencial abaixo
alg 1.0
Claramente, o tempo de execução do algoritmo pode ser 
diferente para lista A[n] para mesma entrada n.
Algoritmo BuscaSequencial (A[0.. n–1], K)
// pesquisa um certo valor num dado vector usando busca sequencial
// Entrada: O vector A[0.. n–1] e a chave de busca K
// Saida: o indice do primeiro elemento de A iguail a chave K ou –1 se não for 
// encontrado elemento igual a chave K
i <– 0 
enquanto i <n E A[i] <> K faça i < - i + 1
Se i < n retorna i
Senão retorna –1
Casos de eficiência
 Como se pode observar no algoritmo 
anterior, o tempo de execução do 
algoritmo pode ser diferente para o 
mesmo tamanho da lista. 
Pior caso
 É o método mais fácil de se obter. Baseia-se 
no maior tempo de execução sobre todas 
as entradas de tamanho n.
 No algoritmo anterior, pode-se observar 
que o pior caso, acontece quando o 
elemento a pesquisar não existir ou se o 
mesmo se encontrar na última posição, o 
algoritmo faz todas comparações possíveis 
para todos valores de entrada de tamanho 
n: Cpior(n)=n.
Melhor Caso
 É o menor tempo de execução em uma 
entrada de tamanho n.
 Podemos analisar eficiencia do melhor caso 
como seguinte:
◦ Determinamos o valor do tamanho da entrada em 
que o contador C(n) é o menor para todos valores 
entrada de tamanho n. Isso, não quer dizer que o 
melhor caso seja o menor valor de n, isto é., para 
tamanho de entrada n o algoritmo executa mais 
rápido.
 No exemplo anterior, Cmelhor (n) = 1
Caso Médio
 Consideremos o caso do algoritmo da pesquisa 
sequencial alg1.0:
◦ A probabilidade de uma busca com sucesso é igual p
onde 0<p<1
◦ A probabilidade de sucesso ocorrer na i-ésima
posição da lista é igual para cada i.
◦ No caso da busca com sucesso, a probabilidade de 
sucesso ocorrer na i-ésima posição da lista é n/p
para cada i e o número de comparações feitas pelo 
algoritmo nesta situação é obviamente i.
◦ No caso de insucesso, o número de comparações é 
n com a probabilidade de (1 – p), assim:
Caso Médio
 Cmed(n) =[1(p/n) + 2 (p/n) + … + i(p/n) + … 
+ n(p/n)] + n(1 – p)
 =(p/n)[1 + 2 + … + i + … +n] + n(1 – p)
 =(p/n)[n(n + 1)/2] + n(1 – p)
 =p(n+1)/2 + n(1 – p) 
 Se p = 1 (sucesso) o número de 
comparações é (n+1)/2
 Se p = 0 (insucesso) – o número de 
comparações é n.
Formulas para contagem de operação básica
 Fórmula Exacta
C(n) = n(n–1)/2
 Fórmula que indica a ordem de crescimento 
com a constante multiplicativa específica
C(n) ≈ 0.5n2
 Fórmula que indica a ordem de crescimento 
com constante multiplicativa desconhecida.
C(n) ≈ c n2
Ordem de Crescimento
 Ordem de crescimento numa constante multipla 
quando n→∞
 Exemplo:
◦ Quanto mais rápido o algoritmo será executado 
no computador que é duas vezes mais rápido?
◦ Quanto tempo demora para resolver o 
problema de dobro tamanho de entrada?
Valores de algumas funções importantes 
quando n → ∞
n log2 n n n log2 n n
2 n3 2n n!
101 3,3 101 3,3*101 102 103 103 3,6*106
102 6,6 102 6,6*102 104 106 1,3*1030 9,3*10157
103 10 103 1,0*103 106 109
104 13 104 1,3*104 108 1012
105 17 105 1,7*105 1010 1015
106 20 106 2,0*106 1012 1018
Valores (alguns aproximado) de várias funções importantes para a análise de algoritmos.
Notação assintótica
 Na sessão anterior, a análise da eficiência 
concentrou-se na ordem de crescimento da 
contagem de operação básica do algoritmo 
como principal indicador da eficiência do 
algoritmo. Para comparar e eleger essas 
ordens de crescimento, usamos as seguintes 
notações: O(big oh ), (big omega),  (big
theta)
Ordem assintótica de crescimento
Uma maneira de comparar as funções que ignora 
factores constantes e pequenos tamanhos de 
entrada
 O(g(n)): classe de funções f(n), que não crescem 
mais rápido que g(n)
 Θ(g(n)): classe de funções f(n), que crescem a 
mesma ordem que g(n)
 (g(n)): classe de funções f(n), que crescem, pelo 
menos, tão rápido quanto g(n)
Notação Informal (Big Oh)
 O(g(n)) é um conjunto de todas funções com orden de 
crescimento menor ou igual que g(n) (para múltiplos de 
uma constante quando n tende a infinito)
 Ex.:
 nO(n2), 100n + 5 O(n2), (½)n(n–1) O(n2).
 n3O(n2), 0,00001n3O(n2), n4 +n + 1 O(n2).
Notação Informal (big Omega)
 (g(n)) é um conjunto de todas funções 
com ordem de crescimento maior ou igual 
que g(n). 
 Ex.
n3 (n2), ½ n(n–1) (n2)
mas 100n +5  (n2).
Notação Informal (Big tetha)
 (g(n)) é um conjunto de todas funções 
que tem a mesma ordem de crescimento 
que g(n).
 Exemplo
n3 (n3), ½ n(n–1) (n2)
mas 100n +5  (n2).
Notação 
Definição:
A função f(n)O(g(n)), se e somente se existe uma 
constante positiva c e um inteiro não negativo n0
para todo positivo n, tal que:
f(n)cg(n) para todo nn0
Ex. 100n+5  O(n2).
Prova:
100n+5 100n +n ( n5)
= 101n
 101n2
Pondo c = 101 e n0= 5, temos 100n+5  O(n
2)
Big-oh (O)
cg(n)f(n)
não 
importa
Fig. 2.1 A notação Big-oh f(n) O(g(n))
Notação 
Definição:
A função f(n)(g(n)), se e somente se existe 
uma constante positiva c e um inteiro não 
negativo n0 para todo positivo n, tal que:
f(n)  cg(n) para todo nn0
Ex. n3 (n2).
Prova: n3n2 para todo n 0,
Portanto podemos seleccionar c=1 e n0=0.
Big-omega ()
cg(n)
f(n)
não 
importa
Fig. 2.2A notação Big-omega f(n) (g(n))
Notação 
Definição
A função f(n)(g(n)), se e somente se 
existe uma constantes positiva c1 e c2 e um 
inteiro não negativo n0 para todo positivo 
n, tal que:
c1g(n) f(n)c2g(n) para todo nn0
Big-theta ()
c1g(n)
f(n)
não 
importa
Fig. 2.3 A notação Big-theta f(n) (g(n))
c2g(n)
Exemplo
(½)n(n-1)(n2) 
(½)n(n-1) = (½)n2 – (½)n  (1/2)n2 para todo n  0
(½)n(n-1)=(1/2)n2 – (1/2)n  ½)n2 – (½)n * (½)n
para todo n  2
=(¼) n2
Logo, pode-se seleccionar c2=¼ , c1=½ e 
n0=2
Propriedades
1. f(n) ∈ O(f(n))
2. f(n) ∈ O(g(n)) sse g(n) ∈(f(n))
3. Se f(n) ∈ O(g(n)) e g(n)∈O(h(n)), então f(n) 
∈O(h(n))
Nota semelhança com a ≤ b
1. Se f1(n) ∈ O(g1(n)) e f2(n) ∈ O(g2(n)) , então 
f1(n) + f2(n) ∈ O(max{g1(n), g2(n)})
Ordem de crescimento usando limites
 As definições de , e  indispensáveis 
para demonstração das propriedades 
abstractas, dificilmente são usadas para 
comparação de ordens de crescimento 
entre duas específicas. O método 
conveniente de o fazer é baseado no calculo 
de limite da razão de duas funções:
Ordem de crescimento usando limites
0 ordem de crescimento de t(n) < ordem de 
crescimento de g(n)
c > 0 ordem de crescimento t(n) = ordem de crescimento
de g(n)
∞ ordem de crescimento de t(n) > ordem de 
crescimento de g(n)
 Os dois primeiro casos significa que t(n)O(g(n)) e os dois últimos 
significa t(n)(g(n)) e o segundo caso implica que t(n)  (g(n))
 Exemplos:
◦ 10n vs. n2
◦ n(n+1)/2 vs. n2

)(
)(
lim
ng
nt
Exemplo
Compare a ordem de crescimento das 
seguintes funções (½)n(n–1) e n2.
Solução:
Como o limite é igual a um número 
positivo, então as duas funções tem a 
mesma ordem de crescimento, assim sendo,
(½)n(n–1)(n2)
Ordem de crescimento de algumas funções 
importantes
 Todas funções logaritmicas loga n pertencem a mesma
classe Θ(log n) não importa a sua base a > 1
 Todos polinómios do mesmo grau k pertencem a mesma
classe:
akn
k + ak-1n
k-1 + … + a0 ∈Θ(n
k)
 Funções exponencial an tem diferentes ordem de 
crescimento para diferentes valores da base a.
ordem log n < ordem nα (α>0) < ordem an < order n! < ordem nn
Classes de eficiência assintótica básicas
1 constante
log n logaritmica
n linear
n log n n-log-n
n2 Quadrática
n3 Cúbica
2n exponencial
n! factorial
Análise matemática para algoritmo não 
recursivos
Procedimento a seguir para o análise matemático do algoritmo não 
recursivo de algoritmo.
1. Encontre a variável que indica o tamanho de entrada.
2. Identifique a operação básica do algoritmo (normalmente 
isto encontra-se dentro do ciclo)
3. Verifique se o número de vezes que é executado a operação 
básica do algoritmo depende do tamanho de entrada. Se 
alem disso, isto depende também de uma outra propriedade, 
as eficiências do pior caso, o caso médio e se necessário, 
melhor caso devem ser analisadas em separado.
4. Construa o somatório expressando o numero de vezes a 
operação básica do algoritmo é executado.
5. Usando as formulas e regras de manipulação de somatórios, 
encontre uma forma próxima para a conta ou encontre a sua 
ordem de crescimento.
Exemplo 1: Elemento máximo
Algoritmo MaxElemento(A[0.. n–1])
//Determina o valor de maior elemento num dado vector
//Entrada: Um vector A[0.. n–1] de números reais
//Saida: O valor de maior elemento de A
maxval < - A[0]
para i <– 1 para n–1 faça
se A[i] > maxval
maxval <- A[i]
retorna maxval
 Medida do tamanho de entrada -?
 Operação Básica -? (operação realizada na maioria das vezes)
 Quantas vezes é a operação básica executado?
Exemplo2: Problema de Unicidade
Algoritmo Unicidade(A[0.. n–1])
//Determina se todos elementos de um dado vector são distintos
//Entrada: Um vector A[0.. n–1]
//Saida: Retorna “verdade” se todos elementos no vector A são 
//distintos e “falso” caso contrário
para i < - 1 para n – 2 faça
para j < - i+1 para n – 1 faça
se A[i] = A[j] retorna falso
retorna verdade
 Medida do tamanho de entrada -?
 Operação Básica -? (operação realizada na maioria das vezes)
 Quantas vezes é executada a operação básica?
Nota: são o pior caso e o melhor caso o mesmo?
Example 2 – Análise do pior caso
Dois casos - ambos igualmente ruim
1. Os dois últimos elementos são os únicos que são iguais
2. Não existem dois elementos iguais
Quantas comparações são feitas para cada um desses 
casos?
 
)(
222
)1(
1...)3()2()1(
)1(1)1()1(1)(
2
22
2
0
2
0
2
0
2
1
nO
nnnnn
nnn
ininn
n
i
n
i
n
i
n
ij
piorC






 








Exemplo 3: Multiplicação matricial
Algoritmo MultMatricial(A[0..n–1, 0..n–1], B[0..n–1, 0..n–1])
//Multiplica duas matrizes de ordem n usando a definição
//Entrada: Duas matrizes A e B de ordem n
//Saida: Matriz C=AB
para i < – 0 até n – 1 faça
para j < – 0 até n – 1 faça
para k < – 0 até n – 1 faça
C[i, j] < – C[i, j] + A[i, k] * B[k, j] 
return C
 Medida do tamanho de entrada -?
 Operação Básica -? (operação realizada na maioria das vezes)
 Quantas vezes é a operação básica executado?
Nota: são o pior caso e o melhor caso o mesmo?
Pior caso


















1
0
332
1
0
1
0
1
0
1
0
1
0
)()(
)(
1)(
n
i
n
i
n
j
n
i
n
j
n
k
nOnnnC
nnC
nC
Exemplo 4: Contagem de dígitos binários
Algoritmo Binário(n)
//Entrada: Um número positivo n
//Saída: A quantidade de digitos binário de n na sua representação 
binária.
cont < - 1 
enquanto n >1 faça
cont <- cont +1
n<- n/2
retorna cont
 Este algoritmo não pode ser investigado exactamente do mesmo modo 
dos exemplos anteriores são.
 Qual é a operação feita com mais frequência?
 Quantas vezes isso acontece (somatórios não se aplica aqui)
◦ n é dividido ao meio cada vez assim que deve acontecer cerca de log2n 
vezes
Plano de Análise de Algoritmos recursivos
 Decidir sobre um parâmetro que indica o tamanho de 
uma entrada.
 Identificar a operação básica do algoritmo.
 Verificar se o número de vezes que a operação básica é 
executada podem variar em diferentes entradas do 
mesmo tamanho. (Se for, os casos o pior, médio e 
melhor deve ser investigado separadamente.)
 Estabeleça uma relação de recorrência com uma 
condição inicial apropriado que expressa o número de 
vezes que a operação básica é executada.
 Resolver a recorrência (ou, pelo menos, estabelecer a 
ordem de crescimento da sua solução) usando o método 
de substituições por retrocesso ou outro método.
Exemplo 1: Avaliação recursiva de n!
 Definição: n ! = 1 ∗ 2 ∗ … ∗(n – 1) ∗ n para n ≥ 1 e 0! = 1
 Definição Recursiva de n!: 
◦ F(n) = F(n – 1) ∗ n para n ≥ 1 e
◦ F(0) = 1
Algoritmo Fact(n)
//Calcula recursivamente n!
//Entrada: Um não negativo inteiro n
//Saida: O factorial de n
Se n=0 retorna 1
Senão retorna Fact(n – 1) * n
Tamanho de entrada:___________
Operação básica:_______________________
Relação de recurrência:______________________________Resolver a recurrência para M(n)
M(n) = M(n – 1) + 1, 
M(0) = 0 //recurrence, condição inicial
Substituição por retrocesso
M(n) = M(n – 1) + 1
= [M(n – 2)+1]+1 = M(n – 2)+2
= [M(n – 3)+1]+2 = M(n – 3)+3
Veja um padrão?
M(n) = M(n –1)+1 = … = M(n – i)+i = … M(n – n)+n = n
Muito trabalho para a resposta óbvia – O(n)
Exemplo 2: A Torre de Hanói “enigma”
 Recorrência para o número de movimentos:
Exemplo 2: A Torre de Hanói “enigma”
Examplo 2: A Torre de Hanói “enigma”
 http://en.wikipedia.org/wiki/Tower_of_Hanoi
 http://www.cut-the-knot.org/recurrence/hanoi.shtml
 Solução Recursiva (Move n>1 discos de A para C)
◦ Move recursivamente n –1 discos de A para B (C é 
Auxiliar)
◦ Então move o maior disco de A para C
◦ Move recursivamente n –1 discos de B para C (A é 
Auxiliar)
 Análise Recursiva de Algoritmo
◦ M(n) = M(n –1) + 1 + M(n –1) para n>1 , M(1) = 1
◦ M(n) = 2M(n –1)+1, M(1) = 1
Resolver recorrência para o número de 
movimentos
M(n) = 2M(n-1) + 1, M(1) = 1
Use Substituição para trás.
M(n) = 2M(n-1)+1
=2[2M(n-2)+1]+1 = 22M(n-2)+2+1
=22[2M(n-3)+1]+2+1 = 23M(n-3)+22+2+1
Padrão
M(n) = 2iM(n-i)+2i-1+2i-2+…+2+1
= 2iM(n-i)+2i-1
Condição inicial: n=1 ou i = n-1
= 2n-1 algoritmo exponencial: ainda melhor
Exemplo 3: Contagem de nºde bits
Algoritmo BinRec
//Entrada: Um número inteiro positivo
//Saída: 
Se n = 1 retorna 1
Senão retorna BinRec(n/2) + 1
 Operação básica: adição
 Relação de recorrência:
A(n) = A( n/2) + 1 para n> 1, A(1) = 0
Problema: n / 2 faz com que a substituição por retrocesso não 
funcione quando n não é uma potência de 2
Estimado: apenas para casos em que n é uma potência de 2
Recorrência ligeiramente Actualizada
A(2k) = A(2k-1) + 1 para k>0, A(20) = 0
Usar a substituição por retrocesso
A(2k) = A(2k-1) + 1
= [A(2k-2) + 1]+1 = A(2k-2) + 2
= [A(2k-3) + 1]+2 = A(2k-3) + 3
…
= A(2k-i) + i
…
= A(2k-k) + k
Assim,
A(2k) = A(1) + k = k
n=2k e então k = log2n
A(n) = log2n = Θ(log n)
Números de Fibonacci
Consideremos a sequencia de números de Fibonacci: 
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, … definidos pela recorrência:
F(n) = F(n – 1) + F(n – 2) para n > 1 (1)
E duas condições iniciais
F(0) =0 e F(1) = 1. (2)
Os números de Fibonacci foram apresentados pelo Leonardo 
Fibonacci em 1202 como solução para o problema concernente 
ao tamanho da população de coelhos.
Fórmula explicita para n-ésimo número de 
Fibonacci
Para resolução do problema de Fibonacci teremos 
que usar o teorema que descreve a solução para 
equação linear homogénea de segunda ordem com 
coeficientes constante.
ax(n) + bx(n – 1) + cx(n – 2) = 0 (3)
Onde os coeficientes a, b e c são reais (a  0).
Seja dada a equação característica da recorrência (3)
ar2 + br + c = 0 (4)
Teorema 1
Sejam r1 e r2 duas raízes da equação características (4) da relação de recorrência (3). 
Assim temos os seguintes casos:
Caso 1: Se r1 e r2 são reais arbitrários, a solução geral da recorrência (3) é dada pela 
formula:
x(n) = r1
n +  r2
n onde  e  são constantes arbitrários
Caso 2: Se r1 e r2 são iguais entre si, a solução geral da recorrência (3) é dada pela 
fórmula:
x(n) =  rn + nrn onde r = r1 = r2 e  e  são constantes arbitrárias.
Caso 3: Se r1,2 = u  iv são complexos e distintos, a solução geral da equação (3) é 
dada pela fórmula:
x(n) =n[cos n + sen n]
Onde  = u2 + v2 ,  = arctan v/u e  e  são constantes arbitrárias
Apliquemos teorema 1 para resolver o problema de 
número de Fibonacci, para isso, temos que reescrever a 
equação (1) da seguinte maneira:
F(n) – F(n – 1) – F(n – 2) = 0 (5)
Sua equação característica da equação (5) é
r2 – r – 1 = 0
com raízes 
Como a equação característica tem duas raízes reais, 
usamos a fórmula indicada no caso 1
(6)
2
51
2
)1(411
2,1



r
nn
nF 






 







 

2
51
2
51
)( 
Para F(0) = 0, F(1) = 1, temos:

Resolvendo o sistema obtemos: =1/5 e = –1/5. Assim, 
substituindo esses valores na equação (6), temos:
Algoritmos para calculo de números Fibonacci
1. Algoritmo Recursivo
Algoritmo F(n)
…
se n<=1 então 
retorna n
senão 
retorna F(n–1) + F(n–2)
… 
Análise de eficiência deste 
algoritmo (TPC)
a) Para número de vezes é 
executada a operação básica
b) Para a função.
2. Algoritmo não recursivo
Algoritmo Fib(n)
…
F[0]=0;
F[1]1
para i de 2 até n passo 1 faça
F[i]  F[i–1] + F[i–2]
retorna F[n]
…
Análise de eficiência deste 
algoritmo (TPC)