Aula 6 Comportamento Assint Tico De Fun Es

Centro Universitário de Araraquara –
UNIARA
Departamento de Ciências da Administração e Tecnologia
Curso de Engenharia de Computação e Sistemas de Informação

PROJETO E ANÁLISE DE
ALGORITMOS
Prof. Msc. José Eduardo Ribeiro

Sumário
Notação Ω
Notação Ө
Notação o

Notação Ω
Conceitos
Da mesma maneira que a notação O fornece um limite assintótico superior sobre uma função, a notação Ω fornece um limite assintótico inferior.
Para uma determinada função g(n), denotamos por
Ω(g(n)) (lê-se “ômega maiúsculo de g de n" ou, as vezes,
“ômega de g de n”).

Notação Ω
Definição
Uma função f(n) é Ωg(n) se existirem duas tais que f(n) >= c*g(n), constantes c e m ou para todo n >= (m ou ).

Notação Ω
Exemplo:
Para mostrar que f(n) = 3n3 + 2n2 é Ω(n3), basta fazer c
= 1, e então 3n3 + 2n2 >= n3 para n >= 0.
A figura ao lado mostra para todos os valores que estão à direita de , o valor de f(n) está sobre ou acima do valor de c*g(n).

Notação Ω
Comparação: Notação O e Notação Ω :

Definição
Considerando-se que a notação Ω descreve um limite inferior, quando a usamos para limitar o tempo de execução do melhor caso de um algoritmo. Por exemplo, o tempo de execução no melhor caso da ordenação por inserção (InsertionSort) é Ω(n), o que implica que o tempo de execução da ordenação por inserção é Ω(n).

Definição
Assim, o tempo de execução da ordenação por inserção recai entre Ω(n) e O(n2), pois ele fica em qualquer lugar entre uma função linear de n e uma função quadrática de n.

Notação Ө (Theta)
Conceitos
Para uma dada função f(n), denotamos por Ө(g(n)) o conjunto de funções:
Ө(g(n))
f(n) : existem constantes positivas , tais que
0 <= *g(n) <= f(n) <= *g(n) para todo n >=

.

Uma função f(n) pertence ao conjunto Ө(g(n)) se existem constantes positivas tais que ela possa ser "imprensada" entre *g(n) e *g(n), para um valor de n suficientemente grande.

Notação Ө (Theta)
Conceitos
Como Ө(g(n)) é um conjunto, poderíamos escrever "f(n) pertence a Ө(g(n))" para indicar que f(n)