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
2013/2
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
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
 encontrar um dado elemento em um conjunto: pesquisa ou busca
 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:
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:
É 
possível 
fazer 
melhor?
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 médio
 Melhor caso
 menor tempo de execução sobre todas as entradas de tamanho n
 Pior caso
 maior tempo de execução sobre todas as 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
Problema: busca/pesquisa/procura em vetor
 Problema
 dado um conjunto de elementos, verificar se um dado elemento ocorre no 
conjunto
 pesquisa ou busca ou procura – search
 Há uma infinidade de algoritmos e estrutura de dados para este 
problema
 pesquisa sequencial em vetor (array) não ordenado
 pesquisa sequencial em vetor ordenado
 pesquisa binária
 hashing
 árvores de pesquisa (AEDS2)
Classificação dos resultados da pesquisa 
 Duas respostas possíveis
 elemento está presente ou não está presente
 Dois casos
 pesquisa com sucesso
 o item procurado está presente no vetor ou arquivo
 pesquisa sem sucesso
 o item procurado não está presente no arquivo
 A análise de complexidade é feita separadamente para cada um 
destes casos
Pesquisa sequencial em vetor
 Vetor não ordenado: caso mais simples de pesquisa
 Entrada
 o vetor preenchido com os elementos do conjunto (registros/estruturas)
 o item procurado: chave de um registro (estruturas)
 Algoritmo
 comparar sequencialmente cada elemento do vetor com o item procurado 
até que
 o item é encontrado: retornar o registro, a posição, etc.
 o fim do vetor é encontrado: indica pesquisa sem sucesso
Exemplo: pesquisar o elemento 22 no vetor
Sucesso: o elemento está presente
Algoritmo: pesquisa sequencial em vetor NÃO ordenado
       32      13       25        19     14       15       5233       64      49      
Vetor não ordenado
Análise do algoritmo de pesquisa sequencial
 Pesquisa em vetor não ordenado
 Definição da operação relevante
 comparação do item procurado com os elementos do conjunto
 Seja f(n) o número de comparações realizado pelo algoritmo de 
pesquisa sequencial
 Análise dos casos
 Pesquisa sem sucesso
 f(n) = n => todos os elementos precisam ser comparados para mostrar que 
o elemento procurado não está presente
 Pesquisa com sucesso
 Melhor caso: f(n) = 1 - o elemento procurado está na 1a. posição
 Pior caso: f(n) = n - o elemento procurado está na última posição
 Caso médio: média de todos os casos - a seguir
Análise do caso médio – pesquisa sequencial
 caso médio: é necessário conhecer a probabilidade de cada elemento do 
conjunto ser procurado
 Neste caso, expressamos a função f(n) da seguinte forma:
 onde p
i
 é a probabilidade do i-ésimo registro (elemento) ser procurado
 Portanto: precisamos conhecer a distribuição de probabilidades do conjunto
 Se cada elemento do conjunto tiver a mesma probabilidade de ser 
procurado, então 
Uso das probabilidades para melhoria da pesquisa
 Como encontrar as probabilidades?
 em geral é difícil conhecer as probabilidades de se pesquisar um elemento
 além disso, as probabilidades podem alterar-se com o tempo ou outros aspectos
 em muitas situações, mesmo não conhecendo a distribuição exata de 
probabilidades, sabemos que a probabilidade de busca de elementos no 
conjunto não é igual
 alguns elementos são muito mais procurados do que outros
 exemplos:
 as 10 palavras mais procuradas no Google em 2012
 Whitney Houston, Gangnam Style, Hurricane Sandy, iPad 3, Diablo 3, Kate 
Middleton, Olympics 2012, Amanda Todd, Michael Clarke Duncan, BBB12
 serviços mais usados pela população
 a sua lista de amigos: alguns são mais próximos
 tabelas: ex: imposto de renda
Uso das probabilidades para melhoria da pesquisa
 Listas auto-ajustáveis
 podemos usar as pesquisas com sucesso para alterar a lista e tornar ao 
caso médio mais rápido
 como?
 mover cada elemento encontrado para posições anteriores na lista
 abordagem conservativa: move uma posição para frente a cada hit
 Exemplo: lista => 1,2,3,4,5,6 => 1,2,4,3,5,6 após buscar o 4
 abordagem agressiva: move o elemento encontrado para a primeira posição
 Exemplo: lista => 1,2,3,4,5,6 => 4,1,2,3,5,6 após buscar o 4
 os elementos mais procurados contribuirão com menor peso para o caso médio
 na busca sequencial, o melhor é ter os elementos ordenados pela frequência de 
busca
Pesquisa sequencial em vetor ordenado
 a pesquisa sequencial pode ser feita em vetor ordenado
 benefício: ocorre somente no caso de pesquisa sem sucesso
      2        3         5          9         14       15       21      33      45       49      
Exemplos de busca: 1, 2, 4, 9, 50
Pesquisa binária
 feita somente em conjuntos ordenados de elementos
 familiar a todos que consultam listas telefônicas e dicionários
 algoritmo básico
 compare a chave pesquisada com o elemento do meio do conjunto
 se a chave for igual: ok, pesquisa com sucesso!
 se a chave for menor, repita o procedimento para a primeira metade do conjunto
 se a chave for maior, repita o procedimento para a segunda metade do conjunto
 até encontrar o elemento ou a posição onde ele deveria estar
 Requisitos
 o conjunto deve estar ordenado pela chave de pesquisa
 o conjunto deve estar em vetor pois o acesso é aleatório
 Pesquisa binária
      2        3         5          9         14       15       21      33      45       49      
1        2        3         4          5        6        7         8        9         10
início
Pesquisa binária: algoritmo
      2        3         5          9         14       15       21      33      45       49      
1        2        3         4          5        6        7         8        9         10
Exemplo de 
algoritmo elegante
Curiosidades: LHC e googol
 Googol: 10100
 LHC: Large Hadron Collider 
 Recriar as condições ocorridas 
uma fração de segundo após o big 
bang
 LHC produz 15 Petabytes de 
dados por ano
 
Dividir para conquistar
Sabe qual é a diferença entre o zero e o um? É uma diferença imensurável.
Não ler é zero. Ler é um. 
Não dá para medir a diferença, pois ela é mais que infinita, é imensurável.  
	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
	Slide 24
	Slide 25
	Slide 26
	Slide 27
	Slide 28
	Slide 29
	Slide 30
	Slide 31
	Slide 32
	Slide 33
	Slide 34
	Slide 35
	Slide 36
	Slide 37
	Slide 38
	Slide 39