Introdução à Análise de Algoritmos

Análise de Algoritmos: Complexidade Temporal e Espacial
Introdução
Nem todos os programas requerem o mesmo esforço computacional, seja em tempo seja em memória. Entre programas que resolvem o mesmo problema há uns mais exigentes que outros.
Existem vários critérios para medir um programa, por exemplo, pode ser possível criar uma classificação baseada no número de instruções ou nas transferências de memória secundária para memória primária. Para tal, vamos considerar dois conceitos relevantes: o tempo que o programa demora a ser executado e o espaço em memória que o programa necessita para ser executado. À esta avaliação dá-nos o critério a complexidade temporal e a complexidade espacial do programa em questão.

Análise de Programas
A complexidade temporal de um programa pode ser determinada analisando a sua estrutura. Como uma linguagem de programação possui uma sintaxe e uma semântica bem definidas, a tarefa de analisar a estrutura de um programa dessa linguagem é facilitada. Considera-se o pior caso, i.e., escolhe-se sempre a opção que implique o número máximo de instruções.
Existem diferentes formas de avaliar as exigências de um programa:
1. Forma empírica – consiste na observação efectiva do programa;
2. Forma experimental – baseado na criação de um modelo simplificado do problema de forma a estimar o comportamento;
3. Forma analítica – demonstração da existência de uma função matemática que calcule as exigências do programa em relação aos parâmetros do problema.
Consideremos um problema P com parâmentros D e um programa que resolve P. após N experiências com a mesma dimensão de dados mas com valores diferentes é possível estimar os recursos gastos em termos do melhor caso, do pior caso ou da média dos casos observados.
Exemplo: considere-se um programa para ordenar (em ordem crescente) um conjunto de elementos guardados num vector. Pode-se obter informação observando o tempo gasto pelo programa a ordenar diferentes vectores. Escolhemos um número