Como calcular a complexidade de algoritmos?

Um dos assuntos mais interessantes que todos os programadores, iniciantes deveriam focar, sem dúvidas tem relação com saber calcular Complexidade de Algoritmos. Este tema tem relação direta com o estudo de Estrutura de Dados, que tem por finalidade estudar os métodos de organização e acesso a grandes volumes de dados.

Certamente você já utilizou Pilhas, Listas e Filas eu seus algoritmos. Estas são estruturas de dados. Para você entender mais sobre este tema, fiz um artigo com mais detalhes sobre estruturas de dados, Estruturas de Dados: Listas, Filas, Pilhas, Conjuntos, Árvores e Hash Tables . 

Então, para que serve a complexidade de algoritmos?

Ao manipular estas estruturas de dados, você precisará de algoritmos para efetuar inserção, remoção e ordenação dos seus elementos. A coisa fica séria quando o volume de dados é muito grande e a quantidade de operações que são feitas sobre estas estruturas se tornam custosas, em questões de tempo e recursos computacionais.

Não preciso nem falar que estamos na era do Big Data, onde estamos produzindo muitos dados o tempo todo. Então, temos que saber calcular o quanto complexo está nossos algoritmos para manipular estas estruturas à medida que essas estruturas aumentam de tamanho de forma expressiva.

Este assunto é tão importante, que é uma área de estudo dentro do ramo da programação de computadores com notação matemática exclusiva, de modo que conseguimos ter uma forma de representar os nossos experimentos de análise de forma que todos possam entender os resultados obtidos. Por ser um assunto um pouco mais técnico, separei-o no artigo Análise de Complexidade de Algoritmos, que é obrigatório para a compreensão de como calcular uma complexidade de algoritmo.

Como calcular Complexidade de Algoritmo?

Entendendo bem essa parte conceitual, você estará apto a mergulhar na prática. Para efetuar os cálculos, você utilizará praticamente 2 métodos :

• Empírico (experimental): Cálculo efetuado a partir de testes de implementação do algoritmo.
• Analítico (teórico): Onde você vai calcular a função de complexidade, onde temos função t = f(n) onde t é o total de tempo de processamento e n é o tamanho da entrada. 

O Método Empírico, é o que comumente a grande maioria utiliza. Onde se observa o tempo de execução do código, implementado na linguagem de programação de sua escolha.

O Métodos Analíticos, não considera estes fatores de ambiente, o foco é representar em uma ordem de grandeza o tempo de execução do algoritmo. Ou seja, observamos o tamanho da entrada e analisamos quais operações vão ser executadas em nosso algoritmo, de modo que consigamos representar uma função que nos mostre qual o resultado em condições, favoráveis ou não, podem deixar nossos algoritmos com desempenho melhor ou pior, dependendo da variação do tamanho da entrada (tamanho n).

Como citado, a complexidade dos algoritmos podem ser calculada através dos fatores de tempo de execução e espaço:

• Tempo de execução: Que é determinado pelas instruções executadas. Ou seja, quanto “tempo” é necessário para computar o resultado para uma instância do problema de tamanho n 
• Espaço de memória utilizado: Calcula quanto “espaço de memória/disco” é preciso para armazenar a(s) estrutura(s) utilizada(s) pelo algoritmo.

Na prática, além dos pontos citados aqui, vamos precisar entender outros aspectos dos nossos algoritmos que impactam diretamente no cálculo em si, como é o caso da ordenação.  No artigo Como calcular Complexidade de Algoritmo na prática, além destes pontos que citei, trago alguns exemplos práticos com códigos, que te ajudarão na elaboração dos resultados dos cálculos que você vai efetuar.

Reconheço que este tema não é tão simples, porém é de suma importância que você domine pelo mesmo seus fundamentos e cálculos. Se seu objetivo é concorrer a vagas mais especializadas, você precisará dominar o assunto.

Agora me conta um pouco sobre você… Você utiliza cálculo de complexidade de algoritmos em seus projetos? Qual a sua experiência neste tema? Deixe aqui seu comentário com algum “case” que possa ajudar outras pessoas a evoluírem nas suas jornadas profissionais. Vai ser bom para elas e muito melhor para você! Até o próximo artigo!

Confiança Sempre!!!

Fontes:

• https://pt.khanacademy.org/computing/computer-science/algorithms/asymptotic-notation/a/big-o-notation
• http://docente.ifsc.edu.br/vilson.junior/ed/07_Complexidade_Algoritmos.pdf