AULA 5 CONTEÚDO ON-LINE - OTIM DE SISTEMAS DE TRANS GST0311

Prévia do material em texto

2: Entender o que se espera na saída
3: Repetir:
Bolar um método.
Se o método é correto, então é preciso:
      - Analisar a complexidade do método; 
      - se complexidade é aceitável, terminar.
4: Implementar (programar)
BOA: Um bom projeto leva a uma boa implementação
- Todas as ideias principais já foram estudadas
- A tradução do projeto em programa é quase mecânica
RUIM: Um projeto não leva a uma boa implementação
- Programar é uma arte
- Um algoritmo inferior bem programado pode ser mais útil que um algoritmo eficiente mal programado
- Há considerações práticas quase tão importantes quanto um bom projeto, como por exemplo:
      - Interfaces 
      - Manutenibilidade 
      - Documentação
Eficiência de um algoritmo
Complexidade de tempo: quanto “tempo” é necessário para computar o resultado para uma instância do problema de tamanho n 
   - Pior caso: Considera-se a instância que faz o algoritmo funcionar mais lentamente.
   - Caso médio: Consideram-se todas as possíveis instâncias e mede-se o tempo médio.
Eficiência de uma estrutura de dados
- Complexidade de espaço: quanto “espaço de memória/disco” é preciso para armazenar a estrutura (pior caso e caso médio).
- Complexidade de espaço e tempo estão frequentemente relacionadas.
Eficiência medida objetivamente
- Como o programador implementou o algoritmo/ED
- Características do computador usado para fazer experimentos:
   - Velocidade da CPU
   - Capacidade e velocidade de acesso à memória primária / secundária, etc 
- Linguagem / Compilador / Sistema Operacional / etc
Medição formal de complexidade 
- Portanto, a medição formal de complexidade tem que ser subjetiva, porém matematicamente consistente
   - Complexidade assintótica