Aula11 Notacoes Assintoticas Bigo

Análise de Algoritmos
Aula - 11
Notações Assintóticas Big-O
Jefferson Magalhães de Morais

jeffersonmorais@gmail.com
26 de outubro de 2020
1 / 10
Notação assintótica Big-O
A figura abaixo apresenta as funções f (n) e g (n) onde
f (n) = O(g (n))
Para todos os valores de n à direita de de n0 , o valor de f (n)

está em ou abaixo de g (n)
2 / 10
A notação Big-O define o limite assintótico superior sobre

uma dada função f (n) tal que
0 ≤ f (n) ≤ c g (n), sempre que n ≥ n0 .
c e n0 são constantes positivas
Normalmente usada para limitar o tempo de execução do pior
caso de um algoritmo
Por exemplo, O(n2 ) é o limite no tempo de execução do pior
caso da odernação por inserção 3 / 10
Exemplo: sejam f (n) = n2 + 10 e g (n) = n3
Mostre que f (n) = O(g (n))
4 / 10
Como base na notação Big-O temos:

0 ≤ f (n) ≤ c g (n), sempre que n ≥ n0
Portanto temos que provar que:
0 ≤ n2 + 10 ≤ c n3 , sempre que n ≥ n0
Para isso temos que encontrar as constantes c e n0 que
satisfazem a inequação. Quais seriam esses valores?
5 / 10
Temos:
0 ≤ n2 + 10 ≤ c n3 , sempre que n ≥ n0
Se fixarmos o valor da constante c em 1 e variar o valor de n
em 2, 3, . . ., veremos que n2 + 10 ≤ n3 , para n ≥ 3. (c = 1 e
n0 = 3)
6 / 10
Temos:
0 ≤ n2 + 10 ≤ c n3 , sempre que n ≥ n0
n0 = 3)
c = 2 e n0 = 2 também seria uma solução?
6 / 10
Temos:
0 ≤ n2 + 10 ≤ c n3 , sempre que n ≥ n0
n0 = 3)
Mostre g (n) não é O(f (n))
6 / 10
Temos:
0 ≤ n2 + 10 ≤ c n3 , sempre que n ≥ n0
n0 = 3)
Mostre g (n) não é O(f (n))
É fácil provar que n3 jamais será menor ou igual a n2 + 10 para
valores elevados de n
6 / 10
Podemos dizer que n2 + 10 é O(n3 ), mas não ao contrário
7 / 10
Podemos dizer que 10 log2 n é O(n), mas o contrário não.
8 / 10
Podemos dizer que 10 log2 n é O(n)?
9 / 10
Podemos dizer que n2 é O(n!), mas não o contrário.
10 / 10

Aula11 Notacoes Assintoticas Bigo

Enviado por

Direitos autorais:

Formatos disponíveis

Aula11 Notacoes Assintoticas Bigo

Enviado por

Dados do documento

Título original

Direitos autorais

Formatos disponíveis

Compartilhar este documento

Compartilhar ou incorporar documento

Opções de compartilhamento

Você considera este documento útil?

Este conteúdo é inapropriado?

Direitos autorais:

Formatos disponíveis

Aula11 Notacoes Assintoticas Bigo

Enviado por

Direitos autorais:

Formatos disponíveis

Análise de Algoritmos

Jefferson Magalhães de Morais

Para todos os valores de n à direita de de n0 , o valor de f (n)

A notação Big-O define o limite assintótico superior sobre

Exemplo: sejam f (n) = n2 + 10 e g (n) = n3

Mostre que f (n) = O(g (n))

Exemplo: sejam f (n) = n2 + 10 e g (n) = n3

Mostre que f (n) = O(g (n))

Como base na notação Big-O temos:

Exemplo: sejam f (n) = n2 + 10 e g (n) = n3

Mostre que f (n) = O(g (n))

Exemplo: sejam f (n) = n2 + 10 e g (n) = n3

Mostre que f (n) = O(g (n))

Exemplo: sejam f (n) = n2 + 10 e g (n) = n3

Mostre que f (n) = O(g (n))

Exemplo: sejam f (n) = n2 + 10 e g (n) = n3

Mostre que f (n) = O(g (n))

Você também pode gostar