O que é análise de complexidade de um algorítimo?

Propomos um algorítimo com a finalidade de resolver problemas do mundo real. Porém, não é raro haver várias propostas de algorítimos para resolver o mesmo problema. E aí neste caso, qual o melhor algorítimo? Então buscamos mensurar a quantidade de recursos que um algorítimo precisa para funcionar. Recursos de processamento, memória e às vezes, largura de banda são os que primeiro nos vêm à mente. No entanto, quando analisamos um algorítimo é muito importante analisa-lo levando em conta o tempo de computação. No modelo de computação genérico temos instruções pré-definidas como instruções de soma, subtração, divisão, multiplicação, desvio condicional, carregamento, cópia e muitas outras. Cada instrução dessa leva um tempo constante para ser realizada. Mas, há algumas tarefas que precisam ser construídas, como por exemplo a ordenação de números naturais. Para isso precisamos construir um algorítimo que realize a tarefa com as operações que a máquina já contempla. Dessa forma, vários modos de realizar a mesma tarefa surgem, e analisar a complexidade de cada solução se torna necessário para eleger a mais aplicável aos recursos disponíveis. No próximo post trarei um problema de ordenação e uma solução para ele. A partir daí, iremos analisar esta proposta e determinar a sua complexidade. Depois vamos verificar outra proposta, com uma abordagem diferente, analisar sua complexidade, e inferir qual o mais eficiente. Inicialmente, o faremos de uma forma generalista, e depois usando ferramentas luxuosas de medida de complexidade, tratando o algorítimo como um modelo matemático de solução de problemas.

Algorítimos, Cormen, et al, 2012 3ed. capítulo 2.