Algoritmos

Cecíllia Moreira de Araújo
Analise de Algoritmos
Analisar um algoritmo significa prever os recursos de que o algoritmo necessitará. Ocasionalmente, recurso como memória, largura de banda de comunicação ou hardware de computador são a principal preocupação, mas com freqüência é o tempo de computação que desejamos medir.
Antes de podermos analisar um algoritmo, devemos ter um modelo de implementação que será usada, inclusive um modelo dos recursos dessa tecnologia e seus custos. Faremos uma suposição de um modelo de computação genérico com um único processador, a RAM, como nossa tecnologia de implementação e entenderemos que nossos algoritmos serão implementados sob a forma de programas de computador. O modelo de RAM contém instruções comumente encontradas em computadores reais.
Os tipos de dados no modelo de RAM são inteiros e de ponto flutuante. Embora normalmente não nos preocupemos com a precisão neste livro, em algumas aplicações a precisão é crucial. Vários modelos computacionais tentam levar em conta os efeitos da hierarquia de memória, que as vezes é significativa em programas de máquinas reais.
Embora normalmente selecionemos apenas um único modelo de máquina para analisar um determinado algoritmo, ainda estaremos diante de muitas opções na hora de decidir como expressar nossa análise. Um objetivo imediato é encontrar um meio de expressão que seja simples de escrever e manipular, que mostre as características importantes de requisitos de recurso de um algoritmo e que suprima os detalhes tediosos.
Análise da ordenação por inserção
O tempo de duração de um algoritmo cresce com o tamanho da entrada, assim, é tradicional descrever o tempo de execução de um programa como uma função do tamanho de sua entrada. Para isso, precisamos definir os termos “tempo de execução” e “tamanho da entrada” como mais cuidado. A melhor noção de tamanho da entrada depende do problema que está sendo estudando, como a ordenação ou o calculo de transformações discretas de