1/31 Análi

Anotacoes

1/31 Análise de Complexidade dos Algoritmos Análise de Complexidade dos Algoritmos Algoritmos e Estruturas de Dados Análise de algoritmos 2/31 Análise de algoritmos Objetivos - Provar que um algoritmo está correto - Determinar os recursos exigidos pelo algoritmo (tempo, espaço, ...) - geralmente existem vários algoritmos para o mesmo problema - como escolher o “melhor” - comparar os recursos exigidos pelos diferentes algoritmos - um algoritmo mais eficiente exige menos recursos para resolver o mesmo problema - prever o crescimento dos recursos exigidos por um algoritmo, à medida que a quantidade de dados de entrada (tamanho de entrada) cresce (taxa de crescimento) Análise de Complexidade dos Algoritmos Algoritmos e Estruturas de Dados Análise de algoritmos 3/31 Tipos de análise - Pormenorizada - mais exacta e direta, mas em geral menos útil - expressa em segundos - resultado da avaliação da eficiência (por ex: tempo gasto): - único - dependente da velocidade e características do processador - Através de ordens de grandeza - ignora as constantes multiplicativas - é uma análise assintótica (ignora os valores pequenos, considera os valores grandes) - expressa em ordens de grandeza (or...