PAA-6-notacaoAssintotica

Prévia do material em texto

Profa. Thaís Alves Burity Rocha 
EFICIÊNCIA DE ALGORITMOS 
Agenda 
 Eficiência de algoritmos 
 
 Notação assintótica 
Introdução 
 Geralmente, um mesmo problema pode ser 
resolvido por diferentes algoritmos 
 
 Critérios para avaliar um algoritmo: 
 Corretude (aulas passadas) 
 
 Eficiência 
 
 Simplicidade 
 
Eficiência 
 Existem dois tipos de eficiência: 
 Eficiência temporal: indica o quão rápido o algoritmo 
é executado 
 
 Eficiência espacial: indica o espaço em memória 
necessário para a execução do algoritmo 
Eficiência 
 Antigamente, espaço em memória e tempo eram 
recursos valiosos 
 
 Atualmente, devido aos avanços nos mecanismos de 
armazenamento, o espaço em memória não é tão 
importante 
 
 No entanto, tempo continua sendo importante, pois 
problemas cada vez mais complexos são tratados 
Como avaliar a eficiência temporal? 
 Existem dois métodos: 
Método empírico: Implementar o algoritmo e medir o 
tempo de execução considerando-se entradas diversas 
 
Método analítico (análise assintótica): Definir o 
tempo de execução do algoritmo através de 
expressões matemáticas em termos do tamanho da 
entrada 
Desvantagens do método empírico 
 Esforço adicional de implementação do algoritmo 
 
 Podemos esquecer alguma entrada em que o 
desempenho é particularmente bom (ou ruim) 
 
 Os resultados dependem fortemente da tecnologia 
 Deve-se garantir o mesmo hardware e ambiente de 
software a fim de ser possível fazer comparação 
confiável entre algoritmos 
Análise assintótica 
 Ao contrário da abordagem experimental: 
 Usa uma descrição de alto nível dos algoritmos, ou 
seja, não requer esforço de implementação 
 
 Leva em consideração todas as possíveis entradas 
 Recursos matemáticos possibilitam generalizações 
 
 É independente do hardware e ambiente de software 
utilizado 
Tamanho da entrada 
 Quase todos os algoritmos levam mais tempo para 
serem executados sobre entradas maiores 
 
 Portanto, é essencial investigar a eficiência de 
algoritmos em função do parâmetro n, que indica o 
tamanho da entrada do algoritmo 
Tempo de execução 
 Eficiência temporal é analisada determinando o 
número de repetições de operações básicas em 
função do tamanho da entrada 
 Operação básica: operação que mais contribui 
para o tempo de execução de um algoritmo 
 
 
Mais sobre T(n) 
 C(n) e a constante cop são calculados por aproximação 
 C(n) não contém informações sobre operações não básicas 
 
 Assuma que para um dado algoritmo C(n) = ½ n(n-1). 
Quanto tempo levará a mais se dobrarmos o tamanho da 
entrada? 
 
 
 
 
 
 
 Válido somente para grandes valores de n 
 
 
Tempo de execução 
 Note que encontramos a resposta sem conhecer o 
valor de cop 
 
 A constante ½ também foi cancelada 
 
 Portanto, na análise da eficiência, ignoramos 
constantes multiplicativas e nos concentramos na 
ordem de crescimento da contagem da operação 
básica 
Tamanho da entrada e operações 
básicas 
Análise de algoritmos 
Ordens de crescimento 
 
 
 
 
 
 
 
 Note que funções logarítmicas crescem mais devagar, e 
funções exponenciais e fatoriais crescem mais rápido 
Crescimento de funções 
 A ordem de crescimento de um algoritmo permite: 
 Caracterização simples da eficiência de um algoritmo 
 
 Comparar a eficiência de diferentes algoritmos 
 
 Pode-se calcular o tempo exato de execução de um 
algoritmo, mas o esforço a mais não vale a pena 
Melhor caso, caso médio e pior caso 
 A maioria dos algoritmos não dependem apenas 
