aula2-casos

Prévia do material em texto

Algoritmos e Estruturas de Dados I
Análise de Complexidade de Algoritmos
Curso de Engenharia de Computação
CEFET-MG
2015/1
Conteúdo da aula
 Exemplos de análise de complexidade de trechos de código
 Casos de complexidade: melhor, pior, esperado
 Custos de problemas importantes em computação
 Exercícios 
Análise de complexidade: exemplo 1
 Função troca ()   
 Seja f(n) o número de operações feito nessa função
 f(n) = 3
Análise de complexidade: exemplo 2
 Inicialização de um vetor
 Seja f(n) o número de instruções executado nesse trecho 
de código
 f(n) = 3n + 2 <= conforme visto na aula anterior
Análise da complexidade pela operação 
relevante 
 O principal interesse da análise de complexidade é 
encontrar a ordem de complexidade da função de custo
 Se a função é constante, logarítmica, linear, quadrática, cúbica, etc.
 As constantes aditivas e multiplicativas da função de custo não são 
relevantes (exceto em casos especiais)
 Por isso, podemos eleger uma operação relevante e fazer a análise 
em função dessa operação
 Exemplo: no código do slide anterior, podemos eleger a atribuição 
a[i]= 0 como operação relevante e obter g(n) = n, que é da 
mesma ordem de complexidade (linear) que f(n) = 3n + 2
Análise de complexidade: exemplo 3 
 Reavaliando o custo usando a notação matemática adequada
Seja g(n) o número de vezes que a atribuição  a[i] = 0 é feita: 
Análise de complexidade: exemplo 4
Operação relevante: multiplicação
Seja f(n) o número de multiplicações feito no código acima:
Análise de complexidade: exemplo 5
Operação relevante: adição
Seja f(n) o número de adições feito no código acima:
Análise de complexidade: exemplo 6
Operação relevante: multiplicação
Seja f(n) o número de multiplicações feito no código acima:
Somatórios 
Soma de uma constante
Soma dos primeiros números naturais
 Mais somatórios
Bibliografia: 
Matemática Concreta: Fundamentos para a Ciência da Computação,
Ronald L. Graham, Donald E. Knuth e Oren Patashnik. 2a edição, 1995, 
LTC.
Análise de complexidade de algoritmos
 Análise de casos específicos
 Melhor caso
 Pior caso
 Caso médio ou esperado
 Análise de problemas específicos
 encontrar o maior elemento de um conjunto
 encontrar o maior e o menor elementos
 Casos de complexidade
 Casos melhor, pior e médio 
ou esperado
 Por que eles ocorrem?
 testes e comandos 
condicionais direcionam a 
caminhos diferentes de 
execução do código 
 cada caminho de execução 
pode ter comandos em 
número e tipos diferentes
 a quantidade de trabalho pode 
ser diferente em cada caminho 
de execução
comando
if (teste)
comando
comando
comando
comando
V
F
Problema: encontrar o maior elemento de um 
conjunto de elementos
 Definição da operação relevante: comparação entre elementos do vetor
 Seja f(n) o número de comparações realizado no código acima:
Custo mínimo ou limite inferior do problema
 Pergunta
 qual é o custo mínimo para encontrar o maior elemento de um conjunto de n 
elementos?
 Teorema
 qualquer algoritmo para encontrar o maior elemento de um conjunto de n elementos 
faz pelo menos n-1 comparações
 Prova
 Devemos mostrar que cada um dos n-1 elementos é menor do que o maior elemento; 
portanto, n-1 comparações são necessárias
 O algoritmo apresentado é ótimo?
 Sim, pois seu custo é igual ao custo mínimo para resolver o problema.
Problema: encontrar o maior elemento de um 
conjunto de elementos
 Seja g(n) o número de vezes que é feita uma atribuição 
para a variável maior:
 dependendo da organização dos dados da entrada, 
