Análise de algoritmos

Análise de algoritmos

1. Algoritmo

   • Conjunto finito de instruções precisas para executar uma computação
   • Pode receber como entrada um conjunto de valores e pode produzir como saída outro conjunto de valores

2. Custo de um algoritmo

   • Quando o custo de um algoritmo é igual ao menor custo possível, o algoritmo é ótimo para a medida de custo considerada
   • Podem existir vários algoritmos para resolver o mesmo problema
   • Se a mesma medida de custo é aplicada a diferentes algoritmos, então é possível compará-los e escolher o mais adequado
   • Tipos de medidas
     • Pela execução do programa em uma plataforma real
       • São bastante inadequadas e os resultados jamais devem ser generalizados
     • Por meio de um modelo matemático
       • Usa um modelo matemático baseado em um computador idealizado

3. Tamanho da entrada de dados

   • A medida do curso de execução de um algoritmo depende principalmente do tamanho da entrada de dados
   • É comum considerar o tempo de execução de um programa como uma função do tamanho da entrada
     • Para alguns algoritmos, o custo da execução é uma função da entrada particular dos dados, não apenas do tamanho da entrada
   • Tipos de casos
     • 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
     • Caso médio
       • Média dos tempos de execução de todas as entrada de tamanho n

4. Notação assintótica

   • Comportamento assintótico das funções
     • Representa o limite do comportamento do custo quando n cresce em uma determinada função f(n)
   • Dominação assintótica
     • Medida de custo ou complexidade que relata o crescimento assintótico da operação considerada
   • Tipos
     • Limite rígido
       • Independente da execução, demandará essa quantidade de tempo
     • Limite superior
       • O pior caso do algoritmo demandará essa quantidade de tempo
     • Limite inferior
       • Melhor caso, o menor tempo necessário para executar o algoritmo