Complexidade de Algoritmos
Professores: Alcides Calsavara e
Edson Scalabrin
Roberta Geneci Neves Weber
Rafael Coninck Teigão
Introdução

Eficácia

Eficiência
Introdução

Espaço

Tempo
Processo de Análise



Identificar o conjunto de entrada;
Identificar a operação base, que
será executada para cada elemento
da entrada;
Definir que tipo de entrada será
estudado.
Tipo de Entrada



Melhor Caso ( notação Ω )
Caso Médio ( notação θ )
Pior Caso ( notação O )
Caso Médio
Melhor Caso
Pior Caso

θ(n3) vs. O(2(n^n))
Principais Funções
Exemplo 1 - Não-Recursivos



K ETGUOPAMGLQZCVD
Busca seqüencial
PARA i = 1 até n FAÇA
SE e == vet[i] ENTÃO
pare;
FIM SE
FIM PARA
Resolver para o pior caso O(g(n))
Exemplo 1 - Não-Recursivo




Encontra-se f(n) pela simplificação do somatório
f(n) = n –1 +1
f(n) = n
g(n) para o pior caso é procurar um elemento
que está na última posição, então, g(n) = n
Exemplo 1 - Não-Recursivo



Satisfazer a equação que define O(g(n)) = O(n)
Sendo c = 1 e n0 =1
0≤1≤1
Exemplo 2 - Recursivos

Fatorial(n)
SE n == 0 ENTÃO
retorne 1;
SENÃO
retorne Fatorial(n - 1) * n;
FIM SE


T(n) = T(n-1) + constante
f(n) é a simplificação da Relação de Recorrência
Exemplo 2 - Recursivos


T(n) = T(n - 1) + 1
T(n) = 1
para n > 0
para n = 0
T(n) = T(n-1)+1 = T(n-2)+1+1 = T(n-3)+1+1+1 = · · ·
= T(n-n)+n = T(0)+n

Substituindo-se : T(n) = 1 + n = n

f(n) = T(n) = n
Exemplo 2 - Recursivos



g(n) = n para pior caso e caso médio
g(n) = 1 para o melhor caso
Prova é igual a do Exemplo 1
Métodos Especiais-Recursivos



Substituição
Árvore de Recursão
Mestre



T(n) = aT(n/b)+h(n)
a ≥ 1, b > 1 e h(n) > 0
compara-se nlogb a com h(n)
Conclusão


Ferramenta de análise
Melhoria de qualidade e eficiência
Referências Bibliográficas

[Koerich, 2005] Koerich, A. (2005).
Notas de aula.