Análise Algorítmica (Notação Assintótica)

04/24/23 EDA - Prof. Paulemir Campos 1

Análise Algorítmica(Notação Assintótica)

UPE – Caruaru – Sistemas de InformaçãoDisciplina: Estrutura de Dados e ArquivoProf.: Paulemir G. Campos


Comportamento Assintóticode Funções A análise de algoritmos para solucionar

um problema de tamanho n é realizada para valores grandes de n.

Para tanto, estuda-se o comportamento assintótico das funções de custo ou de complexidade do algoritmo.

O comportamento assintótico de f(n) representa o limite do custo quando n cresce.


Comportamento Assintóticode Funções Definição: Uma função f(n) domina

assintoticamente outra função g(n) se existem duas constantes positivas c e m tais que, para n m, temos

|g(n)| c.|f(n)|


Comportamento Assintóticode Funções Graficamente, temos:

f, g

m n

g(n)

c . f(n)


Comportamento Assintóticode Funções Exemplo: Seja g(n) = n e f(n) = -

n2, com n pertencente a Z+. Por definição, temos:

|g(n)| c.|f(n)|| n | c . |- n2 | n c . n2

Note que, fazendo c=1 e m=1, f(n) domina assintoticamente g(n).


Comportamento Assintóticode Funções

Graficamente, temos:

f, g

m = 1n

g(n) = n

|f(n)| = c . n2, com c=1


Notação Assintótica ou Notação O

Para expressar que f(n) domina assintoticamente g(n), Knuth (1968, p.104) sugeriu uma notação para essa dominação assintótica.

Assim, escrevemos g(n)=O(f(n)), onde se lê g(n) é da ordem no máximo f(n).



Exemplo: Se a complexidade de tempo de um

algoritmo é g(n)=O(n2), isto significa que existem constantes positivas c e m tais que, para valores de n maiores ou iguais a m, g(n) c. n2 , com n pertencente a Z+.


Notação Assintótica ou Notação O Definição: Uma função g(n) é

O(f(n)) se existem duas constantes positivas c e m tais que, para n m, temos

|g(n)| c.|f(n)|



Exemplo: Seja g(n) = (n+1)2, com n pertencente a Z+. Observe que g(n) é O(n2), quando m = 1 e c = 4, pois, por definição, temos:

|g(n)| c.|f(n)| | (n+1)2 | c . | n2 |

(n+1)2 c . n2 , com m = 1 (n+1)2 4 . n2, com n 1.


Operações com a Notação O Algumas delas são:

f(n) = O(f(n)) c . f(n) = O(f(n)), com c pertencente a

Z*+

O(f(n)) + O(f(n)) = O(f(n)) O(O(f(n))) = O(f(n)) O(f(n))+O(g(n)) = O(max(f(n),g(n))) O(f(n)).O(g(n)) = O(f(n).g(n)) f(n).O(g(n))=O(f(n).g(n))


Operações com a Notação OExemplos: Obtenha a complexidade de tempo

em notação O de alguns algoritmos dada pelas expressões matemáticas seguintes: O(n) + O(n2) + O(n . log n), com n>0= O(max(O(n),O(n2))) + O(n . log n)= O(n2) + O(n . log n)= O(max(O(n2),O(n . log n)))= O(n2), n>0.


Operações com a Notação O

Obtenção de O(max(O(n2

),O(n . log n))) graficamente.

f, g

n > 0

n

g(n) = n . log n

f(n) = n2


Operações com a Notação O [log n + k + O(1/n)] . [n + O(n)], com n>1 = n.log n + log n . O(n) + k.n + k. O(n) + + n . O(1/n) + O(1/n). O(n) = O(n.log n) + O(n . log n) + k.O(n) + k.O(n)

+ + O(n. 1/n) + O(1/n . n)= O(n.log n)+O(n . log n)

+k.O(max(O(n),O(n))) + + O(max(O(n. 1/n),O(n . 1/n)))= O(n.log n) + O(n . log n) + k.O(n) + O(n .

1/n)


Operações com a Notação O (Continuação)= O(n.log n) + O(n . log n) + k.O(n) + O(n .

1/n) Note que, com n>1, para qualquer valor de k,

com k>0, f(n) = k . n domina assintoticamente g(n) = n . 1/n. Assim, temos:

