PAA Aula 4

Prévia do material em texto

bruno.conceicao@ufop.edu.br
Prof. Bruno César Cota Conceição
Projeto e análise de Algoritmos
 Aula 4
Análise de algoritmos iterativos e recursivos
Analisando Algoritmos Interativos
Se tratando de algoritmos Iterativos, ou seja, algoritmos que não são recursivos, ou
possuem uma chamada apenas do algoritmo. 
Analisando Algoritmos Interativos
Se tratando de algoritmos Iterativos, ou seja, algoritmos que não são recursivos, ou
possuem uma chamada apenas do algoritmo. 
Encontrar a função de complexidade desse algoritmo se resume a resolver
somatórios.
Analisando Algoritmos Interativos
Somatórios que contam quantas vezes a operação básica que a gente escolheu foi
executada.
Analisando Algoritmos Interativos
Algoritmo encontra o máximo elemento em um arranjo a.
Analisando Algoritmos Interativos
Vamos analisar relacionado a tempo e comparando em função do pior caso.
Analisando Algoritmos Interativos
Vamos analisar relacionado a tempo e comparando em função do pior caso.
É o caso mais interessante quando queremos saber que nosso algoritmo não pode
ser pior que aquele.
Analisando Algoritmos Interativos
Vamos analisar relacionado a tempo e comparando em função do pior caso.
É o caso mais interessante quando queremos saber que nosso algoritmo não pode
ser pior que aquele.
Ou seja, eu tenho um segurança maior falando se eu disser que no pior caso meu
algoritmo é tão ruim quanto essa complexidade.
Analisando Algoritmos Interativos
Então assumimos que o tamanho da entrada é igual ao tamanho do arranjo que é o
que vai variar de entrada para entrada, de instância para instância.
Analisando Algoritmos Interativos
Então assumimos que o tamanho da entrada é igual ao tamanho do arranjo que é o
que vai variar de entrada para entrada, de instância para instância.
E a operação básica desse problema, qual seria interessante de verificar?
Analisando Algoritmos Interativos
Então assumimos que o tamanho da entrada é igual ao tamanho do arranjo que é o
que vai variar de entrada para entrada, de instância para instância.
E a operação básica desse problema, qual seria interessante de verificar?
No caso, é quantas vezes o elemento vai virar o maior ou não.
Analisando Algoritmos Interativos
Então assumimos que o tamanho da entrada é igual ao tamanho do arranjo que é o
que vai variar de entrada para entrada, de instância para instância.
E a operação básica desse problema, qual seria interessante de verificar?
No caso, é quantas vezes o elemento vai virar o maior ou não.
Analisando Algoritmos Interativos
Analisando Algoritmos Interativos
Analisando Algoritmos Interativos
Provar:
Analisando Algoritmos Interativos
Temos aqui um algoritmo que verifica se o arranjo a
contém somente elementos únicos.
Analisando Algoritmos Interativos
Como são dois laços, então teremos dois somatórios
para calcular o pior custo.
Analisando Algoritmos Interativos
Analisando Algoritmos Interativos
Para o segundo caso temos uma
propriedade vista na matemática
discreta:
Analisando Algoritmos Interativos
Para o segundo caso temos uma
propriedade vista na matemática
discreta:
Analisando Algoritmos Interativos
Analisando Algoritmos Interativos
Analisando Algoritmos Interativos
Como podemos observar, essa
representação é menor do que linear.
Já que dividimos sempre por 2,
podemos pensar na altura de uma
árvore binária.
Analisando Algoritmos Interativos
Analisando Algoritmos Interativos
Analisando Algoritmos Interativos
Análise de Algoritmos Recursivos
Análise de Algoritmos Recursivos
Análise de Algoritmos Recursivos
Basicamente é um projeto de algoritmo por indução.
Análise de Algoritmos Recursivos
Como analisar o
algoritmo? Porque não
tem laço...
Análise de Algoritmos Recursivos
Precisamos de técnicas específicas para representar
essas funções de complexidades de algoritmos
recursivos.
Como analisar o
algoritmo? Porque não
tem laço...
Análise de Algoritmos Recursivos
O recurso matemático
que vamos utilizar são
as funções de
recorrência.
Análise de Algoritmos Recursivos
Análise de Algoritmos Recursivos
Precisamos traduzir essa recorrência para uma forma fechada e então analisar ela e
descobrir a qual notação assintótica ela pertence. Qual a ordem de crescimento dessa
função.
Análise de Algoritmos Recursivos
Aplicando nossa técnica:
 Passo 1: Começar a escrever essa recorrência.
