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.

Existem diferentes motivações para o estudo da complexidade computacional. A preocupação com a complexidade de algoritmos é fundamental para projetar algoritmos eficientes, mas o melhor caminho é ter a preocupação de projetar algoritmos eficientes desde a sua concepção. Também é importante salientar que sempre que criado um algoritmo é preciso analisar a sua complexidade para verificar a sua eficiência, para garantir que além de eficaz o algoritmo execute da maneira mais eficiente possível.

Para garantir a eficiência de um algoritmo é preciso realizar testes e experimentos deste algoritmo, algo que chamamos de avaliação empírica. Uma avaliação empírica corresponde à observação direta do comportamento do algoritmo, através da execução de testes com diferentes conjuntos de dados de entrada e avaliação dos resultados.

Como avaliar a eficiência?

Para expressarmos a eficiência de um algoritmo costumamos usar medidas como o tempo de execução ou o espaço (leia memória) usado. Apesar de o tempo ser bastante utilizado, medir o tempo absoluto (minutos, segundos, milésimos) não é a melhor escolha, pois o resultado pode variar conforme a configuração da máquina executando os testes e isso pode afetar a reprodução dos experimentos. Máquinas mais potentes executam um algoritmo em menor tempo, se comparados os resultados com máquinas menos potentes. Mas, caso os seus testes sejam feitos em um mesmo ambiente, compartilhando a mesma configuração, este é um fator a ser levado em consideração.

Geralmente, para expressar o custo de um algoritmo, contamos o número de operações relevantes executadas pelo algoritmo. Essas operações podem ser comparações, operações aritméticas, movimentos de dados, etc. O número de operações existentes em um algoritmo é representado por uma função de n.

O número de operações realizadas por um algoritmo depende diretamente do conjunto de entrada empregado para sua execução. Diferentes entradas podem acarretar em diferentes execuções, assim, resultando em custos diferentes. Desta forma, nos interessa o pior caso, o caso no qual o maior número de operações é utilizada para qualquer entrada de tamanho n.

Meios de medir a complexidade de um algoritmo.

Existem três maneiras de avaliar a complexidade de um algoritmo com entradas de mesmo tamanho (uma vez que entradas de tamanho n podem ser mais rápidas para resolver do que outras):

– Melhor caso: é o melhor caso para resolver um problema de tamanho n.

– Pior caso: pior caso para resolver um problema de tamanho n.

– Caso médio: complexidade para resolver o problema de tamanho n. Este caso só é definido com relação a uma distribuição de probabilidade sobre as entradas, isto é, se todas as entradas do mesmo tamanho são consideradas de terem a mesma probabilidade de aparecer, então a complexidade do caso médio é definida com à distribuição uniforme de todas as entradas de tamanho n.

A complexidade adotada para um algoritmo é entendida como a de pior caso, por ser o limite (ou aquilo que consideramos como "o máximo esperado a ser atingido").

Eficácia vs. Eficiência

Outro ponto importante é entender a diferença entre eficácia e eficiência. Ambos parecem ter o mesmo sentido, mas são diferentes e muitas vezes são empregados de maneira incorreta, sendo:

– Eficácia: trata-se de fazer algo corretamente. Se o seu algoritmo faz o que deve (em outras palavras, "se ele resolve um problema" em um tempo finito com recursos finitos) então seu algoritmo é eficaz.

– Eficiência: trata-se de fazer algo da melhor forma possível, no caso da computação isso está associado ao fato de resolver algo consumindo a menor quantidade de recursos computacionais e em menor tempo. Existem diferentes algoritmos para resolver um mesmo problema, mas cada um destes algoritmos consome de maneira diferente recursos computacionais.

Na minha opinião, não existe algoritmo eficiente que não sejaz eficaz. Se o algoritmo é eficiente e não faz aquilo que deveria fazer corretamente, então sua execução não é justificável.

 

FH