= O(n.log n) + O(n . log n) + k.O(n)= O(max(O(n.log n),O(n . log n))) + k.O(n)= O(n. log n) + k.O(n), n>1.


Operações com a Notação O (Continuação)= O(n. log n) + k.O(n), n>1.Obs.: Note que, com k=1, f(n) = n . log n dominaassintoticamente g(n) = k . n, com n 10.Por sua vez, com k=10, g(n) = k . n dominaassintoticamente f(n) = n . log n, com 1 < n <

1010.Portanto, devido a forte dependência do valor

de k,vamos deixar a resposta como mostrada

acima.


Operações com a Notação Of, g

n > 1

n

g(n) = n

f(n) = n

Obtenção de O(max(O(n),O(n))) graficamente.



n > 1n

f(n) = n . 1/n

Obtenção de O(max(O(n. 1/n), O(n . 1/n))) graficamente. g(n) = n . 1/n



n > 1n

f(n) = n . log n Obtenção de O(max(O(n.log n), O(n . log n))) graficamente. g(n) = n . log n


Operações com a Notação O Análise gráfica

de O(n. log n) e k.O(n), n>1 e k=1.

Neste caso, temos g(n) = k . n (k=1) dominando assintoticamente f(n) = n . log n, para 1 < n < 10.

f, gn = 10

n

g(n) = k . n, com k=1

f(n) = n . log n


Constantes Multiplicativas versus Notação Assintótica

Por questão de simplificação, na obtenção de uma notação assintótica, deve-se desprezar constantes e adições.

Geralmente por isso, a notação assintótica não serve para comparar dois algoritmos, mas sim, nos fornece uma idéia da complexidade de execução de um em relação ao outro.


Exemplo:

Um algoritmo F possui complexidade de tempo f(n) = 100 . n, isto é, O(n) e um outro algoritmo G é dado por g(n) = 2.n2, ou seja, O(n2). Qual desses dois algoritmos é melhor para resolver um problema de tamanho n?



Resposta: Depende! Note que para valores menores

do que 50 (n<50), o algoritmo G [O(n2)] é melhor, g(n) = 2.n2 (É dominado assintoticamente por f(n) = 100.n).

Por outro lado, para valores maiores ou iguais a 50 (n 50), o algoritmo F [O(n)] é melhor, f(n) = 100.n (É dominado assintoticamente por g(n)= 2.n2).



Classes de Comportamento Assintótico

As principais classes de problemas possuem as seguintes funções de complexidade: f(n)=O(1): São algoritmos de

complexidade constante. O uso desses algoritmos independem do tamanho de n. Neste caso, as instruções do algoritmo são executadas um número fixo de vezes.



f(n)=O(log n): São algoritmos de complexidade logarítmica. Este tempo de execução ocorre tipicamente em algoritmos que resolvem um problema transformando-o em problemas menores.

f(n)=O(n): São algoritmos de complexidade linear. Em geral, um pequeno trabalho é realizado sobre cada elemento de entrada.



f(n)=O(n .log n): Este tempo de execução ocorre tipicamente em algoritmos que resolvem um problema quebrando-o em problemas menores, resolvendo cada um deles independentemente e depois junta-se as soluções.

f(n)=O(n2): São algoritmos de complexidade quadrática. Geralmente isto ocorre quando há processamento com um laço dentro do outro. São úteis quando n é relativamente pequeno.



f(n)=O(n3): São algoritmos de complexidade cúbica. Úteis apenas para resolver pequenos problemas.

f(n)=O(2n): São algoritmos de complexidade exponencial. Tais algoritmos geralmente não são úteis para resolver problemas do ponto de vista prático. Ocorrem em problemas quando se usa “força bruta” para resolvê-los.



Sobre classes de comportamento assintótico destacam-se: f(n)=O(cn), c>1: Algoritmos com essa

função de complexidade são chamados de algoritmos exponenciais no tempo de execução.

f(n)=O(p(n)), p(n) é um polinômio: Já algoritmos cuja função de complexidade é um polinômio são conhecidos por algoritmos polinomiais no tempo de execução.



Algoritmos Exponenciais Quando o tamanho de n é grande,

tornam-se bastante ineficientes na prática;

São geralmente simples variações de pesquisa exaustiva;

Problemas solucionados apenas por tais algoritmos são considerados intratáveis, isto é, não existe solução por algoritmo polinomial.



Algoritmos Polinomiais Quando o tamanho de n é grande,

