Algoritmos e como analisar sua complexidade
Os algoritmos estão basicamente em todas as tarefas que realizamos no dia a dia. Muitos deles executamos no “automático”, sem sequer perceber “o que” ou “como” estamos fazendo. No desenvolvimento de software não é assim tão diferente. Mas afinal, o que são algoritmos? E por que é importante analisar a complexidade deles?
É o que veremos neste post! :)
O que é um Algoritmo?
Um conjunto de passos necessários para realizar uma tarefa.
Não são só os programas de computador que executam algoritmos, eles também são executados e implementados por nós, humanos.
Por exemplo, você já pensou no algoritmo que executa para alguma das tarefas abaixo?
- Escovar os dentes
- Tomar banho
- Cozinhar
- Dirigir de casa para o trabalho
No nosso dia a dia, executamos uma série de passos para completar pelo menos uma das tarefas acima. Pegando como exemplo a tarefa Dirigir de casa para o trabalho, os meus passos são basicamente os seguintes:
- Pegar meu carro
- Dirigir até a casa dos meus amigos para dar carona
- Dirigir até o local do escritório onde trabalho
- Deixar meu carro no estacionamento
Esse é o conjunto de passos necessários (algoritmo) que eu executo para concluir esta tarefa.
Agora pense no conjunto de passos necessários que você executa para concluir essa mesma tarefa. Muito provavelmente é bem diferente do meu. Os nossos algoritmos podem ser diferentes, mas o nosso objetivo é o mesmo.
Nos programas de computador isso não é diferente: existem diversos algoritmos que realizam uma série de tarefas e muitas das vezes nem nos preocupamos em saber como são, somente os usamos (me incluo nisso).
Por exemplo, como deve ser o algoritmo que o Google Maps ou Waze usam para calcular a melhor rota de um local a outro? Como deve ser o algoritmo que faz o Netflix sugerir filmes e séries com base no que já assistimos?
Eu particularmente não sei como é, mas sei que é eficiente. E é nesse ponto, da eficiência, que a análise da complexidade entra.
O que é a Complexidade de Algoritmos?
Em ciência da computação, a complexidade de algoritmos se refere ao quanto de tempo e memória um algoritmo consome para executar uma tarefa de acordo com o tamanho da sua entrada.
Em geral, são avaliados o consumo de tempo e memória, porém neste post falarei somente da complexidade de tempo.
Analisando a complexidade de tempo, conseguimos determinar como um algoritmo se comportará dado o crescimento dos seus elementos de entrada. Podemos ter uma noção do tempo que levará para processar 10, 100 ou 1000 elementos.
E por que essa análise é importante?
- Para conseguir determinar qual algoritmo é mais eficiente
- Para conseguir desenvolver algoritmos mais eficientes
- Para conseguir analisar se o algoritmo de uma biblioteca, ou até da própria linguagem que está sendo usada, é eficiente
Enfim, o foco é na eficiência!
Complexidade de Tempo
É o tempo que uma atividade leva para ser concluída.
Começarei analisando o tempo usando o método Frequency Count, que basicamente em contar o número de vezes que um passo é executado, onde para cada passo é atribuído uma unidade de tempo, que começa com o valor 1.
O tempo que um algoritmo leva é expressado pela função f(n), tal que n é o tamanho dos dados.
O resultado de uma análise é expressado da seguinte forma:
([função que expressa tempo]) = [Soma das unidades de tempo]
Vamos analisar alguns algoritmos e entender na prática como funciona.
A primeira função efetua a soma de dois números inteiros:
Podemos ver que para tal tarefa, o algoritmo implementado executa apenas um passo: a soma dos dois números. Como para cada passo atribuímos uma unidade de tempo, o resultado é f(n) = 1.
Vamos analisar o próximo exemplo, um algoritmo que divide um número inteiro por outro número inteiro:
Apesar de também ser uma operação matemática como a soma, o algoritmo de divisão contém alguns passos a mais porque é necessário verificar se o divisor é 0, visto que, se for esse o caso, não é possível realizar a divisão dos números. Como temos um total de quatro passos e atribuímos para cada um deles uma unidade de tempo, temos como resultado f(n) = 4.
Já o próximo algoritmo efetua a soma de todos os elementos de uma lista de inteiros:
Neste algoritmo, um dos passos é o for, uma instrução de repetição;, isso quer dizer que o código dentro do for será executado várias vezes. Como esse número de execuções dependerá do tamanho dos dados, neste caso atribuímos o valor n para a unidade de tempo. Como resultado temos f(n) = 2n + 3.
O próximo algoritmo efetua a soma dos elementos de uma lista com os de uma segunda lista.
Como resultado temos f(n) = 2n² + 2n + 3.
Até aqui vimos somente algoritmos simples, certo? Agora imagine analisar algoritmos bem mais complexos e ter que fazer todos estes cálculos? Meio inviável, né? Embora pareça ser o mais apropriado, é uma maneira muito trabalhosa e no fim não vale a pena.
Geralmente, a intenção quando estamos analisando um algoritmo, é saber como ele se comportará nos casos em que temos muitos elementos para processar. São nessas situações que precisamos encontrar o termo predominante da soma.
Por exemplo, qual é o termo predominante da soma para o terceiro algoritmo?
f(n) = 2n + 3
Neste caso, o termo predominante é 2*n, explicarei o porquê!
Em qualquer situação onde n for maior que 1 (n>1), o produto (resultado da multiplicação) já valerá mais que o segundo termo da soma.
Faça um teste, substitua n por qualquer valor maior que 1 e resolva a multiplicação.
E o termo predominante da soma para o último algoritmo?
f(n) = 2n² + 2n + 3
Neste caso, o termo predominante é 2*n², porque quando n > 1, o produto já valerá mais do que o segundo e terceiro termo da soma. Faça o teste também!
Por isso, existe uma forma mais comum, por assim dizer, para analisar a complexidade de algoritmos, em que os termos constantes e menos significativos são desconsiderados. Essa forma é a Complexidade Assintótica.
É aqui que entra a Ordem de complexidade, ou Notação-O ou Big-O.
Notação Big-O
Usada para classificar um algoritmo de acordo com a taxa de crescimento das operações à medida que cresce o número de elementos processados.
A notação Big-O também define uma função que expressa a complexidade de tempo de um algoritmo. Para isso é usada a letra O seguida de uma função sobre n.
As classes mais comuns são:
- O(1) — Constante, número de operações não cresce à medida que cresce o número de elementos
- O(log n) — Logarítmico, número de operações é menor que o número de elementos
- O(n) — Linear, o número de operações cresce proporcionalmente ao número de elementos
- O(n²) — Quadrático, o número de operações será maior do que o número de elementos
- O(2^n) — Exponencial, o número de operações cresce muito rápido comparado ao número de elementos
- O(n!) — Fatorial, o número de operações cresce muito, muito rápido, mesmo para um pequeno número de elementos
Abaixo, temos um gráfico que ilustra a Taxa de Crescimento das Operações x Quantidade de Elementos:
Podemos ver no gráfico a seguinte classificação:
- Zona vermelha é horrível, evite!
- Zona laranja é ruim, evite também!
- Zona amarela é justo, razoável!
- Zona verde claro é bom, legal!
- Zona verde escuro é excelente, parabéns!
Com isso, vamos agora usar a notação Big-O para classificar os algoritmos que vimos anteriormente, considerando sempre o termo predominante da soma.
O primeiro algoritmo teve como resultado f(n) = 1, ou seja independente do crescimento dos elementos, o algoritmo executará apenas uma operação. Podemos então definir esse algoritmo como sendo Constante — O(1).
O segundo algoritmo teve como resultado f(n) = 4, ou seja independente do crescimento dos elementos, o algoritmo executará quatro operações. Podemos então definir que esse algoritmo também é Constante — O(1).
O terceiro algoritmo teve como resultado f(n) = 2n + 3, o que significa que o número de operações irá crescer proporcionalmente ao número de elementos, visto que temos o n como variante nesta função. Podemos então definir que esse algoritmo é Linear — O(n).
O último algoritmo teve como resultado f(n) = 2n² + 2n + 3, ou seja, o crescimento das operações será maior que o número de elementos. Também temos o n como variante nesta função, porém nesse caso há um termo elevado à segunda potência (quadrado). Podemos então definir que esse algoritmo é Quadrático — O(n²).
A tabela abaixo uma tabela ilustra o crescimento do número de operações de acordo com o crescimento do número de elementos.
Perceba que para 16 elementos, em um algoritmo exponencial, serão executadas no mínimo 65.536 operações. Bem preocupante, certo?
Em geral, o processo de análise é o mesmo que fizemos anteriormente, contando o número de passos e identificando o termo predominante.
Algumas tendências que podemos observar:
- Algoritmos sem laço de repetição tendem a ser Constantes — O(1)
- Algoritmos que tenham laços de repetição, mas não aninhados, tendem a ser Lineares — O(n)
- Algoritmos que tenham dois laços de repetição aninhados, tendem a ser Quadráticos — O(n²)
- O acesso direto pelo índice de um array, geralmente é O(1).
- Métodos de extensão das listas, em média são O(n). Por exemplo: any, sum e filter.
- Algoritmos de ordenação como Bubble Sort, Insertion Sort e Selection Sort em média são O(n²).
Conhecer essas classes e saber como classificar os algoritmos nos dá a capacidade de determinar o quanto um algoritmo é bom ou ruim, eficiente ou ineficiente. Claro que não conseguimos medir o tempo exato em segundos, minutos ou horas. Até porque para isso precisaríamos executar, medir e alterar. Imagine fazer isso para algoritmos que levam horas ou até dias? Sem chances!
Então, espero que eu tenha cumprido o objetivo deste post, que foi de dar uma visão geral do que são os algoritmos e como analisamos sua complexidade, usando o método Frequency Count e a notação Big-O.
Abaixo deixo algumas referências para leitura e estudo!
Referências:
Vídeos 1 à 1.7
Tem interesse em trabalhar conosco? Nós estamos sempre procurando por pessoas apaixonadas por tecnologia para fazer parte da nossa tripulação! Você pode conferir nossas vagas aqui.
