Métodos de Análise e Projeto de Algoritmos

Notação Assintótica

Em geral, um algoritmo que é assintoticamente mais eficiente será a melhor escolha para todas as entradas, exceto as muito pequenas.

Recorrências

Seguem uma abordagem dividir e conquistar que envolve três passos em cada nível da recursão:

1. Dividir o problema em um determinado número de subproblemas.
2. Conquistar os subproblemas, resolvendo-os recursivamente. Porém, se os tamanhos dos subproblemas forem pequenos o bastante, basta resolvê-los de maneira direta.
3. Combinar as soluções dos subproblemas para formar a solução para o problema original.

Método de Substituição

Este método é usado para resolver recorrências e envolve os seguintes passos:

• Pressupor a forma da solução.
• Usar a indução matemática para encontrar as constantes e mostrar que a solução funciona.

Este método é eficiente, mas só pode ser aplicado em casos nos quais é fácil pressupor a forma da resposta. O método de substituição pode ser usado para estabelecer limites superiores ou inferiores sobre uma recorrência.

Método da Árvore de Recursão

Cada nó representa o custo de um único subproblema em algum lugar no conjunto de invocações de funções recursivas. Somamos os custos dentro de cada nível da árvore para obter um conjunto de custos por nível, e então somamos todos os custos por nível para determinar o custo total de todos os níveis da recursão.

Método Mestre

O Método Mestre fornece um processo de “livro de receitas” para recorrências da forma T(n) = aT(n/b) + f(n), onde a ≥ 1 e b > 1 são constantes, e f(n) é uma função assintoticamente positiva.

O Método Mestre exige a memorização de três casos, mas, daí em diante, a solução de muitas recorrências pode ser descoberta com facilidade.

Algoritmos Gulosos (Greedy)

Em geral, os algoritmos relacionados a problemas de otimização funcionam através de uma sequência de passos, com um conjunto de opções (escolhas) em cada passo. Um algoritmo guloso sempre faz a escolha que parece ser a melhor no momento (a escolha mais apetitosa).

Divisão e Conquista (Divide and Conquer)

Em geral, esses algoritmos seguem uma abordagem de dividir e conquistar: eles quebram o problema em vários subproblemas que são similares ao problema original, mas menores em tamanho, os resolvem recursivamente e combinam as soluções para solucionar o problema original.

Processo de Divisão e Conquista

Passos no Nível da Recursão

• Dividir: O problema em um determinado número de subproblemas.
• Conquistar: Os subproblemas, resolvendo-os recursivamente. (Se os subproblemas forem pequenos o bastante, basta resolvê-los de maneira direta.)
• Combinar: As soluções dadas aos subproblemas, a fim de formar a solução para o problema original.

Vantagens

• Simplifica problemas complexos.
• Resolve problemas de modo eficiente.
• Permite Paralelismo.