Análise de espaço e tempo

A análise de complexidade dos algoritmos é importante para definir o custo inerente a eles. Desta forma, dado um problema pode-se definir qual é a melhor solução para ele. Todo tipo de custo é calculado, mas os principais são o tempo de execução (uso de CPU) - relacionado ao nº de operações que o programa executa - e o espaço ocupado (uso de memória) - relacionado à quantidade de dados.
A análise do espaço é feita de forma muito simples: avaliando a quantidade de variáveis e o espaço ocupado por cada uma delas. O uso eficiente do espaço se dá quando o algoritmo utiliza o espaço da entrada mais uma fração desse valor. O uso pouco eficiente se dá quando o algoritmo utiliza o espaço dos dados da entrada mais uma vez ou mais esse valor.

A análise do tempo pode ser feita de duas formas:

• Medição empírica: mede o tempo do mesmo algoritmo para entradas diferentes. É uma medição muito particular, porque vai depender da capacidade de processamento do computador, do hardware, do sistema operacional, enfim. Muitas coisas. Por ser uma medida tão particular, ela só é válida para o ambiente em que foi feita, apesar de dar o tempo real da execução.
• Medida analítica: determina a quantidade de trabalho para resolver o problema baseando-se na entrada de dados, no algoritmo utilizado e na natureza do problema. O tempo é proporcional à quantidade de instruções executadas (dentre atribuições, operações lógicas, aritméticas, leitura e escrita de dados, condicionais, loops, chamadas a outras funções e combinações de todos esses procedimentos), portanto, conta-se o número de instruções e o custo é dado por uma expressão matemática que tem n (nº de entradas) como parâmetro e resulta no nº de instruções em função de n. Para medir certinho o tempo, basta calcular o tempo médio por instrução e multiplicar pelo nº de instruções.
  
  Exemplo: seja o comando for(i=0; i<N; i++) a[i] = 0; O laço é executado N vezes. Portanto, há 1 atribuição de valor a i (em i=0), N incrementos de i, N+1 comparações para ver se i<N e N atribuições do valor 0 a cada posição do vetor a. Portanto, a inicialização de um vetor é dada por f(n) = 3n + 2; sendo f(n) o número de instruções executadas.

DADO: um computador de 1GHz executa aproximadamente 10^9 instruções por segundo, cada uma com custo médio de 1ns.

Algoritmo ótimo é aquele que cujo custo equivale ao custo mínimo da classe de problemas que ele resolve.