Algoritmos e estrutura de dados ii

Disponível somente no TrabalhosFeitos
  • Páginas : 32 (7970 palavras )
  • Download(s) : 0
  • Publicado : 11 de março de 2012
Ler documento completo
Amostra do texto
Medida do Tempo de Execução de um Programa
Livro “Projeto de Algoritmos” – Nívio Ziviani Capítulo 1 – Seção 1.3 http://www2.dcc.ufmg.br/livros/algoritmos/

Algoritmos e Estrutura de Dados II

Medida do Tempo de Execução de um Programa

O projeto de algoritmos é fortemente influenciado pelo estudo de seus comportamentos.

Depois que um problema é analisado e decisões de projeto sãofinalizadas, é necessário estudar as várias opções de algoritmos a serem utilizados, considerando os aspectos de tempo de execução e espaço ocupado.

Muitos desses algoritmos são encontrados em áreas como pesquisa operacional, otimização, teoria dos grafos, estatística, probabilidades, entre outras.
Algoritmos e Estrutura de Dados II

Tipos de Problemas na Análise de Algoritmos

Análise de umalgoritmo particular. Qual é o custo de usar um dado algoritmo para resolver um problema específico?

Algoritmos e Estrutura de Dados II

Tipos de Problemas na Análise de Algoritmos

Análise de um algoritmo particular. Qual é o custo de usar um dado algoritmo para resolver um problema específico? Características que devem ser investigadas:

análise do número de vezes que cada parte doalgoritmo deve ser executada, estudo da quantidade de memória necessária

Algoritmos e Estrutura de Dados II

Tipos de Problemas na Análise de Algoritmos

Análise de um algoritmo particular. Qual é o custo de usar um dado algoritmo para resolver um problema específico? Características que devem ser investigadas:

análise do número de vezes que cada parte do algoritmo deve ser executada,estudo da quantidade de memória necessária.

Análise de uma classe de algoritmos. Qual é o algoritmo de menor custo possível para resolver um problema particular? Toda uma família de algoritmos é investigada. Procura-se identificar um que seja o melhor possível. Coloca-se limites para a complexidade computacional dos algoritmos pertencentes à classe.
Algoritmos e Estrutura de Dados II

Custo deum Algoritmo

Determinando o menor custo possível para resolver problemas de uma dada classe, temos a medida da dificuldade inerente para resolver o problema.

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 adiferentes algoritmos, então é possível compará-los e escolher o mais adequado.

Algoritmos e Estrutura de Dados II

Medida do Custo pela Execução do Programa

Tais medidas são bastante inadequadas e os resultados jamais devem ser generalizados:

os resultados são dependentes do compilador que pode favorecer algumas construções em detrimento de outras;

os resultados dependem do hardware;quando grandes quantidades de memória são utilizadas, as medidas de tempo podem depender deste aspecto.

Apesar disso, há argumentos a favor de se obterem medidas reais de tempo.

Ex.: quando há vários algoritmos distintos para resolver um mesmo tipo de problema, todos com um custo de execução dentro de uma mesma ordem de grandeza.

Assim, são considerados tanto os custos reais das operaçõescomo os custos não aparentes, tais como alocação de memória, indexação, carga, dentre outros.
Algoritmos e Estrutura de Dados II

Medida do Custo por meio de um Modelo Matemático

Usa um modelo matemático baseado em um computador idealizado.

Deve ser especificado o conjunto de operações e seus custos de execuções.

É mais usual ignorar o custo de algumas das operações e considerarapenas as operações mais significativas.

Ex.: algoritmos de ordenação. Consideramos o número de comparações entre os elementos do conjunto a ser ordenado e ignoramos as operações aritméticas, de atribuição e manipulações de índices, caso existam.

Algoritmos e Estrutura de Dados II

Função de Complexidade

Para medir o custo de execução de um algoritmo é comum definir uma função de custo ou...
tracking img