podem ser realizadas entre 1 e n atribuições
Para que tipo de 
entrada ocorrem 
os casos 
extremos?
Problema: encontrar o maior e o menor 
elementos de um conjunto (maxmin1)
Seja f(n) o número de comparações entre elementos do vetor:
Versão 2: maxmin2
O custo da execução pode depender não somente do 
tamanho da entrada de dados, mas também da ordem
dos elementos em cada entrada específica de tamanho n.
O custo da execução pode depender não somente do 
tamanho da entrada de dados, mas também da ordem
dos elementos em cada entrada específica de tamanho n.
IMPORTANTEIMPORTANTE!
Versão 2: maxmin2
Seja f(n) o número de comparações entre elementos do vetor:
melhor caso: 
pior caso: 
Em que 
condições 
estes casos 
ocorrem?
Maxmin2: análise do caso médio
 Seja f(n) o número de comparações entre elementos do vetor
 Análise simples do caso médio:
 o número mínimo de comparações é n-1
 vamos supor que os resultados dos testes no primeiro if são
 50% verdadeiro
 50% falso
 Portanto, teremos: 
Limite inferior para o problema de encontrar o 
maior e o menor elementos
 Considere a seguinte estratégia para resolver o problema (maxmin3):
 Primeira parte: compare os elementos aos pares, identificando o maior e o menor 
em cada par
 Segunda parte: encontre o maior no conjunto de maiores e o menor no conjunto de 
menores
 Se o tamanho do conjunto for ímpar, último elemento deve ser duplicado 
Custo: 
Para 
todos os 
casos!
Comparação entre os algoritmos maxmin
algoritmo melhor caso pior caso caso médio
maxmin1 2(n­1) 2(n­1) 2(n­1)
maxmin2 n­1 2(n­1) 3n/2 – 3/2
maxmin3 3n/2 – 2 3n/2 – 2 3n/2 – 2
Qual é a sua 
análise para 
estes dados?
 Definição dos casos melhor, pior e esperado
 Melhor caso
 Menor número de comandos executados para n dados de entreda
 Menor tempo de execução para entradas de tamanho n
 Pior caso
 Maior número de comandos para entradas de tamanho n
 Maior tempo de execução para entradas de tamanho n
 fornece um limite superior para o número de instruções
 o custo da execução do algoritmo nunca será pior do que o pior caso
 corresponde à entrada de dados mais desfavorável
 Caso médio ou esperado
 média dos tempos de execução para TODAS as entradas de tamanho n
 depende da probabilidade de ocorrência de cada arranjo específico da entrada 
 esta distribuição de probabilidades nem sempre é conhecida
 é comum supor que todas as entradas possíveis são igualmente prováveis
 
 
Importância dos casos
 Pior caso
 muitas vezes é considerada a medida mais importante
 fornece um limite superior para o número de passos que o 
algoritmo pode efetuar, para qualquer entrada de tamanho n
 Caso médio
 é o caso esperado
 é uma medida da maioria dos casos
 considerada muito importante
 a análise do caso médio pode ser complexa
 Melhor caso
 uso menos freqüente, para situações específicas
 
 
Análise de Complexidade: conclusões até 
aqui
 O número de comandos executados por um algoritmo é uma 
medida da complexidade de tempo do algoritmo
 O número de comandos executados depende do tamanho da 
entrada 
 e pode depender também do arranjo específico dos dados na 
entrada, isto é, de como os dados estão combinados entre si 
para uma entrada de mesmo tamanho
• A análise completa dos algoritmos inclui todos os casos
A seguir: exercícios no quadro
	Computabilidade
	Slide 2
	Slide 3
	Slide 4
	Slide 5
	Slide 6
	Slide 7
	Slide 8
	Slide 9
	Slide 10
	Slide 11
	Slide 12
	Slide 13
	Slide 14
	Slide 15
	Slide 16
	Slide 17
	Slide 18
	Slide 19
	Slide 20
	Slide 21
	Slide 22
	Slide 23
	Importância dos casos
	Complexidade de tempo
	Slide 26