Complexidade de Computação
Katia Guimarães
Avaliando a Qualidade de um
Algoritmo
• É preciso ter bem definido
– O que é dado de entrada e
– O que é esperado na saída
• Dado que o algoritmo resolve CORRETAMENTE
o problema,
Quanto recurso ele gasta (espaço e tempo) ?
Como calcular o tempo de execução de
um algoritmo?
• Métodos Empíricos - Obtemos o tempo de
execução através da execução propriamente
dita do algoritmo, considerando-se entradas
diversas.
• Métodos Analíticos - Obtemos uma ordem de
grandeza do tempo execução através de
expressões matemáticas que traduzam o
comportamento do algoritmo.
Métodos Empíricos
Obtemos o tempo de execução através da execução
propriamente dita do algoritmo, considerando
entradas diversas.
Problemas:
1. Não temos tempo suficiente para rodar todas
as possíveis instâncias de todos os tamanhos.
2. Depende diretamente do equipamento sendo
usado para avaliação.
Métodos Analíticos
Obtemos uma ordem de grandeza do tempo
execução através de expressões matemáticas que
traduzam o comportamento do algoritmo.
Problemas:
1. Definir que variáveis usar nas expressões
matemáticas
2. Analisar o comportamento do algoritmo
para possíveis cenários.
Métodos Analíticos
Que variáveis usamos nestas expressões matemáticas ?
Resp.: Tamanho da entrada (depende do problema).
Exemplos
Ordenação: Número de itens da entrada (tamanho n do vetor
para ordenar).
Multiplicação de 2 inteiros: Número total de bits necessários
para representar a entrada em notação binária.
Comparação de cadeias de caracteres: Número de símbolos
Nas duas cadeias ( n + m).
Um exemplo simples
prod = 0;
cont = x;
Repetir {
prod = prod + y;
cont = cont – 1}
até que cont=0;
Idéia Central
Tempo de execução = No. de passos efetuados pelo algoritmo
EXEMPLO
Algoritmo Inversão de sequência
Entrada: sequência de elementos armazenados no vetor S[i],
i = 1 até n.
Saída: sequência invertida dos elementos de S[i].
Início
Para i := 1, ..., |_ n/2 _| faça
temp := S[i]
S[i] := S[n – i + 1]
S[n – i + 1] := temp
Fim
Classificação – Complexidade de Tempo
Notação:
A - um algoritmo.
E = {E1,...,Em} – conjunto de entradas possíveis de A.
ti = Número de passos efetuados por A com entrada Ei.
Definição:
Complexidade de pior caso = Max (Ei  E) {ti},
Complexidade do caso médio = Σ (1 <= i <= m)(pi * ti)
onde pi é a probabilidade de ocorrência da entrada Ei.
Notações O, Ω e Θ
Notação O  Limite superior para o tempo de execução.
O problema pode ser resolvido em tempo NO MÁXIMO x.
Notação Ω  Limite inferior para o tempo de execução.
O problema requer tempo NO MÍNIMO x.
Notação Θ  Limite exato para o tempo de execução.
O problema requer tempo NO MÍNIMO x e
pode ser resolvido em tempo NO MÁXIMO x.
Notações O, Ω e Θ
Intuitivamente, nas definições de complexidade
usamos as notações O, Ω e θ para
1. Desprezar as constantes aditivas ou multiplicativas.
Ex:
número de passos = 3n + 25
aproximado  n
2. Desprezar os termos de menor grau , mantendo apenas
o termo DOMINANTE.
Ex: número de passos = 3n2 + 8n + 14
aproximado  n2
Notações O, Ω e Θ -
POR QUÊ??
Porque o interesse é assintótico.
Definição (notação O):
Sejam f,h funções positivas de variável inteira n.
Diz-se que f é O(h) [f = O(h)] quando existirem
(1) uma constante c > 0 e
(2) um inteiro n0, tais que:
n > n0 => f(n)  c . h(n)
Ex:
f = n2 + 1
f = n2 + 1
f = 403
f = 3n + 5 log n + 2
f = 5 · 2n + 12 · 5n10





f = O(n2) (c=3, n0 = 4)
f = O(n3) (c=3, n0 = 4)
f = O(1) (c= ?, n0 = ?)
f = O(n)
f = O(2n)
Definição (notação  ):
Sejam f,h funções positivas de variável inteira n.
Diz-se que f é (h), escrevendo-se f = (h),
quando existir uma constante c > 0 e um valor
inteiro n0, tal que:
n > n0 => f(n)  c . h(n)
Ex:
 f = (n2)
f = (n)
f = (1)
Mas não vale: f = (n3)
f = n2 – 1
Definição (notação ):
Sejam f e h funções positivas de variável inteira.
Diz-se que f é (h), escrevendo-se f = (h),
quando ambas as condições acontecem:
f = O(h) e f = (h).