Complexidade Notação O

Esta é uma pré-visualização de arquivo. Entre para ver o arquivo original

*
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. 
*
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). 
Métodos Analíticos
*
Um exemplo simples
prod = 0;
cont = x;
Repetir {
 prod = prod + y;
 cont = cont – 1}
até que cont=0;
*
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
Idéia Central
*
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.
 
Classificação – Complexidade de Tempo
*
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.
*
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 Θ
*
Porque o interesse é assintótico.
Notações O, Ω e Θ - POR QUÊ??
*
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 = O(n2) (c=3, n0 = 4)
 f = n2 + 1  f = O(n3) (c=3, n0 = 4)
 f = 403  f = O(1) (c= ?, n0 = ?)
 f = 3n + 5 log n + 2  f = O(n) 
 f = 5 · 2n + 12 · 5n10  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 – 1  f = (n2)
 f = (n)
 f = (1)
 Mas não vale: f = (n3)
*
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).