Top Algorithms and Data Structures You Really Need To Know
Se você quer se tornar um engenheiro de software, mas não sabe por onde começar, vamos salvar o suspense: são algoritmos e estruturas de dados.
Após você obter a essência desses pilares da programação, você começará a vê-los em todos os lugares. E quanto mais algoritmos e estruturas de dados você aprender, mais eles servirão como combustível para sua carreira como engenheiro de software.
Para começar, vamos primeiro mergulhar fundo na Search and Sort, duas classes de algoritmos sem os quais você não pode viver. Depois vamos fazer um rápido levantamento do resto da paisagem que inclui árvores, gráficos, programação dinâmica e toneladas a mais.
Em termos gerais, há duas categorias de algoritmos de busca que você precisará saber imediatamente: linear e binário. Depth First Search (DFS) e Breadth First Search (BFS) também são super importantes, mas vamos salvá-los para a seção de travessia do gráfico abaixo.
Linear search
Os algoritmos lineares e binários são nomeados como tal para descrever quanto tempo (complexidade de tempo) uma pesquisa vai levar com base no tamanho da entrada que está sendo pesquisada.
Por exemplo, com algoritmos de pesquisa linear, se você tiver 100 itens para pesquisar, então o pior cenário exigiria que você olhasse cada item no input antes de encontrar o valor desejado. É chamado linear porque o tempo que leva para pesquisar está exatamente correlacionado com a quantidade de itens na pesquisa (100 itens/entrada = 100 verificações/complexidade)
Em resumo, linear = simples (não há nada de inteligente no algoritmo). Por exemplo: imagine que você está tentando encontrar seu amigo Lin entre uma linha de pessoas sem uma ordem em particular. Você já sabe como Lin é, então você simplesmente tem que olhar para cada pessoa, uma a uma, em sequência, até que você reconheça ou não reconheça Lin. É isso mesmo. Ao fazer isso, você está seguindo o algoritmo de busca linear
Binary search
Binary search gets its name because the word binary means “of or relating to 2 things” and the algoritmo funciona dividindo a entrada em duas partes até encontrar o item que está sendo procurado. Uma metade contém o item pesquisado e a outra metade não. O processo continua até que o local onde o input é dividido se torne o item que está sendo pesquisado. A pesquisa binária é basicamente apenas uma abordagem altamente disciplinada do processo de eliminação. É mais rápida que a busca linear, mas só funciona com sequências ordenadas.
Um exemplo deve deixar isso mais claro. Suponha que você esteja tentando encontrar o seu amigo Bin (que tem 1,5 m) em uma linha de arquivo único de pessoas que foram ordenadas por altura da esquerda para a direita, do mais baixo para o mais alto. É uma fila muito longa, e você não tem tempo de passar um a um por todo o processo, comparando a altura de todos com a de Bin. O que pode fazer?
/div>>
Enter pesquisa binária. Você seleciona a pessoa no meio da linha, e mede sua altura. São 5’7”. Então imediatamente você sabe que esta pessoa, junto com todos à sua direita, não é Bin. Agora que você cortou seu problema ao meio, você volta sua atenção para o resto da linha e escolhe a pessoa do meio novamente. Eles têm 1,80 m. Então você pode descartar essa pessoa e qualquer um à sua esquerda, cortando o problema ao meio novamente. E assim por diante. Depois de apenas cinco ou seis destas rachaduras, você chega rapidamente ao Bin em uma fração do tempo que levou para encontrar Lin. Ao fazer isso, você seguiu o algoritmo de busca binária.
Sorting
Ordering, caso contrário conhecido como ordenação, listas de itens é uma das tarefas de programação mais comuns que você fará como um desenvolvedor. Aqui nós olhamos para dois dos mais úteis algoritmos de ordenação: MergeSort e QuickSort.
MergeSort
Suponhamos que ao invés de cruzar a linha ordenada de pessoas no exemplo acima, você precisa criar uma linha ordenada de pessoas fora de um grupo não ordenado. Você não tem muito tempo, então você inventa uma estratégia para acelerar as coisas.
Você primeiro tem o grupo de pessoas, que estão todas agrupadas, divididas em duas. Então você tem cada um dos dois grupos divididos em dois novamente, e assim por diante, até que você esteja lidando inteiramente com indivíduos. Então você começa a emparelhar os indivíduos, e tem o mais alto dos dois em cada par de pé, à direita do outro. Logo todos estão organizados nestes pares ordenados à esquerda-direita.
P>Próximo, você começa a unir os pares ordenados em grupos ordenados de quatro; depois unindo os grupos ordenados de quatro em grupos ordenados de oito; e assim por diante. Finalmente, você descobre que você tem uma linha completa, ordenada em altura, exatamente como a que você encontrou acima. Sem saber, você seguiu o algoritmo MergeSort para realizar a sua proeza.
QuickSort
QuickSort é um pouco complexo demais para ser facilmente imaginado com as pessoas, por isso vamos chegar um pouco mais perto do código. Para começar, vamos imaginar que você tem uma lista não ordenada, ou array, de oito números que você quer ordenar.
4 2 13 6 15 12 7 9
Você poderia usar o MergeSort, mas você ouve que o QuickSort é geralmente mais rápido, então você decide experimentá-lo. O seu primeiro passo é escolher um número na lista chamado pivot. Escolher o número do pivot certo fará toda a diferença na rapidez do seu QuickSort, e existem fórmulas prontas a seguir para escolher bons pivôs. Mas por enquanto, vamos manter as coisas simples e simplesmente ir com o último número no array para o nosso número de pivô: 9.
4 2 13 6 15 12 7 9
Para tornar o próximo passo mais fácil de seguir, vamos criar um separador no início do array e representá-lo com o sinal de libra.
# 4 2 13 6 15 12 7 9
Movendo da esquerda para a direita através do nosso array, o nosso objetivo é colocar qualquer número menor que o pivô (9) à esquerda do separador, e qualquer número maior que (ou igual a) o pivô à direita do separador. Começamos com o primeiro número da nossa matriz: 4. Para movê-lo para a esquerda do separador, apenas movemos o separador para cima um elemento:
4 # 2 13 6 15 12 7 9
Fazemos o mesmo com o próximo número: 2.
4 2 # 13 6 15 12 7 9
Mas então chegamos ao 13, que é maior que o pivô número 9 e já para o lado direito do separador. Então deixamos isso em paz. A seguir chegamos ao 6, que precisa ir para a esquerda do separador. Então primeiro trocamos com o 13 para colocá-lo na posição:
4 2 # 6 13 15 12 7 9
Então movemos o separador passou por ele:
4 2 6 # 13 15 12 7 9
P>P>Próximo é 15, que já está à direita do separador, então o deixamos em paz. Depois temos 12. A mesma coisa. Mas o 7, nosso último número antes de chegar ao pivô, precisa do mesmo tipo de ajuda em movimento que o 6. Então trocamos o 7 pelo 13 para colocá-lo na posição:
4 2 6 # 7 15 12 13 9
Então, mais uma vez, movemos o separador passando-o:
4 2 6 7 # 15 12 13 9
Finalmente, chegamos ao nosso número do pivô: 9. Seguindo a mesma lógica que temos acima, trocamos 15 com 9 para obter o número do pivô onde ele precisa estar:
4 2 6 7 # 9 12 13 15
Desde que todos os números à esquerda de 9 são agora menores que 9, e todos os números à direita de 9 são maiores que 9, terminamos com o nosso primeiro ciclo de QuickSort. A seguir, vamos tratar cada conjunto de quatro números de cada lado do separador como um novo array para aplicar o QuickSort. Vamos poupá-lo dos detalhes, mas a próxima rodada nos dará quatro pares de números para aplicarmos facilmente a nossa rodada final do QuickSort. O resultado final será a seguinte lista ordenada que nos levará menos tempo a gerar do que teria com o MergeSort mais simples:
2 4 6 7 9 12 13 15
Sorting algorithms cheat sheet
Estes são os algoritmos de ordenação mais comuns com algumas recomendações para quando usá-los. Internalize-os! Eles são usados em todo o lado!
Selecção de pilhas: Quando você não precisa de uma classificação estável e você se preocupa mais com o desempenho do pior caso do que o desempenho médio dos casos. É garantido ser O(N log N), e usa O(1) espaço auxiliar, o que significa que você não ficará inesperadamente sem espaço de pilha ou pilha em entradas muito grandes.
Introsort: Este é um tipo rápido que muda para um tipo de pilha após uma certa profundidade de recursividade para contornar o pior caso de O(N²) do tipo rápido. É quase sempre melhor do que uma ordenação rápida simples e antiga, uma vez que você obtém o caso médio de uma ordenação rápida, com desempenho garantido de O(N log N). Provavelmente a única razão para usar um tipo de pilha em vez deste é em sistemas com limitações severas de memória onde o espaço da pilha O(log N) é praticamente significativo.
Insertion sort: Quando N é garantido ser pequeno, inclusive como caso base de uma ordenação rápida ou de uma ordenação de fusão. Enquanto isso é O(N²), ele tem uma constante muito pequena e é uma ordenação estável.
Bubble sort, seleção de ordenação: Quando você está fazendo algo rápido e sujo e por alguma razão você não pode simplesmente usar o algoritmo de ordenação da biblioteca padrão. A única vantagem que estes têm sobre a ordenação de inserção é ser ligeiramente mais fácil de implementar.
Triagem rápida: Quando você não precisa de uma ordenação estável e o desempenho médio dos casos importa mais do que o desempenho dos piores casos. Uma ordenação rápida é O(N log N) em média, O(N²) no pior caso. Uma boa implementação utiliza O(log N) de armazenamento auxiliar na forma de espaço de pilha para recursion.
Merge sort: Quando você precisa de um estável, O(N log N) sort, esta é a sua única opção. A única desvantagem é que ele usa espaço auxiliar O(N) e tem uma constante um pouco maior do que uma ordenação rápida. Existem alguns tipos de fusão no local, mas AFAIK ou não são todos estáveis ou são piores que O(N log N). Mesmo os tipos de O(N log N) no local têm uma constante muito maior do que os antigos tipos de merge que são mais curiosidades teóricas do que os algoritmos úteis.