do tamanho da entrada, mas também das 
especificidades da entrada 
 Pior caso W(n): indica o maior tempo obtido, levando 
em consideração todas as entradas possíveis 
 Caso médio A(n): indica o tempo médio obtido, 
considerando todas as entradas possíveis 
Melhor caso B(n): indica o menor tempo obtido, 
levando em consideração todas as entradas possíveis 
Exemplo: Busca sequêncial 
 Problema: Dado um vetor de tamanho n e uma 
chave de busca com valor K, encontre o elemento 
de valor K, se presente 
 Algoritmo: 
 
 
 
 
 
 Pior caso? Caso médio? Melhor caso? 
Busca(A,n,K) 
 i=1 
 while(i ≤ n and A[i] != K) 
 i = i + 1 
 if (i≤n) 
 return i 
 else 
 return -1 
Notação assintótica 
 A análise da eficiência se concentra na ordem de 
crescimento do número de operações básicas de um 
algoritmo 
 Para comparar e classificar estas ordens de 
crescimento são utilizadas notações assintóticas 
 Objetivo: 
 Resumir o comportamento de um algoritmo em fórmulas 
simples e de fácil compreensão 
 Simplificar e descartar informações desnecessárias 
Eficiência assintótica 
 Maneira como o tempo de execução se comporta 
quando a entrada aumenta indefinidamente 
 
 Em geral, um algoritmo que é assintoticamente mais 
eficiente será a melhor escolha para todas as 
entradas (exceto para as muito pequenas) 
Notação Assintótica 
 Notação O (Big-O) 
 
 Notação Ω (Omega ou Big-Omega) 
 
 Notação Θ (Theta ou Big-Theta) 
 
Notação Big-O 
 Sejam duas funções 
f(n) e g(n) 
 f(n) está em O(g(n)) 
se existem constantes 
positivas c e n0 tais 
que f(n) ≤ c∙g(n) 
para n ≥ n0 
 
 Ou seja, f(n) não 
cresce mais do que 
g(n) 
 
Notação Big-O 
 Ao invés de “f(n) está em O(g(n))”, podemos 
dizer: 
 “f(n) é O(g(n))” 
 
 “f(n) ϵ O(g(n))” 
 
 “f(n) = O(g(n))” 
 
 Válido para as demais notações 
Notação Big-O 
 Exemplo: 2n + 10 é O(n) 
 2n + 10 ≤ c∙n 
 (c − 2) n ≥ 10 
 n ≥ 10/(c − 2) 
 
 Escolher c = 3 e n0 = 10 
 
 Certamente existem outras opções para c e n0, mas o 
importante é que existe alguma opção 
 
n0= 
Notação Big-O 
 A notação O coloca um limite superior no tempo de 
execução 
 
Notação Big-O 
 Exemplo: n2 não está 
em O(n) 
 n2 ≤ cn 
 n ≤ c 
 
 A desigualdade não 
pode ser satisfeita 
pois c deve ser uma 
constante 
Notação Big-O: Regras 
 Sejam d(n), e(n), f(n) e g(n) funções dos inteiros não-
negativos nos reais positivos. Então, as seguintes 
regras são válidas: 
Notação Big-O: Regras 
Notação Big-O: Regras 
Notação Big-O: Exemplos 
 f(n) = 10000n2 + 10000  f(n) = O(n2) 
 Regra 4: polinômio de grau 2 
 
 C=10.001 e n≥100 
 
 f(n) = 10000n2 + 10000  f(n) = O(n3) 
 Qualquer polinômio de grau superior à f(n) é limite superior para 
f(n) 
 C=1000 e n≥100 
 f(n) ≤ c g(n) 
 104 ∙ (102)2+ 104 ≤ 103 ∙ (102)3 
 104 ∙ 104+ 104 ≤ 103 ∙ 106 
 104 ∙ 104+ 104 ≤ 104 ∙ 105 
 104 + 1 ≤ 105 
 
 
 
 
