Aula 1 Ferramentas De An Lise

ANÁLISE DE ALGORITMOS – AULA 1
FERRAMENTAS DE ANÁLISE

1

INTRODUÇÃO

As estruturas de dados e os algoritmos são conceitos centrais para a computação, pois se constituem nas ferramentas básicas para a construção de softwares. De forma simples, uma estrutura de dados é a forma pela qual a informação é organizada e armazenada, e um algoritmo é um procedimento, passo a passo, para realizar alguma tarefa em tempo finito.
O quadro-resumo a seguir exibe as etapas na construção de um programa computacional, inserindo as estruturas de dados e os algoritmos no processo de solução de um problema.

MODELO MATEMÁTICO

ALGORITMO INFORMAL

TIPOS ABSTRATOS DE DADOS
(TAD’s*)

ESTRUTURAS DE DADOS

PROGRAMA EM

PROGRAMA

PSEUDOLINGUAGEM

COMPUTACIONAL

∗ TAD é a descrição matemática dos valores que um tipo de dado pode ter e das operações que podem ser feitas com eles.

Como se está interessado em bons algoritmos e estruturas de dados, é importante a definição de ferramentas de análise. A ferramenta básica de análise envolve a caracterização do tempo de execução de algoritmos e operações sobre estruturas de dados, com seu consumo de memória também sendo de interesse.

2

TEMPO DE EXECUÇÃO

Se um algoritmo for implementado, é possível estudar o tempo gasto por ele executando-o com vários dados de entrada e registrando o tempo gasto em cada execução.
Essas medições podem ser feitas de forma precisa usando-se chamadas do sistema que são incluídas na linguagem ou no sistema operacional em que o algoritmo foi implementado.
Em geral, o interesse é determinar a dependência do tempo de execução com respeito ao tamanho da entrada fornecida para o algoritmo. Para determiná-la, podem-se realizar vários experimentos e, por meio de gráficos, relacionar o tamanho da entrada com o tempo de execução medido. Para ser significativa, essa análise exige que sejam escolhidos bons

Página 1 de 11

ANÁLISE DE ALGORITMOS – AULA 1 exemplos de entradas e que sejam feitos testes suficientes para que se