Posted on Mar 11, 2022

Complexidade de Algoritmos

Nos dias actuais, com o avanço do poder de processamento das máquinas, tem se tornado muito difícil assumir que um Software pode ter baixa performance, por causa dos algoritmos utilizados. Nomalmente a culpa é a atribuida a outros factores externos como o Sistema Operativo, a rede, a Linguagem de Programação e o framework utilizado.

O que pode tornar um algoritmo lento?

Um algoritmo pode ter vários factores que influenciam no seu tempo de execução, nas quais podemos destacar:

Iterações;
Acesso a estruturas de dados;
Chamadas recursivas
Leitura e escrita de arquivos;
Leitura e escrita no Banco de Dados;
Requisições para serviços externos;

Como medir o tempo de execução de um algoritmo?

O tempo de execução pode ser medido em qualquer linguagem de programação. As linguagens têm bibliotecas para manipulação do tempo. Podemos criar funções que medem o tempo de execução dos os algoritmos e posteriormente refactorar o código.

Sugestão: A função deve capturar tempo em segundos e no início e no fim de todas instruções e capturar novamente o tempo. O resultado será a diferença entre o tempo final e o tempo inicial. Também podemos criar outras funções auxiliares.
Algumas linguagens (Python, Javascript e PHP) possuem métodos mágicos que permitem chamar dinamicamente e/ou obter as suas propriedades como nome, parâmetros, posição na memória e outros.

Observação: A velocidade de execução do algoritmo pode ser influenciado pelas especifações da máquina. Máquinas mais potentes podem executar algorítmos lentos em menos tempo, comparando com máquinas nenos potentes.

Exemplo: Usando a linguagem Python, vamos calcular o tempo de execução para 2 problemas:

Somar os elementos de uma lista de 60 mil números aleatórios, usando 4 algoritmos diferentes.
Ler de um arquivo CSV de 4 mil registos de registos e salvar no Banco SQLite, usando 3 algoritmos diferentes. No final teremos 12 mil registos (4 * 3 000).

Algoritmo para calcular o tempo