Introdução à Complexidade de Algoritmos

Esta é uma pré-visualização de arquivo. Entre para ver o arquivo original

Introdução à Complexidade de Algoritmos Tempo de leitura: 14 minutos 26 de março de 2019 Pressione Enter ou clique para ver a imagem em tamanho real. Algoritmos e estruturas de dados são temas frequentemente ignorados por diversas pessoas da área de desenvolvimento e engenharia de software, desde universitários até 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ários". Pressione Enter ou clique para ver a imagem em tamanho real. Hoje em dia também existe uma discussão muito recorrente sobre linguagens de programação sendo melhores ou mais rápidas que outras. Apesar de um poder ser melhor que outro em situações diferentes, nada importa que uma pessoa que esteja escrevendo o código não tenha 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 uma 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 baseia-se num conjunto de dados que se pretende analisar, com as suas especificidades, e o resultado que se pretende alcançar. Como podemos perceber, existem diversos problemas que podem ser resolvidos utilizando algoritmos. Não existe uma "bala de prata" para resolver os métodos eficientes. Porém existem categorias nas quais os problemas e seus subproblemas podem ser classificados. Abstraindo o problema, podemos identificar sua categoria e aplicar técnicas específicas conhecidas para resolvê-los da maneira mais eficiente. Algumas das principais categorias/técnicas são: - Algoritmos Gananciosos - Programação Dinâmica - Dividir e Conquistar - Backtracking - Pesquisa e Classificação Existem também estruturas de dados que são usadas 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 para analisar o desempenho 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. Queremos comparar algoritmos em termos do que eles são: Ideias de como algo é computado. Comparar o tempo que os 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 cujo soma resulta na entrada específica ( alvo ) e retorna as posições dos números encontrados: Algoritmo em Golang Algoritmo em Kotlin Rodando as duas soluções com o arrays de até 1000 elementos, o algoritmo em Go é muito mais rápido que o Kotlin, demorando apenas alguns nanosegundos para encontrar o resultado, enquanto o Kotlin demora poucos milissegundos 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 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 gráfico seguinte: Pressione Enter ou clique para ver a imagem em tamanho real. Variação do tempo de execução dos algoritmos de acordo com o tamanho da entrada Conforme a entrada cresce, o tempo de execução em Kotlin varia muito pouco, apresentando valores entre 0 e 234 milissegundos. 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 a rapidez com que um programa executa suas computações. Exemplos de cálculos 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 verifique até 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 Para começar a entender a análise da complexidade de algoritmos, precisamos 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 devemos fazer é contar as instruções fundamentais deste código executado. Primeiro, separaremos o código em pequenas instruções e consideraremos que o processador executa como uma instrução cada. A primeira instrução é uma atribuição do primeiro elemento da lista a uma variável que será utilizada para ser comparada com os outros elementos da lista e armazenar o elemento maior. maior := lista[0] Após isso, o loop será inicializado indice := 0 e seu bloco será executado caso o array não esteja vazio. Após isso temos duas instruções: índice := 0 índice < n E ao final de cada laço temos 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, 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 definir 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 programado. Caso o array esteja ordenado [1,2,4,5,6], o código dentro do if será executado 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, temos 4 instruções dentro do laço de repetição. No final, podemos chegar à seguinte função que nos dá o número de instruções no pior caso para o algoritmo: f( n ) = 4 + 2n + 4n = 6n + 4 Comportamento Assintótico Seria uma tarefa muito difícil 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 prazo, podemos remover todas as constantes e manter o prazo que mais cresce. Na função f(n) = 6n + 4 , obviamente, 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 anterior de n seja 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, os cientistas da computação adotaram a Notação Big-O. Ela é utilizada para delimitar de forma assintótica 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ão com que ele execute 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 identificar a complexidade do algoritmo. Geralmente, quando um algoritmo possui apenas 1 laço de reprodução sua complexidade é O(n), quando possui 2 laços encadeados O(n ² ) e nenhum laço de reprodução O(1). Mas cuidado, isso nem sempre se aplica! Complexidade de sequência Todas as análises feitas até agora foram em função do número de operações que os algoritmos menores, 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 do 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 usados ​​para resolver o Two Sum no começo desse post. Exemplo Dois Soma em Kotlin Algoritmo 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 alvo já esteja no mapa, o elemento que faltava para a soma ser igual ao alvo é encontrado . O algoritmo exige, no pior dos casos, que todos os itens do array sejam percorridos e aumentados 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 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 Dois Soma em Go Algoritmo em Golang 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 seja atual igual ao target, o valor é retornado. Na pior das hipóteses, o algoritmo deverá percorrer n*n vezes o array para informar que não existem 2 elementos que somados resultaram 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. Busca binária em Python — GeekforGeeks 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 seja 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 seja a mesma que a final. A cada iteração no loop, o número de elementos a serem percorridos cai pela metade. Por isso, a complexidade do 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, start, 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 às seguintes possibilidades de recorrência: Resolvendo a soluçã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. Árvore de execução do Merge Sort. Os números representam o espaço extra a cada chamada recursiva. Devido ao fato do merge sort utilizado nesse exemplo não ser executado em paralelo, sua execução acontece de uma maneira semelhante a um Depth First Traversal ou busca em profundidade . Dessa forma, apenas um "galho" da árvore será expandido por vez, durante uma pilha de recursão, e o número de espaço extra utilizado será de no máximo 3n . A pilha de execução acontecerá da seguinte forma: O primeiro "galho" formado representou com os números em destaque. Somando os números destacados, temos o valor 16 + 8 + 4 + 2 +1 +1 = 32 (equivalente a 2n ). E em seguida: Cuja 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: Pressione Enter ou clique para ver a imagem em tamanho real. Essa é a última pilha 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 na 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 deles fosse "grátis" . O código a seguir utiliza a função do python de uma lista algumas vezes para filtrar todos os usuários que estão em uma lista de bloqueio. A complexidade de tempo do código acima é O(n ²) . Verifique 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 uma 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 verifique 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 em diferentes estruturas de dados possui complexidades diferentes. No dia a dia como desenvolvedor é muito fácil se comparar com um caso semelhante ao algoritmo acima. Não é necessário conhecer uma 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 permite 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 sua importância. Para entender melhor o assunto é necessário estudar mais o fundo de cada um dos relatos relatados, além de vários outros, utilizando recursos jurídicos. Implementar algoritmos de maneiras eficientes continua sendo de extrema importância para conseguir construir aplicações que permitam 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 é à toa que as maiores empresas de tecnologia, como Google, Facebook e Amazon possuem processos seletivos que avaliam rigidamente o nível de conhecimento em algoritmos de seus candidatos. Mas é claro que “ algoritmos” não é o tópico mais importante para um profissional da área dominar. De nada adianta dominar o fundo de 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á implementado. Aqui está um repositório que utiliza 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 base sólida de conhecimento e técnica de algoritmos é uma característica que separa os programadores verdadeiramente elaborados dos novos. 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. s