Outro dia participei de uma discussão sobre "O que é a complexidade algorítmica?". Por conta disso, resolvi escrever esse post. Já havia falado sobre complexidade algorítmica entre outros posts deste blog, como neste link, onde falamos sobre o algoritmo de busca binária.
A Teoria da Complexidade Computacional é uma área de conhecimento destinada a avaliação da complexidade de algoritmos.
Esta avaliação trata de analisar o custo computacional de um algoritmo, o qual pode estar relacionado a diferentes fatores, como: tempo de execução, utilização de memória principal, utilização de disco e consumo de energia.
Um algoritmo pode ser tido como solução aceitável quando para qualquer entrada produz uma resposta correta. Entretanto, mesmo resolvendo um problema, um algoritmo pode ser tido como inaceitável, por possuir um custo computacional elevado.
Fernando Henrique Ferreira 