Notacao Assintotica

Notao AssintticaFREN L. SOUZA

EFREN L. SOUZA / TEORIA DOS GRAFOS / UFOPA IEG PC 1

Roteiro

1. Ordem de Crescimento

2. Notao Assinttica

3. Calculando a Complexidade

4. Bibliografia


Ordem de Crescimento


Abstraes simplificadores

Calcular a quantidade exata de operaes de um algoritmo muito trabalhoso e contm detalhes que no so to necessrios

At o momento simplificamos a anlise de algoritmos com Ignorando o custo real de cada instruo (usando constantes abstratas )

Ignoramos tambm esses custos constantes abstratos O tempo de execuo a2 + + para constantes , e que dependem dos custos


Ordem de crescimentoOrdem de crescimento o tempo de execuo que realmente interessa

Considera apenas o termo de mais alta ordemNa formula a2 + + , apenas o termo 2 selecionado, pois os de mais

baixa ordem so insignificantes para grandes valores de

Tambm ignoramos o coeficiente constante desse termo, ficando apenas 2, pois ele menos significativo na eficincia computacional


Eficincia

Consideramos um algoritmos mais eficiente quando seu tempo de execuo no pior caso apresenta ordem de crescimento menor que do outro algoritmo

Essa avaliao pode ser incorreta para entradas pequenas

Porm, para entradas grandes um algoritmo de complexidade 2

executar mais rapidamente que um de complexidade 3


Eficincia assinttica

Quando observamos tamanhos de entrada grandes o suficiente para tornar relevante apenas a ordem de crescimento do seu tempo de execuo, estamos estudando a eficincia assinttica dos algoritmos

Estamos preocupados em como o tempo de execuo do algoritmos aumenta com o tamanho da entrada

Em geral, um algoritmo assintoticamente mais eficiente ser a melhor escolha


Notao Assinttica


Etimologia A palavra assinttica etimologicamente significa o que no cai junto, o que no coincide

Uma assntota de uma funo um limitante do qual a funo se aproxima mas jamais atingeExemplo clssico exemplo o valor zero para a funo 1 medida que cresce, se aproxima cada vez mais de zero, mas nunca o

atinge

Por extenso, o campo da Assinttica engloba tudo o que diz respeito ao comportamento de funes quando os valores do domnio tendem ao infinito


Tipos de notao assinttica

Existem alguns tipos de notao assinttica usados para simplificar a anlise de algoritmos

Notaes , , , ,

Essas notaes so usadas em termos de funes

So convenientes para descrever a funo do tempo de execuo (), que em geral definida sobre tamanhos de entrada inteiros


Notao

Para uma dada funo , denotamos por (()) o conjunto de funes = : 1, 2 0 0 1() 2 0}

Como um conjunto, podemos escrever , para indicar que um membro de

Podemos expressar a mesma coisa com =

Dizemos que um limite assintoticamente restrito para , i.e. limita uma funo acima e abaixo

A notao (1) indica uma funo constante


Usando a definio formal paraMostrar que

2

2+ 3 = 2 para todo 0

Pela definio 12 2

2+ 3 2

2

Simplificando, a diviso por 2 produz 1 1

2+3

2

A desigualdade esquerda vlida para qualquer valor 1 com 1 1

2 O menor valor de

1

2+3

obtido fazendo =

A desigualdade direita vlida para qualquer valor 1 com 2 7

2 O maior valor de

1

2+3

obtido fazendo = 1


Notao

Para uma dada funo , denotamos por O(()) o conjunto de funes

= : 0 0 0}

Usamos a notao para dar um limite assinttico superior

Temos um limite sobre o tempo de execuo de um algoritmo em cada entrada

O Insertion Sort tem complexidade No pior caso (2)

No melhor caso ()

No geral O(2)


Notao

Para uma dada funo , denotamos por (()) o conjunto de funes = :

0 0 () () 0}

Usamos a notao para dar um limite assinttico inferior

Geralmente utilizado para indicar o melhor casoO melhor caso do Insertion Sort ()

O Insertion Sort fica entre () e O(2)


Notao

O limite da notao pode ou no ser assintoticamente restritoO limite 22 = (2) assintoticamente restrito

O limite 2 = 2 no assintoticamente restrito

Usamos a notao para denotar um limite superior que no assintoticamente restrito

Definimos o( ) como o conjunto = { : > 0, 0 > 0 0 < 0}

As notaes e so semelhantes, mas2 = (2)

22 (2)


Notao

Por analogia, a notao est para assim como a notao est para

Definimos (()) como = { : > 0, 0 > 0 0 < () 0}

As notaes e so semelhantes, mas 2

2 =

2

2 (2)


Calculando a Complexidade


O algoritmo Selection Sort

public static void selectionSort( int v[] ) {

for( int i=0; i

Desenvolvendo


T n = =0

2

=+1

1

1 = =0

2

=1

1

1 = =0

2

)( 1

= 2 )( + 1

2 1 1

=2

2= ()

Provando que2

2

2= ()


2

2

2= 1, 2 0

0 12 2

2

2 2

2

1 1

21

2n, = 2 1

1

4

2 1

21

2n, = 2

1

2

,2

2

2= 1

1

4, 2 1

2 0 2

BibliografiaThomas, T. H.; Leiserson, C. E.; Rivest, R. L.;Stein, C. Algoritmos: teoria e prtica. Rio deJaneiro: Campus, 2012.

Szwarcfiter, Jayme. Grafos e AlgoritmosComputacionais, Campus, Rio de Janeiro, 1984.

Boaventura, P.O. Grafos Teoria, Modelos eAlgoritmos. 5a edio. Edgard Blucher, 2012.


Documents

Notacao Assintotica