Notação Big-O: Exemplos 
 f(n) = 6n3 + 4n + 9  f(n) = O(n3) 
 Regra 4: Polinômio de grau 3 
 C=7 e n≥3 
 
 f(n) = 3n + 5 log n + 2  f(n) = O(n) 
 Regra 2: 
 f1(n) = 3n + 2 e f2(n) = 5 log n = logn
5 
 f1(n) = O(n)  regra 4 
 f2(n) = O(logn)  regra 6 
 f1(n) + f2(n) = O(n + logn) = O(n) 
 C=4 e n≥64 
 
 f(n) = 450  f(n) = O(1) 
Notação Omega 
 A notação omega coloca um limite inferior no 
tempo de execução 
 
 f(n) está em Ω(g(n)) se existem constantes positivas c e 
n0 tais que c∙g(n) ≤ f(n) para n ≥ n0 
 
Ou seja, f(n) não decresce menos do que g(n) 
 
 
Notação Omega 
 A figura apresenta as funções f(n) e g(n), onde f(n) = 
Ω(g(n)) 
 
 
 
 
 
 
 
 Para todos os valores de n à direita de n0, o valor de 
f(n)está em ou acima de g(n) 
Notação Omega: Exemplo 
 Mostre que f(n) = 7n − 2 é Ω(n) 
 
 Para provarmos, precisamos apenas definir 
constantes c e n0 tais que 
 7n−2 ≥ c∙n, para todo n≥n0 
 
 Escolhendo c = 6 e n0 = 2, pode-se verificar que 
f(n) = Ω(n) 
 7n−2 = 6n+n−2 ≥ 6n para todo n ≥ 2 
Notação Theta 
 A notação Theta coloca um limite inferior e 
superior no tempo de execução 
 Sejam duas funções f(n) e g(n) 
 
 f(n) está em Θ(g(n)) se: f(n) está em O(g(n)) e f(n) 
está em Ω(g(n)) 
 
 Isto é, se existem constantes reais c1>0 e c2>0, e uma 
constante inteira n0 ≥1 tal que c2g(n) ≥ f(n) ≥ c1g(n), 
para n ≥ n0 
 A figura abaixo apresenta as funções f(n) e g(n), 
onde f(n) = Θ(g(n)) 
 
 
 
 
 
 
 
 
 Para todos os valores de n à direita de n0, o valor de f(n) 
reside em c1g(n) ou acima dele, e em c2g(n) ou abaixo 
deste valor 
 
Notação Theta 
Notação Theta: Exemplo 
 Mostre que f(n) = ½ n2 - 3n é Θ(n2) 
 
 Para provarmos, precisamos apenas definir 
constantes c1, c2 e n0 tais que 
 c2g(n) ≥ ½ n
2 - 3n ≥ c1g(n), para todo n ≥ n0 
 
 Escolhendo c1 = 1/14, c2 = 1/2 e n0 = 7, pode-se 
verificar que f(n) = Θ(n2) 
 73 ≥ 73 – 72 ∙6 ≥ 72 
Notação Theta, O e Omega 
Funções assintóticas básicas 
 Algumas funções ocorrem com muita frequência na 
análise de algoritmos, de tal forma que são usados 
termos especiais para se referir à complexidade 
delas 
 
 Por exemplo, o termo linear é usado para se referir 
à classe de funções que são O(n) 
Funções assintóticas básicas 
Notações utilizadas 
 lg n = log2n (Logaritmo binário) 
 ln n = logen (Logaritmo natural) 
 lgkn = (lg n)k (Exponenciação) 
 lg lg n = lg(lg n) (Composição) 
 
 Para todo a > 0, b > a, c > a e n real: 
 
Exemplo 
 Para entrada de tamanho n, a ordenação por 
