Análise e Complexidade de Algoritmos

Procedimentos computacionais
1. Entradas
  1. Saídas
2. Algoritmo correto
  1. Resolve o problema
Avaliar eficiência/desempenho
1. Considerado tecnologia
2. Tão importante como hardware
Computador infinitamente rápido?
1. Recursos limitados
  1. Processamento
  2. memória
Ordenação
1. Inserção
  1. Exemplo do baralho
  2. loop invariante
    1. ao final de cada etapa uma parte da solução
    2. provar a corretude
    3. Inicialização
      1. verdadeira antes da primeira iteração
    4. manutenção
      1. durante a execução
    5. término
Complexidade de Algoritmos
1. Tempo
  1. Depende da entrada
    1. Qtd de itens
    2. custo linear
      1. melhor caso
      2. melhor caminho
        já ordenado
      3. loop
    3. custo quadrático
      1. maior tempo de execução
      2. executar todos os passos
      3. pior caso
    4. custo constante
      1. instruções simples
  2. Um algoritmo é melhor se o custo de pior caso for menor
2. Comportamento
3. Complexidade Assintótica
  1. Comportamento de acordo com o crescimento da entrada
    1. Tende ao infinito
  2. Assintoticamente mais eficiente
    1. um algoritmo que é assintoticamente mais eficiente será a melhor escolha para todas as entradas, exceto as muito pequenas
  3. Medidas de complexidade/Custo
    1. Melhor caso
      1. Menor tempo de execução sobre todas as possíveis entradas de tamanho N
    2. pior caso
      1. maior tempo de execução
    3. caso médio
      1. média dos tempos de todas as as entradas
  4. Descarta termos constantes
Prevê recursos neccessários
Resolver problemas computacionais
Divisão e conquista
1. Ordenação por intercalação
  1. Divide em 2 pedaços
    1. Classificar recursivamente
      1. Intercalar as 2 metades
  2. Custo: Equação de recorrência
    1. 2*T(n/2) --divisão + O(n) -Merge
2. Recursividade
  1. Chamar a si mesmo
3. Passos:
  1. Dividir
    1. Conquistar
      1. Combinar
        Merge
4. QuickSort
Estudar n. de vezes que operações são executadas
Algoritmos Gulosos
1. Busca resolver problemas de otimização
  1. caminho mínimo/menor custo
2. Técnica de construção de algoritmos
3. Preocupa-se a melhor opção LOCAL viável
4. Lembrar PACMAN/Come e não vomita
5. Algoritmos simples e de fácil implementação
6. Conjunto de candidatos
  1. Escolhidos
  2. Rejeitados
7. Passo
  1. Escolhe qual elemento é mais viável
    1. Sequencia de decisões para alcançar o prob.
      1. Ou faz parte da decisão, ou é descartado
  2. Lembrar do problema do troco
Backtracking
1. Busca exaustiva/completa
2. Método Sistemático
3. Estratégia de resolução de problemas
4. Se der errado, volta e escolhe outro caminho
Medir eficiência
Algoritmos diferentes resolvem o mesmo problema com a mesma eficiência?
Complexidade computacional
1. Custo = memória + tempo
2. Análise
  1. Empírica
    1. Na execução
      1. Analisa desempenho
      2. custos não aparentes/alocação a memória
      3. computadores e linguagens
      4. resultado pode ser mascarado pelo hardware
        pode existir outra execução no momento
  2. Matemática
    1. Estudo formal
      1. Ideia por trás do algoritmo
    2. Independente de hardware
      1. Ignora detalhes de baixo nível (LP, hardware)
      2. ident. como o algoritmo se comporta c entrada

Media attachments

5a3600d8-5e4c-44bd-b79d-7df3081a00fc.PNG (image/PNG)

Next up

Análise e Complexidade de Algoritmos

Description

Resource summary

Media attachments

Similar

	Created by Izabella Rezende almost 8 years ago