Análise de Algoritmos: Eficiência, Medição e Notação Assintótica

Existem várias maneiras de resolver um problema. Como escolher entre elas? Geralmente, há dois objetivos na concepção de programas de computador:

• A concepção de um algoritmo que é fácil de compreender, codificar e depurar (Engenharia de Software).
• A concepção de um algoritmo que faz uso eficiente dos recursos de informática (Análise e Projeto de Algoritmos).

A análise de algoritmos nos permite medir a dificuldade de um problema e avaliar a eficiência de um algoritmo.

Medindo o Tempo de Execução: Operações Básicas

Não se pode medir o tempo em segundos, pois não há um padrão de computador de referência. Em vez disso, deve-se medir o número de operações básicas ou elementares.

As operações básicas são realizadas pelo computador em tempo limitado por uma constante, por exemplo:

• Operações básicas de aritmética
• Atribuição de tipos predefinidos
• Saltos (chamadas a funções, procedimentos e retorno)
• Comparações lógicas
• Acesso a estruturas básicas (vetores e matrizes)

É possível estudar a complexidade de um algoritmo com base apenas em um pequeno conjunto de sentenças que influenciam o tempo de execução.

Métodos para Medir o Tempo de Execução

Para medir o tempo de execução de um algoritmo, existem vários métodos. Alguns deles são:

a) Benchmarking

A técnica de benchmarking é considerada uma coleção de entradas que representam uma carga de trabalho típica de um programa.

b) Perfil (Profiling)

Associa a cada instrução de um programa um número que representa a fração do tempo total gasto para executar aquela instrução específica. Uma das técnicas mais conhecidas (e informais) é a regra 90-10, que afirma que 90% do tempo de execução é gasto em 10% do código.

c) Análise

Consiste em agrupar as entradas de acordo com seu tamanho e estimar o tempo de execução do programa para entradas desse tamanho, T(n). Esta é a técnica a ser estudada no curso.

Assim, o tempo de execução pode ser definido como uma função da entrada. Denomina-se T(n) o tempo de execução de um algoritmo para uma entrada de tamanho n.

Eficiência Assintótica e Notação

O foco principal da análise de algoritmos está na forma como o tempo de execução cresce quando o tamanho da entrada aumenta. Esta é a eficiência assintótica do algoritmo. É chamado de "assintótico" porque analisa o comportamento de funções no limite, ou seja, sua taxa de crescimento.

A notação assintótica é descrita por uma função cujo domínio são os números naturais (N), que estima o tempo de execução ou o espaço de memória de algoritmos com base no comprimento da entrada. Consideram-se funções assintoticamente não negativas.

A notação assintótica capta o comportamento da função para valores grandes de N.

As notações assintóticas não dependem dos casos específicos (melhor, médio, pior) de execução, por isso uma notação que determina o pior caso pode ser aplicada em diversas situações.