inserção é executada em 8n2 etapas, enquanto que 
a ordenação por intercalação é executada em 
64nlgn etapas. 
 
 Qual é a complexidade destes algoritmos? 
 
 Para que valores de n a ordenação por inserção 
supera a ordenação por intercalação? 
 
Exemplo 
 Complexidade dos algoritmos: 
 Por inserção: O(n2) 
 
 Por intercalação: O(nlgn) 
Exemplo 
 A ordenação por inserção possui complexidade 
maior que a ordenação por intercalação se: 
Exemplo 
Resumo 
 Tanto eficiência temporal como espacial são 
medidas em função do tamanho da entrada 
 
 Eficiência temporal é medida contando o número 
de vezes em que cada operação básica é 
executada 
 
 A eficiência de dois algoritmos pode ser 
significativamente diferente para entrada de 
mesmo tamanho 
Resumo 
 É importante distinguir as eficiências de melhor 
caso, caso médio e pior caso 
 
 O interesse principal é na ordem de crescimento 
do algoritmo à medida que o tamanho da entrada 
cresce indefinidamente 
 
 As notações O, Ω e Θ são usadas para comparar o 
tempo de execução de dois algoritmos 
Resumo 
 Na prática, aplicamos a notação Ω para descrever 
um limite inferior para o melhor caso e a notação O 
para descrever um limite superior para o pior caso 
de um algoritmo 
 
 Quando o algoritmo não possui pior ou melhor 
caso, se aplica o uso da notação Θ 
Exercício 1 (exercício 3.1-4) 
 2n+1 = O(2n)? 
Exercício 1 (exercício 3.1-4) 
 2n+1 = O(2n)? 
 
 Resposta: 
 Se isso for verdade, existe c e n0 constantes positivas, 
tais que a seguinte relação é válida 
 2n+1 ≤ c 2n, para n > n0 
 
 C = 2 e n0=1 
 
 Conclusão: 2n+1 = O(2n) 
 
Exercício 2 (exercício 3.1-4) 
 22n = O(2n)? 
Exercício 2 (exercício 3.1-4) 
 22n = O(2n)? 
 
 Resposta: 
 Se isso for verdade, existe c e n0 constantes positivas, tais 
que a seguinte relação é válida 
 22n ≤ c 2n, para n > n0 
 
 Desenvolvendo a inequação, chegamos a situação de 2n ≤ 
c, que é inválida, dado que c tem que ser constante 
 
 Conclusão: 22n ≠ O(2n) 
 
Exercício 3 (exercício 3.1-3) 
 Explique porque a declaração “O tempo de 
execução no algoritmo A é no mínimo O(n2)” é 
isenta de significado 
Exercício 3 (exercício 3.1-3) 
 Explique porque a declaração “O tempo de 
execução no algoritmo A é no mínimo O(n2)” é 
isenta de significado 
 Resposta: 
 Seja T(n) o tempo de execução do algoritmo A 
 A afirmativa diz que T(n) ≥ O(n2) 
 Isso significa que T(n) ≥ f(n), sendo f(n) alguma função 
em O(n2) 
 Essa afirmativa não diz nada em relação à T(n), uma 
vez que a função g(n) = 0, para todo n, está em O(n2) 
Exercício 4 (exercício 2.2-1) 
 Expresse a função n3/1000 – 100n2 – 100n + 3 
em termos da notação theta (Θ) 
 
Exercício 4 (exercício 2.2-1) 
 Expresse a função n3/1000 – 100n2 – 100n + 3 
em termos da notação theta (Θ) 
 Resposta: Θ(n3) 
 
 c2g(n) ≥ 1/1000n
3 – 100n2 – 100n + 3 ≥ c1g(n), para 
todo n ≥ n0 
 n0 = 10
6, c1 = 10
-18 e c2 = 1 
 
Referência 
 CORMEN, T. H.; LEISERSON, C. E.; RIVEST, R. L.; 
STEIN, C. Algoritmos: Teoria e prática. Tradução da 
Segunda edição Americana. Editora Campus, 2002.