Análise e Complexidade de Algoritmos

Análise e Complexidade de Algoritmos

1. Procedimentos computacionais

   • Entradas
     • Saídas
   • Algoritmo correto
     • Resolve o problema

2. Avaliar eficiência/desempenho

   • Considerado tecnologia
   • Tão importante como hardware

3. Computador infinitamente rápido?

   • Recursos limitados
     • Processamento
     • memória

4. Ordenação

   • Inserção
     • Exemplo do baralho
     • loop invariante
       • ao final de cada etapa uma parte da solução
       • provar a corretude
       • Inicialização
         • verdadeira antes da primeira iteração
       • manutenção
         • durante a execução
       • término

5. Complexidade de Algoritmos

   • Tempo
     • Depende da entrada
       • Qtd de itens
       • custo linear
         • melhor caso
         • melhor caminho
           • já ordenado
         • loop
       • custo quadrático
         • maior tempo de execução
         • executar todos os passos
         • pior caso
       • custo constante
         • instruções simples
     • Um algoritmo é melhor se o custo de pior caso for menor
   • Comportamento
   • Complexidade Assintótica
     • Comportamento de acordo com o crescimento da entrada
       • Tende ao infinito
     • Assintoticamente mais eficiente
       • um algoritmo que é assintoticamente mais eficiente será a melhor escolha para todas as entradas, exceto as muito pequenas
     • Medidas de complexidade/Custo
       • Melhor caso
         • Menor tempo de execução sobre todas as possíveis entradas de tamanho N
       • pior caso
         • maior tempo de execução
       • caso médio
         • média dos tempos de todas as as entradas
     • Descarta termos constantes

6. Prevê recursos neccessários

7. Resolver problemas computacionais

8. Divisão e conquista

   • Ordenação por intercalação
     • Divide em 2 pedaços
       • Classificar recursivamente
         • Intercalar as 2 metades
     • Custo: Equação de recorrência
       • 2*T(n/2) --divisão + O(n) -Merge
   • Recursividade
     • Chamar a si mesmo
   • Passos:
     • Dividir
       • Conquistar
         • Combinar
           • Merge
   • QuickSort

9. Estudar n. de vezes que operações são executadas

10. Algoritmos Gulosos

    • Busca resolver problemas de otimização
      • caminho mínimo/menor custo
    • Técnica de construção de algoritmos
    • Preocupa-se a melhor opção LOCAL viável
    • Lembrar PACMAN/Come e não vomita
    • Algoritmos simples e de fácil implementação
    • Conjunto de candidatos
      • Escolhidos
      • Rejeitados
    • Passo
      • Escolhe qual elemento é mais viável
        • Sequencia de decisões para alcançar o prob.
          • Ou faz parte da decisão, ou é descartado
      • Lembrar do problema do troco

11. Backtracking

    • Busca exaustiva/completa
    • Método Sistemático
    • Estratégia de resolução de problemas
    • Se der errado, volta e escolhe outro caminho

12. Medir eficiência

13. Algoritmos diferentes resolvem o mesmo problema com a mesma eficiência?

14. Complexidade computacional

    • Custo = memória + tempo
    • Análise
      • Empírica
        • Na execução
          • Analisa desempenho
          • custos não aparentes/alocação a memória
          • computadores e linguagens
          • resultado pode ser mascarado pelo hardware
            • pode existir outra execução no momento
      • Matemática
        • Estudo formal
          • Ideia por trás do algoritmo
        • Independente de hardware
          • Ignora detalhes de baixo nível (LP, hardware)
          • ident. como o algoritmo se comporta c entrada

Images and files in the map