Esses algoritmos são essenciais para o fluxo de trabalho de cada programador.
Como estudante de programação, você provavelmente aprendeu muitos algoritmos diferentes ao longo de sua carreira. Tornar-se proficiente em diferentes algoritmos é absolutamente essencial para qualquer programador.
Com tantos algoritmos, pode ser um desafio acompanhar o que é essencial. Se você está se preparando para uma entrevista ou simplesmente aprimorando suas habilidades, esta lista tornará isso relativamente fácil. Continue lendo enquanto listamos os algoritmos mais essenciais para programadores.
1. Algoritmo de Dijkstra
Edsger Dijkstra foi um dos cientistas da computação mais influentes de seu tempo e contribuiu para muitas áreas diferentes da ciência da computação, incluindo sistemas operacionais, construção de compiladores e muito mais. Uma das contribuições mais notáveis de Dijkstra é a engenhosidade de seu algoritmo de caminho mais curto para grafos, também conhecido como algoritmo de caminho mais curto de Dijkstra.
O algoritmo de Dijkstra encontra o caminho mais curto em um grafo de uma fonte para todos os vértices do grafo. A cada iteração do algoritmo, um vértice é adicionado com a distância mínima da fonte e um que não existe no caminho mais curto atual. Esta é a propriedade gananciosa usada pelo algoritmo de Djikstra.
O algoritmo é tipicamente implementado usando um conjunto. O algoritmo de Dijkstra é muito eficiente quando implementado com um Min Heap; você pode encontrar o caminho mais curto em apenas O(V+ElogV) tempo (V é o número de vértices e E é o número de arestas em um determinado grafo).
O algoritmo de Dijkstra tem suas limitações; ele só funciona em grafos direcionados e não direcionados com arestas de peso positivo. Para pesos negativos, o algoritmo de Bellman-Ford é normalmente preferível.
As perguntas da entrevista geralmente incluem o algoritmo do Djikstra, por isso recomendamos entender seus detalhes e aplicações intrincados.
2. Mesclar Ordenação
Temos alguns algoritmos de classificação nesta lista, e a classificação por mesclagem é um dos algoritmos mais importantes. É um algoritmo de ordenação eficiente baseado na técnica de programação Divide and Conquer. No pior cenário, a ordenação por mesclagem pode classificar “n” números em apenas O(nlogn). Em comparação com técnicas de classificação primitivas, como Bubble Sort (que leva tempo O(n^2), a classificação por mesclagem é excelentemente eficiente.
Na ordenação por mesclagem, o array a ser classificado é repetidamente dividido em subarrays até que cada subarray consista em um único número. O algoritmo recursivo então mescla repetidamente os subarrays e classifica o array.
3. Classificação rápida
Quicksort é outro algoritmo de ordenação baseado na técnica de programação Divide and Conquer. Nesse algoritmo, um elemento é primeiro escolhido como pivô e todo o array é então particionado em torno desse pivô.
Como você provavelmente adivinhou, um bom pivô é crucial para uma classificação eficiente. O pivô pode ser um elemento aleatório, o elemento de mídia, o primeiro elemento ou até mesmo o último elemento.
As implementações do quicksort geralmente diferem na maneira como escolhem um pivô. No caso médio, o quicksort ordenará um array grande com um bom pivô em apenas O(nlogn).
O pseudocódigo geral do quicksort particiona repetidamente o array no pivô e o posiciona na posição correta do subarray. Ele também coloca os elementos menores que o pivô à sua esquerda e os elementos maiores que o pivô à sua direita.
4. Primeira Pesquisa de Profundidade
Depth First Search (DFS) é um dos primeiros algoritmos de grafo ensinados aos alunos. DFS é um algoritmo eficiente usado para percorrer ou pesquisar um gráfico. Ele também pode ser modificado para ser usado na travessia de árvore.
A travessia DFS pode começar a partir de qualquer nó arbitrário e mergulha em cada vértice adjacente. O algoritmo retrocede quando não há vértice não visitado ou há um beco sem saída. O DFS é normalmente implementado com uma pilha e uma matriz booleana para acompanhar os nós visitados. O DFS é simples de implementar e excepcionalmente eficiente; funciona(V+E), onde V é o número de vértices e E é o número de arestas.
As aplicações típicas da travessia DFS incluem classificação topológica, detecção de ciclos em um gráfico, localização de caminhos e localização de componentes fortemente conectados.
5. Pesquisa em amplitude
Breadth-First Search (BFS) também é conhecido como um percurso de ordem de nível para árvores. BFS funciona em O(V+E) semelhante a um algoritmo DFS. No entanto, o BFS usa uma fila em vez da pilha. O DFS mergulha no gráfico, enquanto o BFS percorre todo o gráfico.
O algoritmo BFS utiliza uma fila para acompanhar os vértices. Os vértices adjacentes não visitados são visitados, marcados e enfileirados. Se o vértice não tiver nenhum vértice adjacente, então um vértice é removido da fila e explorado.
O BFS é comumente usado em redes peer-to-peer, caminho mais curto de um grafo não ponderado e para encontrar a árvore geradora mínima.
6. Pesquisa Binária
Binary Search é um algoritmo simples para encontrar o elemento necessário em um array ordenado. Ele funciona dividindo repetidamente a matriz pela metade. Se o elemento necessário for menor que o elemento central, o lado esquerdo do elemento central será processado posteriormente; caso contrário, o lado direito é dividido pela metade e pesquisado novamente. O processo é repetido até que o elemento necessário seja encontrado.
A complexidade de tempo do pior caso da pesquisa binária é O(logn), o que a torna muito eficiente na pesquisa de matrizes lineares.
7. Algoritmos Mínimos de Spanning Tree
Uma árvore geradora mínima (MST) de um grafo tem o custo mínimo entre todas as árvores geradoras possíveis. O custo de uma árvore geradora depende do peso de suas arestas. É importante observar que pode haver mais de uma árvore geradora mínima. Existem dois algoritmos principais do MST, ou seja, o de Kruskal e o de Prim.
O algoritmo de Kruskal cria o MST adicionando a borda com custo mínimo a um conjunto crescente. O algoritmo primeiro classifica as arestas por seu peso e, em seguida, adiciona arestas ao MST começando pelo mínimo.
É importante notar que o algoritmo não adiciona arestas que formam um ciclo. O algoritmo de Kruskal é preferido para grafos esparsos.
O Algoritmo de Prim também usa uma propriedade gulosa e é ideal para grafos densos. A ideia central no MST de Prim é ter dois conjuntos distintos de vértices; um conjunto contém o MST crescente, enquanto o outro contém vértices não utilizados. Em cada iteração, a aresta de peso mínimo que conectará os dois conjuntos é selecionada.
Algoritmos de árvore de abrangência mínima são essenciais para análise de cluster, taxonomia e redes de transmissão.
Um programador eficiente é proficiente com algoritmos
Os programadores aprendem e desenvolvem constantemente suas habilidades, e há alguns fundamentos essenciais nos quais todos precisam ser proficientes. Um programador habilidoso conhece os diferentes algoritmos, os benefícios e as desvantagens de cada um e qual algoritmo seria mais apropriado para um determinado cenário.