AEDII-aula03

Prévia do material em texto

1
Aula 03 – Notação assintótica, 
Pesquisa binária e recursividade
MC3305
Algoritmos e Estruturas de Dados II
Prof. Jesús P. Mena-Chalco
jesus.mena@ufabc.edu.br
2Q-2014
2
Notação assintótica de funções
Introdução baseada nas aulas do Prof. Antonio A. F. Loureiro (UFMG)
3
Comportamento assintótico de funções
A análise de algoritmos é realizada para
valores grandes de n.
Estudaremos o comportamento assintótico das funções de 
custo.
O comportamento assintótico de f(n) representa o limite do 
comportamento de custo, quando n cresce.
4
Dominação assintótica
Definição:
Uma função f(n) domina assintoticamente uma outra 
função g(n) se existem duas constantes positivas c e tais 
que, para , temos:
5
Dominação assintótica
Definição:
Uma função f(n) domina assintoticamente uma outra 
função g(n) se existem duas constantes positivas c e tais 
que, para , temos:
6
Dominação assintótica
Exemplo:
Sejam
Ambas as funções dominam assintoticamente uma da outra, 
ja que:
 para n>=1
 para n>=0
7
Notação assintótica de funções
Existem 3 notações assintóticas de funções:
Notação
Notação
Notação
8
Notação 
 g(n) é um limite assintótico firme de f(n)
9
Notação 
 f(n) é da ordem no máximo g(n)
