Análise de algoritmos

Em Ciência da computação, a análise de algoritmos tem como função determinar os recursos necessários para executar um dado algoritmo. A maior parte dos algoritmos estão pensados para trabalhar com entradas (inputs) de tamanho arbitrário. Em geral, a eficiência ou complexidade de um algoritmo é função do tamanho do problema, do número de passos necessário (complexidade temporal) e da complexidade espacial ou de memória do sistema usado para executar o algoritmo. Esta disciplina faz parte da mais vasta teoria da complexidade computacional, que permite fazer estimativas quanto aos recursos necessários para que um algoritmo resolva um determinado problema computacional.

Assim, o objetivo final desta é fazer com que os alunos produzam não apenas códigos que funcionem, mas que sejam também eficientes. Para isso, deve-se estudar alguns tipos de problemas que podem ser resolvidos computacionalmente. Em seguida, deve ser visto como a abordagem adotada para resolver pode influenciar, levando a um algoritmo mais ou menos eficiente. A longo prazo, espera-se que o aluno consiga naturalmente compreender quais estruturas e técnicas são mais adequadas para cada problema e as utilize de forma a produzir programas o mais eficientes possível.

"Ao verificar que um dado programa está muito lento, uma pessoa prática pede uma máquina mais rápida ao seu chefe. Mas o ganho potencial que uma máquina mais rápida pode proporcionar é tipicamente limitado por um fator de 10, por razões técnicas ou econômicas. Para obter um ganho maior, é preciso buscar melhores algoritmos. Um bom algoritmo, mesmo rodando em uma máquina lenta, sempre acaba derrotando (para instâncias grandes do problema) um algoritmo ruim rodando em uma máquina rápida. Sempre."

S. S. Skiena, The Algorithm Design Manual[1]