PAA Aula 6

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 6
Projeto de algoritmos por Redução e Conquista
(Incremental)
Projeto de algoritmos: Incremental 
(decrease-and-conquest)
Projeto de algoritmos: Incremental 
(decrease-and-conquest)
Projeto de algoritmos: Incremental 
(decrease-and-conquest)
Projeto de algoritmos: Incremental 
(decrease-and-conquest)
Projeto de algoritmos: Incremental 
(decrease-and-conquest)
Projeto de algoritmos: Incremental 
(decrease-and-conquest)
Projeto de algoritmos: Incremental 
(decrease-and-conquest)
Projeto de algoritmos: Incremental 
(decrease-and-conquest)
Projeto de algoritmos: Incremental 
(decrease-and-conquest)
Projeto de algoritmos: Incremental 
(decrease-and-conquest)
Projeto de algoritmos: Incremental 
(decrease-and-conquest)
Projeto de algoritmos: Incremental 
(decrease-and-conquest)
Projeto de algoritmos: Incremental 
(decrease-and-conquest)
Da para fazer melhor? Uma solução que seja por
exemplo O(n)?
Projeto de algoritmos: Incremental 
(decrease-and-conquest)
Projeto de algoritmos: Incremental 
(decrease-and-conquest)
Começamos a perceber a repetição de elementos de ordem maior.
Projeto de algoritmos: Incremental 
(decrease-and-conquest)
Começamos a perceber a repetição de elementos de ordem maior.
E alguns valores sendo multiplicados de forma repitida.
Projeto de algoritmos: Incremental 
(decrease-and-conquest)
Começamos a perceber a repetição de elementos de ordem maior.
E alguns valores sendo multiplicados de forma repitida.
Quando identificamos a solução de um mesmo subproblema.
Projeto de algoritmos: Incremental 
(decrease-and-conquest)
Começamos a perceber a repetição de elementos de ordem maior.
E alguns valores sendo multiplicados de forma repitida.
Quando identificamos a solução de um mesmo subproblema.
Dizemos que há a sobreposição de um subproblema, e assim, utilizamos essa
solução para os demais.
Projeto de algoritmos: Incremental 
(decrease-and-conquest)
Projeto de algoritmos: Incremental 
(decrease-and-conquest)
Projeto de algoritmos: Incremental 
(decrease-and-conquest)
Projeto de algoritmos: Incremental 
(decrease-and-conquest)
Projeto de algoritmos: Incremental 
(decrease-and-conquest)
Projeto de algoritmos: Incremental 
(decrease-and-conquest)
Projeto de algoritmos: Incremental 
(decrease-and-conquest)
Projeto de algoritmos: Incremental 
(decrease-and-conquest)
Projeto de algoritmos: Incremental 
(decrease-and-conquest)
Logo, nosso problema de exponenciação, que é nato ser de
ordem linear, pode ser resolvido com um número muito
menor de operações de ordem logarítmica.
Projeto de algoritmos: Incremental 
(decrease-and-conquest)
Logo, nosso problema de exponenciação, que é nato ser de
ordem linear, pode ser resolvido com um número muito
menor de operações de ordem logarítmica.
Visto que o logaritmo cresce sempre muito lentamente.
Projeto de algoritmos: Incremental 
(decrease-and-conquest)
Logo, nosso problema de exponenciação, que é nato ser de
ordem linear, pode ser resolvido com um número muito
menor de operações de ordem logarítmica.
Visto que o logaritmo cresce sempre muito lentamente.
Conseguimos isso pela sobreposição de subproblemas.
Estudo de caso: Ordenação por inserção
Estudo de caso: Ordenação por inserção
Mão de cartas já ordenada
Estudo de caso: Ordenação por inserção
Estudo de caso: Ordenação por inserção
Pseudo-código: Ordenação por inserção
Pseudo-código: Ordenação por inserção
Análise da complexidade: Ordenação por inserção
Análise da complexidade: Ordenação por inserção
Operação que nós vamos analisar.
Análise da complexidade: Ordenação por inserção
Pior caso, pular todos os “is” elementos.
Análise da complexidade: Ordenação por inserção
Pior caso, pular todos os “is” elementos.
Melhor caso, já estar na posição correta.
Análise da complexidade: Ordenação por inserção
Análise da complexidade: Ordenação por inserção
No melhor caso, existem algumas entradas que vão fazer esse algoritmo ter um
comportamento linear. 
Análise da complexidade: Ordenação por inserção
No melhor caso, existem algumas entradas que vão fazer esse algoritmo ter um
comportamento linear. 
Isso quando a entrada estiver ordenada.
Análise da complexidade: Ordenação por inserção
No melhor caso, existem algumas entradas que vão fazer esse algoritmo ter um
comportamento linear. 
Isso quando a entrada estiver ordenada.
No pior caso, ele sempre troca todo mundo.
Considerações sobre a complexidade de espaço
Considerações sobre a complexidade de espaço
O n pode crescer indefinidamente, eu posso ter entradas
grandes. Mas quanto de espaço eu preciso para executar este
algoritmo, fora esse tamanho da entrada e em função de n.
Considerações sobre a complexidade de espaço
Não precisamos de espaço adicional nenhum. Usamos o
mesmo espaço, já alocado da entrada, que é o arranjo, para
mover o elemento no arranjo.
Considerações sobre a complexidade de espaço
A quantidade de memória que vou utilizar é um valor fixo
e não vai variar conforme o tamanho da entrada.
Considerações sobre a complexidade de espaço
Independente se é o melhor caso, caso médio ou pior caso.
Sempre as operações serão in-place e não vamos precisar de
um espaço adicional para executar este algoritmo..
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.