O é usada para expressar o tempo de execução de um algoritmo no pior caso, está se 
definindo também o limite (superior) do tempo de execução desse algoritmo para todas 
as entradas.
10
Notação 
Operações entre conjuntos de funções
11
Notação 
Omega: Define um limite inferior para a função, por um fator constante.
g(n) é um limite assintoticamente inferior
12
Teorema 
13
Comparação de programas
Podemos avaliar programas comparando as funções de 
complexidade, negligenciando as constantes de 
proporcionalidade.
Um programa com tempo de execução é melhor do 
que outro com tempo
14
Comparação de programas
Exemplo:
O programa1 leva vezes para ser executado.
O programa2 leva vezes para ser executa. 
Qual dos dois é o melhor?
Programa 1 Programa 2
15
Comparação de programas
Exemplo:
O programa1 leva vezes para ser executado.
O programa2 leva vezes para ser executa. 
Qual dos dois é o melhor?
Depende do tamanho do problema.
Programa 1 Programa 2
16
Comparação de programas
Exemplo:
O programa1 leva vezes para ser executado.
O programa2 leva vezes para ser executa. 
Qual dos dois é o melhor?
Depende do tamanho do problema.
Para n<50, o programa 2 é melhor
Para n>50, o programa 1 é melhor
Programa 1 Programa 2
17
Comparação de programas
18
Comparação de funções de complexidade
19
Hierarquias de funções
A seguinte herarquia de funções pode ser definida do ponto 
de vista assintótico:
onde e são constantes arbitrárias com 
20
Tratabilidade do problema
Um problema é considerado
Intratável:
Se ele é tão difícil que não se conhece um algoritmo 
polinomial para resolvê-lo
Tratável (bem resolvido):
Se existe um algoritmo polinomial para resolvê-lo.
21
Tratabilidade do problema
Um problema é considerado
Intratável:
Se ele é tão difícil que não se conhece um algoritmo 
polinomial para resolvê-lo
Ex. Algoritmo do caixeiro viajante
Tratável (bem resolvido):
Se existe um algoritmo polinomial para resolvê-lo.
Ex. Algoritmo de multiplicação de matrizes.
← Algoritmo de Strassen
22
O problema do Caixeiro Viajante
Um caixeiro viajante deseja visitar n cidades de tal forma que 
sua viagem inicie e termine em uma mesma cidade, e cada 
cidade pode ser visitada uma única vez.
Supondo que sempre há uma estrada entre 2 cidades, o 
problema é encontrar a menor ruta para a viagem.
23
O problema do Caixeiro Viajante
Um caixeiro viajante deseja visitar n cidades de tal forma que 
sua viagem inicie e termine em uma mesma cidade, e cada 
cidade pode ser visitada uma única vez.
Supondo que sempre há uma estrada entre 2 cidades, o 
problema é encontrar a menor ruta para a viagem.
24
O problema do Caixeiro Viajante
Um algoritmo “simples” seria verificar todas as rotas e 
escolher a menor delas.
Há rotas possíveis 
a distância total percorrida em cada rota envolve n adições
logo o número de adiciones é
25
O problema do Caixeiro Viajante
Um algoritmo “simples” seria verificar todas as rotas e 
escolher a menor delas.
Há rotas possíveis 
a distância total percorrida em cada rota envolve n adições
logo o número de adiciones é
No exemplo anterior teríamos 24 adições.
26
O problema do Caixeiro Viajante
Um algoritmo “simples” seria verificar todas as rotas e 
escolher a menor delas.
Há rotas possíveis 
a distância total percorrida em cada rota envolve n adições
logo o número de adiciones é
No exemplo anterior teríamos 24 adições.
Com 50 cidades teríamos 
27
O problema do Caixeiro Viajante
Um algoritmo “simples” seria verificar todas as rotas e escolher 
a menor delas.
Há rotas possíveis 
a distância total percorrida em cada rota envolve n adições
logo o número de adiciones é
No exemplo anterior teríamos 24 adições.
Com 50 cidades teríamos 
Em um computador que executa adições por segundo
o tempo para resolver o problema seria > séculos.
28
O problema do Caixeiro Viajante
29
Pesquisa Binária
30
Algoritmo de Pesquisa Binária
Binary search algorithm
Binary chop
Parte do presuposto de que o vetor está ordenado e realiza 
sucessivas divisões do espaço de busca:
O elemento procurado (chave) é comparado com o 
elemento do meio do vetor:
Se são iguais, a busca termina com sucesso.
Caso contrário:
Se o elemento do meio vier antes da chave, então a busca continua 
na metade posterior do vetor,
Caso contrário, a busca continua na metade anterior do vetor.
31
Algoritmo de Pesquisa Binária
32
Algoritmo de Pesquisa Binária
Onde esta o erro?
33
Algoritmo de Pesquisa Binária
O algoritmo parte do presuposto de termos o vetor ordenado na forma ascendente.
Existe outro erro?
34
Algoritmo de Pesquisa Binária
Melhor caso: 
Pior caso:
35
Algoritmo de Pesquisa Binária
Melhor caso: 1
Pior caso: log(n)
36
Algoritmo de Pesquisa Binária (versão 2)
Onde está o erro?
37
Algoritmo de Pesquisa Binária (versão 2)
Erro nos índices (do slide anterior)
38
Algoritmo de Pesquisa Binária (versão 2)
39
Recursividade 
Uma função recursiva é aquela que se chama a si mesma (obrigatoriamente)?
40
Recursividade 
Uma função recursiva não necessariamente é aquela que se chama a si mesma
41
Exercícios-Problema (EPs) para esta semana
10696 - Problem A - f91
299 - Train Swapping 
10499 - The Land of Justice 
Data: 07/Julho (segunda-feira) até às 23h50.
Arquivos: 
Para cada exercício-problema deverá submeter:
O código fonte: nome do arquivo → RA_nroDoProblema.cpp
O comprovante de aceitação (Uva) → RA_nroDoProblema.pdf
Exemplo: 10123456_11567.cpp
 10123456_11567.pdf
42
Exercícios-Problema
Use o Toolkit para ter mais exemplos de dados de entrada
http://uvatoolkit.com/problemssolve.php
Teste com o problema 10055 – Hashmat
Resultados Finais do ICPC
http://icpc.baylor.edu/scoreboard/
43
ICPC
Resultados Finais do ICPC
http://icpc.baylor.edu/scoreboard/Slide 1
	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 40
	Slide 41
	Slide 42
	Slide 43