Complexidade de Algoritmos
Published: 2022-03-11 13:19:45


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
![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/3qw313y6ve69q5v58svh.jpg)

Classe para calcular o tempo

![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/4ksl5dgoedr1fef6nae8.jpg)

Classe para calacular a soma de elementos
![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/1dkd37muprboc16e5mjh.jpg)

Classe para Leitura do CSV
![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/df4qka6wytgwvjyna11n.jpg)

Testando a soma de Elementos
![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/egrkqvsh2kjhpo9mxpzs.jpg)

Ficheiro CSV com 4 mil registos
![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/6phbknaf5o8j2dnpdhb0.jpg)

Testando CSV
![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/s5msrk6op65wmi9vpwks.jpg)

Base de dados Final
![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/h5z68vb836c8etu2mj3j.jpg)

Código disponível em: https://github.com/ortizdavid/algorithm-complexity
Para mais artigos:
- https://www.dev.to/ortizdavid
- https://www.medium.com/@ortizaad1994