Algoritmo

Algoritmo: Qualquer procedimento computacional bem definido que toma algum valor ou conjunto de valores como entrada e produz algum valor ou conjunto de valores como saída (Cormen, 2002). Estrutura de dados: Quando os dados obtidos na entrada do algoritmo são dispostos e manipulados de forma homogênea no processo de computação de sua saída, trata-se de tipo abstrato de dados. Uma estrutura de dados é um meio para armazenar e organizar dados com o objetivo de facilitar o acesso e as modificações (Cormen, 2002). Todos os problemas a serem resolvidos por algoritmos possuem dados. Estes são armazenados em estruturas, escolhidas de acordo com as operações que podem ser realizadas sobre elas e com o custo de cada uma dessas operações. O que é análise de algoritmos? Segundo Cormen (2002), é a previsão dos recursos de que o algoritmo necessitará.

- Memória.

- Largura de banda de comunicação.

- Hardware de computação.

- Tempo de computação.

Envolve dois tipos de problemas distintos: - análise de um algoritmo particular: calcular o custo de um determinado algoritmo na resolução de um problema. - análise de uma classe de algoritmos: determinar o algoritmo de menor custo possível para resolver um problema. Modelo RAM: - Instruções executadas uma após a outra, sem operações concorrentes. - Instruções encontradas em computadores reais, tais como instruções aritméticas, de movimentação de dados e de controle. Tempo de execução de um algoritmo: função de custo T, onde T(n) é a medida do tempo necessário para executar um algoritmo para um problema de tamanho n. Um algoritmo nem sempre se comporta de modo uniforme, podendo identificar três casos: Pior caso = maior tempo de execução sobre todas as entradas de tamanho n. Melhor caso = menor tempo de execução sobre todas as entradas de tamanho n. Caso médio = média dos tempos de execução sobre todas as entradas de tamanho n. O tempo de execução de um algoritmo aumenta proporcionalmente ao tamanho da entrada n