An Lise E Complexidade Dos Algoritmos

FACULDADE ANHANGUERA DE CASCAVEL
CIÊNCIAS DA COMPUTAÇÃO - 7º PERÍODO

ANALISE E COMPLEXIDADE DE
ALGORITMOS

Acadêmico:

ATPS
Etapa 1

Cascavel 2015.
PASSOS

Passo 1 (Aluno)
Ler o Capítulo 1 – “Introdução”: Seção 1.3; subseções 1.3.1, 1.3.2, do livro do Ziviani (2005).

Passo 2 (Equipe)
Definir, de acordo com o texto lido no passo 1, as medidas de complexidade Ômicron ( ), Ômega ( ) e Theta ( ).

Introdução

Custo Assintótico de Funções

O custo assintótico de uma função f(n) representa o limite do comportamento de custo quando n cresce. Geralmente, um algoritmo que é assintoticamente mais eficiente será a melhor escolha para valores grandes de n.

Dominação Assintótica

Definição: f(n) domina assintoticamente g(n) se existem duas constantes positivas c e m tais que, para n >= m, temos |g(n)| <= c.|f(n)| m n

Exemplo: Seja g(n) = n e f(n) = -n 2
Temos que |n| <= |-n 2 | para todo n ∈ N.
Fazendo c = 1 e m = 0 a definição é satisfeita. Logo, f(n) domina assintoticamente g(n)

Notação O

Notação trazida da matemática por Knuth (1968): g(n) = O(f(n))

A medida de complexidade Ômicron, considerada o pior caso, é representado pela letra grega 0 e baseia-se no maior tempo de execução entre todas as entradas.
Ex.: O algoritmo de pesquisa sequencial em um vetor tem complexidade f(n) = O(n).

Entende-se:

- g(n) é de ordem no máximo f(n)
- f(n) domina assintoticamente g(n)
- (f(n) é um limite assintótico superior para g(n))
- O(f(n)) representa o conjunto de todas as funções que são assintoticamente dominadas por uma dada função f(n).

Se g(n) ∈ O(f(n)) então g(n) = O(f(n))

Se dizemos que g(n) = O(n ² )

Significa que existem constantes c e m | g(n) <= c. n 2 para n >= m

Exemplo:

N
(N+1)²
2n²
0
1
0
3
4
2
4
9
8
3
16
18

Notação Ω

A medida de complexidade ômega, representada pela letra grega Ω, refere-se ao melhor caso, onde exprime o menor tempo de execução de um algoritmo para uma entrada n.
Ex.: O algoritmo de pesquisa