Análise de Algoritmos Recursivos
Análise de Algoritmos Recursivos
Passo 2: Substituindo o valor de i na função:
Função de complexidade nesse caso é n
Função de complexidade nesse caso é n
Análise de Algoritmos Recursivos
Passo 2: Substituindo o valor de i na função:
Resolvendo Recorrências: Substituição
Resolvendo Recorrências: Substituição
Método formal, pois usa indução matemática para provar que uma recorrência
é uma função de determinada ordem.
Resolvendo Recorrências: Substituição
Resolvendo Recorrências: Substituição
Vamos provar essa recorrência:
Resolvendo Recorrências: Substituição
Vamos provar essa recorrência:
Resolvendo Recorrências: Substituição
Resolvendo Recorrências: Substituição
Desenvolvendo
Agora precisamos achar um c que faça nossa expressão ser verdadeira.
Resolvendo Recorrências: Substituição
Agora precisamos achar um c que faça nossa expressão ser verdadeira.
Resolvendo Recorrências: Substituição
Agora precisamos achar um c que faça nossa expressão ser verdadeira.
Resolvendo Recorrências: Substituição
Agora precisamos achar um c que faça nossa expressão ser verdadeira.
Resolvendo Recorrências: Substituição
Agora vamos ver o passo base.
Resolvendo Recorrências: Substituição
Resolvendo Recorrências: Substituição
Parece que a principio n = 1 está errado e não serve, porém temos que lembrar que na
notação assintótica, temos que encontrar um n0 que a partir desse momento, aquela
função começa a dominar.
Resolvendo Recorrências: Substituição
Parece que a principio n = 1 está errado e não serve, porém temos que lembrar que na
notação assintótica, temos que encontrar um n0 que a partir desse momento, aquela
função começa a dominar.
Então o passo base pode ser um valor inicial qualquer que eu escolher.
Resolvendo Recorrências: Substituição
Parece que a principio n = 1 está errado e não serve, porém temos que lembrar que na
notação assintótica, temos que encontrar um n0 que a partir desse momento, aquela
função começa a dominar.
Então o passo base pode ser um valor inicial qualquer que eu escolher.
Vamos tentar agora com n=2.
Resolvendo Recorrências: Substituição
Basta que o c seja pelo menos 2 para que esta inequação ser verdade.
Assim provamos o caso base, e já provamos o passo da indução. Portanto está
provado que:
Métodos adicionais: vamos treinar com exercícios e discutir em outras
oportunidades
Encontrar função fechada da recorrência.
Expansão de termos com um plus do recurso visual.
Entender a intuição por trás dele e aplicar diretamente.
Dica: pegar uma recorrência, entender como foi a
transformação do algoritmo para a recorrência, e ai
resolver a recorrência por vários métodos.
Referências:
Créditos ao professor Vinícius Dias pelo material disponibilizado.
 LEVITIN, Anany. Introduction to the Design and Analysis of Algorithms. 3a edition. Editora
Addison Wesley;
2. CORMEN, Thomas H.; LEISERSON, Charles E.; RIVEST, Ronald L.; STEIN, Clifford.
Introduction to Algorithms. 3a edition. Editora The MIT Press;
3. ERICKSON, Jeffe. Algorithms. 1st edition. June 2019.
Disponível em: https://jeffe.cs.illinois.edu/teaching/algorithms/book/Algorithms-JeffE.pdf
4. KLEINBERG, Jon; TARDOS, Éva. Algorithm Design. Editora Addison Wesley.
5. DASGUPTA, Sanjoy; PAPADIMITRIOU, Christos; VAZIRANI, Umesh. Algorithms. Editora
McGraw-Hill.
Disponível em: https://integrada.minhabiblioteca.com.br/#/books/9788563308535/pageid/0
6. MANBER, Udi. Introduction to Algorithms: A Creative Approach. 1st edition. Editora
AddisonWesley
7. DE, A. et al. [s.l: s.n.].Disponível em: <http://waltenomartins.com.br/ap_aa_v1.pdf>. Acesso em: 4 out. 2023.