Introdução à Complexidade de Algoritmos
Algoritmos e estruturas de dados são temas frequentemente ignorados por diversas pessoas da área de desenvolvimento e engenharia de software, desde universitários aos programadores mais experientes. Os principais argumentos utilizados giram em torno do fato de que "as linguagens de programação e frameworks atuais já implementam os algoritmos da maneira mais eficiente" ou de que "os recursos de hardware disponíveis hoje (como memória e processador) tornam a preocupação com algoritmos desnecessária".
Hoje em dia também existe uma discussão muito recorrente sobre linguagens de programação serem melhores ou mais rápidas que outras. Apesar de uma poder ser melhor que outra em situações diferentes, de nada importa se a pessoa que estiver escrevendo o código não tiver uma noção fundamental de algoritmos.
Neste post falarei sobre o que é um algoritmo, a importância de estudá-los e apresentarei brevemente um dos temas mais importantes da Ciência da Computação para engenharia de software: Análise de Complexidade de Algoritmos.
Algoritmos
No mundo da ciência da computação, algoritmos são processos computacionais bem definidos que podem receber uma entrada, processá-la e produzir um ou mais valores como saída.
Alguns exemplos de problemas que envolvem algoritmos comuns são:
- Calcular a rota mais curta entre duas ruas
- Contar o número de amigos em comum em uma rede social
- Organizar de maneira eficiente tarefas de acordo com sua prioridade, prazo e duração
- Organizar a lista de contatos por ordem alfabética
- Encontrar uma mensagem no histórico de conversas
De forma geral, podemos pensar em algoritmos como uma ferramenta para resolver um problema bem definido. A definição de um problema se baseia em um conjunto de dados que se deseja processar, com suas especificidades, e o resultado que é desejado alcançar.
Como podemos perceber, existem diversos problemas que podem ser resolvidos utilizando algoritmos. Não existe uma "bala de prata" para resolvê-los de maneiras eficiente. Porém existem categorias nas quais os problemas e seus subproblemas podem ser classificados. Abstraindo o problema, podemos identificar a sua categoria e aplicar técnicas específicas conhecidas para resolvê-los da maneira mais eficiente.
Algumas das principais categorias/técnicas são:
- Greedy Algorithms
- Dynamic Programming
- Divide and conquer
- Backtracking
- Search and Sorting
Existem também Estrutura de Dados que são utilizados nessas e outras técnicas para ajudar na eficiência desses algoritmos. Como por exemplo: (Grafos, Árvores, Heaps, Tabelas Hash, Pilhas e Filas)
Eficiência dos algoritmos
Já sabemos que existem diversas ferramentas parar analisar a performance de um programa, os conhecidos Profilers. Porém, apesar de sua eficiência, eles não são úteis para Complexidade de Algoritmos. Complexidade de Algoritmos analisa um algoritmo em "nível de idealização/definição"— isto é, ignorando qualquer implementação de linguagens específicas ou hardware. Nós queremos comparar algoritmos em termos do que eles são: Ideias de como algo é computado.
Comparar o tempo que algoritmos levam para executar em milissegundos não são parâmetros para dizer que um algoritmo é melhor que o outro.
É possível que códigos mal escritos em Golang rodem muito mais rápido (até certo ponto) do que o mesmo código escrito em C# ou Java.
Vamos analisar duas soluções para o famoso problema Two Sum, que verifica se existem 2 números cuja soma resulte na entrada específica (alvo) e retorna as posições dos números encontrados:
Rodando as duas soluções com o arrays de até 1000 elementos, o algoritmo em Go é muito mais rápido que Kotlin, demorando apenas alguns nanosegundos para encontrar o resultado, enquanto Kotlin demora poucos milisegundos na maioria dos casos.
Será que podemos afirmar que o algoritmo em Go é melhor que o em Kotlin?
Para isso, precisamos definir o que realmente é um “algoritmo melhor”.
Podemos dizer que o melhor algoritmo para resolver um problema é aquele que possui a menor complexidade de tempo e espaço. Em outras palavras, é o algoritmo que, conforme a entrada cresce tendendo ao infinito, é aquele que apresenta a menor variação de tempo e memória utilizada para terminar.
Rodando os mesmos algoritmos com entradas variando de 0 a 1 milhão e extraindo o tempo de execução podemos montar o seguinte gráfico:
Conforme a entrada cresce, o tempo de execução em Kotlin varia muito pouco, apresentando valores entre 0 e 234 milisegundos. Já Go, apresenta tempos de execução entre 0 e 15 minutos com entradas muito grandes.
Um algoritmo pode ser melhor que outro quando processa poucos dados, porém pode ser muito pior conforme o dado cresce.
A Análise de complexidade nos permite medir o quão rápido um programa executa suas computações. Exemplos de computações são: Operações de adição e multiplicação; comparações; pesquisa de elementos em um conjunto de dados; determinar o caminho mais curto entre diferentes pontos; ou até verificar a presença de uma expressão regular em uma string.
Claramente, a computação está sempre presente em programas de computadores.
Entender este conceito permitirá que continue estudando algoritmos com um melhor entendimento da teoria por trás deles.
Contando Instruções
Para começar a entender a análise de complexidade de algoritmos, precisamos conseguir identificar superficialmente o número de instruções que um algoritmo possui.
O maior elemento de um array de N elementos pode ser encontrado com o seguinte algoritmo:
Agora, a primeira coisa que deveremos fazer é contar quantas instruções fundamentais este código executa. Primeiro, separaremos o código em pequenas instruções e consideraremos que o processador as executem como uma instrução cada.
A primeira instrução é uma atribuição do primeiro elemento da lista à uma variável que será utilizada para ser comparada com os outros elementos da lista e armazenar o maior elemento.
maior := lista[0]
Após isso, o loop será inicializado indice := 0 e seu bloco será executado caso o array não seja vazio.
Após isso temos duas instruções:
indice := 0
indice < n
E ao final de cada laço teremos mais duas instruções:
indice++ que incrementa o contador do loop e
indice < n que verifica se o loop já percorreu todo o array.
Desconsiderando o corpo do for-loop podemos definir uma função matemática f(n) que, dado um n, nos mostra o número de instruções que o algoritmo precisará.
Desconsiderando o corpo do loop, chegamos à função :
f(n) = 4 + 2n.
Análise de pior caso
Considerando o corpo do loop, temos um acesso a um array e uma comparação (2 instruções), porém caso o elemento atual seja maior que o maior elemento até o momento, teremos mais um acesso ao array e uma atribuição (+2 instruções). Isso torna um pouco mais difícil de definirmos uma função para o número de instruções.
Já percebemos que o número de instruções executadas varia de acordo com a entrada.
Na maioria das vezes quando vamos analisar um algoritmo temos que pensar em qual é o cenário onde o nosso algoritmo precisaria do maior número de instruções para executar. Nesse caso, é quando o vetor estiver ordenado. Caso o array esteja ordenado [1,2,4,5,6], o código dentro do if executará em toda iteração. Enquanto para a entrada [5,6,3,5,1,2] ele só executaria uma vez.
Cientistas da computação chamam isso de Análise de Pior Caso.
Então, no pior caso, nós temos 4 instruções dentro do laço de repetição. No final, podemos chegar na seguinte função que nos dá o número de instruções necessárias no pior caso para o algoritmo:
f( n ) = 4 + 2n + 4n = 6n + 4
Comportamento Assintótico
Seria uma tarefa muito maçante ficar contando o número de instruções para cada trecho de código que escrevemos. Além de que o número de instruções varia muito de linguagem para linguagem, compiladores e até mesmo o processador que estamos utilizando.
Na análise de complexidade nós apenas nos importamos com o termo que mais cresce de acordo com a entrada. Para chegarmos nesse termo, podemos remover todas as constantes e manter o termo que mais cresce.
Na função f(n) = 6n + 4, claramente, 4 continua 4 independentemente da entrada, porém 6n fica cada vez maior. Removendo ele ficamos com a função f(n) = 6n.
Como o número 6 é uma constante, podemos removê-lo e chegar na função f(n) = n. Isso simplifica muito a análise da complexidade do algoritmo.
Agora, vamos encontrar o comportamento assintótico das seguintes funções:
- f(n) = 5n + 12 nos dá f(n) = n
Pelo mesmo motivo do exemplo anterior. - f(n) = 915 nos dá f(n) = 1
Estamos removendo o multiplicador 915 * 1 - f(n) = n² + 2n + 300 nos dá f(n) = n²
Aqui, o termo n² cresce mais rápido do que 2n - f(n) = n² + 2000n + 5929 nos dá f(n) = n²
Mesmo que o fator antes de n é bem grande, podemos encontrar um valor para n onde n² se torna maior que 2000n.
Complexidade e Notação Big-O
Para descrever o comportamento assintótico de um algoritmo, cientistas da computação adotaram a Notação Big-O. Ela é utilizada para delimitar assintóticamente o crescimento (tempo ou espaço) superior do algoritmo.
Utilizando o algoritmo para encontrar o maior elemento como exemplo, podemos encontrar casos de entrada que fará ele executar um número menor de operações. Não é para todo caso de entrada que sua função para o número de instruções será f(n).
Utilizando a notação Big-O, podemos dizer que a complexidade do algoritmo é "Big-O de O(n)", ou seja, no pior dos casos cresce em ordem de n.
Para algoritmos simples, é muito fácil de identificar a complexidade do algoritmo. Geralmente, quando um algoritmo possui apenas 1 laço de repetição sua complexidade é O(n), quando possui 2 laços encadeados O(n²) e nenhum laço de repetição O(1). Mas cuidado, isso nem sempre se aplica!
Complexidade de espaço
Todas as análises feitas até agora foram em função do número de operações que os algoritmos requerem, e isso é o equivalente à complexidade de tempo.
A complexidade de espaço de um algoritmo não é muito diferente da complexidade de tempo em questão de análise, e também utilizamos a notação Big-O.
Para analisar a complexidade de espaço de um algoritmo devemos identificar o quanto de memória nosso algoritmo precisa alocar para resolver o problema no pior dos casos.
Analisando alguns algoritmos
Vamos analisar novamente os algoritmos utilizados para resolver o Two Sum no começo desse post.
Exemplo Two Sum em Kotlin
Para cada um dos itens do array, caso o item atual não esteja no mapa, ele é adicionado, e caso a diferença do elemento atual com o target já estiver no mapa, o elemento que faltava para a soma ser igual ao target é encontrado.
O algoritmo requer, no pior dos casos, que todos os itens do array sejam percorridos e adicionados no mapa. Como o acesso e adição no mapa são constantes (O(1)), sua complexidade de tempo é O(n).
Podemos dizer que ele utiliza n espaços de memória extra (1 entrada no mapa para cada um dos elementos do array). Sendo assim, sua complexidade de espaço também é O(n).
Exemplo Two Sum em Go
O algoritmo feito em Go é um pouco diferente.
Para cada um dos itens do array, todos os elementos do array são percorridos novamente. Caso a soma dos dois elementos atuais seja igual ao target, o valor é retornado. No pior dos casos, o algoritmo deverá percorrer n*n vezes o array para informar que não existem 2 elementos que somados resultam no target. Por isso, sua complexidade de tempo é quadrática (O(n²)).
Como essa solução não aloca nenhum espaço extra, podemos dizer que sua complexidade de espaço é constante (O(1)).
Busca binária — O(log n) tempo e O(1) espaço.
O algoritmo de busca binária consiste em retornar o índice do elemento procurado em um array ordenado, caso ele exista.
O algoritmo começa verificando se o elemento buscado está na posição inicial. Caso positivo, retorna sua posição.
Caso o elemento na posição do meio for menor que o elemento buscado, ele aplica o mesmo algoritmo considerando a posição do meio como inicial. E caso o elemento na posição do meio for maior que o elemento buscado, ele aplica o algoritmo considerando a posição do meio como final.
Esse algoritmo se repete até que o elemento procurado seja encontrado ou caso a posição inicial for a mesma que a final.
A cada iteração no loop, o número de elementos a serem percorridos cai pela metade. Por isso, complexidade te tempo é logarítmica (O(log n)).
Como o algoritmo só requer uma variável extra para rodar (mid) sua complexidade de espaço é O(1). As variáveis arr, begin, end e x já estavam alocadas, e por isso não influenciaram na complexidade de tempo.
Merge Sort — O(n log n) tempo e O(n) espaço
O algoritmo Merge Sort utiliza a técnica Divide and Conquer. Durante sua execução, o array de entrada é dividido em duas metades, e a função mergeSort é chamada recursivamente para cada uma delas, intercalando as duas metades de forma ordenada no final.
Analisar a complexidade do merge sort é um pouco mais complexo.
Mas basicamente, podemos dizer que o tempo para executar o mergesort é igual ao tempo para ordenar o lado esquerdo + o tempo para ordenar o lado direito + tempo para mesclar as duas metades (c).
E quando o tamanho da entrada for 1, ele demora um tempo constante.
A partir disso, podemos chegar na seguinte equação de recorrência:
Resolvendo a equação, é possível chegar na complexidade de tempo O(n log n).
Para entender sua complexidade de espaço, vamos utilizar uma árvore representando o espaço que o algoritmo precisa a cada chamada de função.
Devido ao fato do merge sort utilizado nesse exemplo não executar em paralelo, sua execução acontece de uma maneira parecida com um Depth First Traversal (ou busca em profundidade). Dessa forma, apenas um "galho" da árvore será expandido por vez, durante a stack de recursão, e o número de espaço extra utilizado será de no máximo 3n.
A stack de execução acontecerá da seguinte forma:
Somando os números destacados, temos o valor 16 + 8 + 4 + 2 +1 +1 = 32 (equivalente a 2n).
E em seguida:
Cuja a soma é: 16+8+4+2+ 2+1+1 = 34.
E assim por diante. Até que no final do algoritmo teremos os seguintes valores extra em memória:
Essa é a ultima stack de execução e é onde o algoritmo tem alocado um maior número de espaço extra. Todos os arrays mesclados anteriormente ainda estão em memória.
No final chegamos no seguinte valor:
16 + 8 + 8 + 4 + 4 + 2 + 2 + 1 + 1 = 46.
Se analisarmos casos com valores de entradas maiores, é possível perceber que o espaço extra para todos os casos não passa de 3n.
Analisando assintóticamente, este valor é equivalente a O(n).
Abstração das linguagens de programação
Como mencionado no começo desse post, a maioria das linguagens de programação utilizadas hoje já implementam diversas estruturas de dados e algoritmos conhecidos de forma eficiente. Mesmo assim, precisamos conhecer, ou ter uma ideia, dos algoritmos que são utilizados na implementação das funções das linguagens que estamos utilizando.
É muito comum encontrar códigos no dia a dia que utilizam estruturas de dados incorretas como parte de um algoritmo e utilizam suas funções como se o custo delas fossem "grátis".
O código a seguir utiliza a função in do python de uma lista n vezes para filtrar todos os usuários que estão em uma block list.
A complexidade de tempo do código acima é O(n²).
Verificar se um elemento está presente em uma lista, na maioria das linguagens de programação, possui complexidade O(n). No pior dos casos é necessário percorrer a lista inteira para verificar se o elemento está presente nela.
O código a seguir produz o mesmo resultado, porém de maneira mais eficiente.
A mudança no código é quase imperceptível, mas mesmo assim, foi possível reduzir consideravelmente a complexidade e salvar muitos segundos quando comparado com a solução anterior (lembra-se do exemplo no começo do post?).
O set, em Python, utiliza uma tabela hash em sua implementação. E verificar se um elemento está presente em uma tabela hash tem complexidade O(1) no caso médio. Portanto, a complexidade do código acima é O(n).
A função in, em diferentes estruturas de dados, possui complexidades diferentes.
No dia a dia como desenvolvedor é muito fácil se deparar com um caso semelhante ao algoritmo acima.
Não é necessário conhecer a linguagem de programação muito a fundo para imaginar qual a complexidade que os algoritmos que ela implementa apresentam. Conhecer os principais algoritmos e suas complexidades nos permitem fazer uma melhor análise sobre a eficiência do código que estamos escrevendo. E assim, podemos escrever um código melhor.
Conclusão
Esse post foi apenas uma breve introdução ao tópico de Algoritmos e Complexidade para mostrar a sua importância. Para entender melhor o assunto é necessário estudar mais a fundo cada um dos tópicos citados, além de vários outros, utilizando recursos apropriados.
Implementar algoritmos de maneiras eficientes continua sendo de extrema importância para conseguir construir aplicações que permitam com que o produto seja escalável e o usuário tenha uma boa experiência.
Conforme o tempo passa, apesar dos recursos de hardware ficarem cada vez mais baratos e eficientes, surge cada vez mais a necessidade de processar um número maior de dados.
Não é a toa que as maiores empresas de tecnologia, como Google, Facebook e Amazon possuem processos seletivos que avaliam rigidamente o nível do conhecimento em algoritmos de seus candidatos.
Mas é claro, "algoritmos" não é o tópico mais importante para um profissional da área dominar. De nada adianta dominar a fundo algoritmos sem conseguir escrever um Código Limpo, sem saber construir um sistema, sem saber trabalhar em equipe, ou até mesmo, sem ter uma visão do negócio onde está atuando.
Aqui esta um repositório que utilizo para praticar algoritmos e estruturas de dados. Ele possui a implementação de diversos algoritmos diferentes e soluções para vários problemas de sites como LeetCode, HackerRank, etc.
Para finalizar, ficaremos com o trecho retirado do livro Algoritmos de Thomas Cormen:
Uma sólida base de conhecimento e técnica de algoritmos é uma característica que separa os programadores verdadeiramente qualificados dos novatos. Com a moderna tecnologia computacional, você pode executar algumas tarefas sem saber muito sobre algoritmos; porém, com uma boa base em algoritmos, é possível fazer muito, muito mais.