tornam-se muito úteis na prática; São geralmente obtidos através de um

entendimento mais profundo da estrutura do problema;

Apresentam boa solução, isto é, um problema é considerado bem resolvido quando existe um algoritmo polinomial para resolvê-lo.


Comparação entre Funções de Complexidade

Funçãode

Custon=10 n=20 n=30 n=40 n=50 n=60

n 10-5 s 2.10-5 s 3.10-5 s 4.10-5 s 5.10-5 s 6.10-5 sn2 10-4 s 4.10-4 s 9.10-4 s 16.10-4 s 25.10-4 s 36.10-4 s

n3 10-3 s 8.10-3 s 27.10-3 s 64.10-3 s 125.10-3 s 216.10-3 sn5 0,1 s 3,2 s 24,3 s 1,7 min 5,2 min 13 min2n 10-3 s 1 s 17,9 min 12,7 dias 35,7 anos 366 séc.3n 59.10-3 s 58 min 6,5 anos 3855 séc. 108 séc. 1013 séc.

Segundo Garey e Johnson (1979, pág. 7), temos:

OBS.: Um algoritmo linear executa em 1s um milhão de operações.


Técnicas de Análise de Algoritmos Determinar a ordem de tempo de

execução de um algoritmo (notação O) é em geral mais simples do que encontrar a expressão matemática exata da função de complexidade.


Técnicas de Análise de Algoritmos Tentando tornar mais simples a tarefa de

obter tal expressão matemática, Aho, Hopcroft e Ullman (1983) enumeraram alguns princípios a serem seguidos: 1. Operação de atribuição, leitura ou escrita

são consideradas como O(1). Exceções: Chamada de função em comando de

atribuição e atribuições que envolvem vetores de tamanho arbitrariamente grandes.


Técnicas de Análise de Algoritmos

2. O tempo de execução de uma seqüência de comandos é determinado pelo maior tempo de execução de qualquer comando dessa seqüência (operação dominante).

3. O tempo de execução de um comando de decisão é composto pelo tempo de execução dos comandos executados dentro do comando condicional mais o tempo para avaliar a condição, que é O(1).



4. O tempo para executar um laço é a soma do tempo de execução do corpo do laço mais o tempo de avaliar a condição de parada (geralmente é O(1)), multiplicado pelo número de iterações do laço.

5. Quando o algoritmo possui procedimentos não recursivos, o tempo de execução de cada procedimento deve ser computado separadamente um a um, iniciando com os procedimentos que não chamam outros procedimentos.



5. (Continuação) Depois, avalia-se os procedimentos que chamam os procedimentos que não chamam outros procedimentos, utilizando os tempos dos procedimentos já avaliados. Este processo é repetido até chegar no algoritmo principal.



6. Quando o algoritmo possui procedimentos recursivos, para cada procedimento é associada uma função de complexidade f(n) desconhecida, onde n mede o tamanho dos argumentos para o procedimento. Outra opção é determinar o número total de chamadas recursivas, calcular a complexidade de uma dessas chamadas recursivas (sem considerar outras chamadas), e efetuar esse produto.


Técnicas de Análise de Algoritmos Exemplo: Obtenha a função de

complexidade de tempo e também em notação O do algoritmo abaixo:inteiro Fatorial(inteiro i){ // i 0

se i=<1 então retorne (1)senão retorne (i * Fatorial(i-1))

}



Resposta: a) Obtenção da função de complexidade de

tempo.- Esse procedimento recursivo é chamado n

vezes;- A complexidade de uma chamada é

constante, isto é, O(1). Pois, para n 1, apenas uma atribuição é executada; e para n > 1 apenas um produto é efetuado.



Resposta:a) (Continuação)- Logo, temos um produto de n por 1. Assim,

f(n)=n é a função de complexidade de tempo desse algoritmo recursivo.

b) Como f(n) = n é a função de complexidade de tempo desse algoritmo, então, trata-se de um algoritmo polinomial de ordem O(n).


Referências Bibliográficas Ziviani, N. Projeto de

Algoritmos: Com implementações em Pascal e C. São Paulo: Pioneira, 5a. ed., 1999.

Szwarcfiter, J. L.; Markenzon, L. Estruturas de Dados e seus Algoritmos. Rio de Janeiro: LTC, 2a. ed., 1994.

Documents

Análise Algorítmica (Notação Assintótica)