Dez algoritmos práticos básicos que os programadores devem conhecer e suas explicações

• ### Algoritmo 1: Algoritmo de classificação rápida

A classificação rápida é um tipo de algoritmo de classificação desenvolvido por Tony Hall. Em circunstâncias médias, a classificação de n itens requer O (nlogn) comparações. Em circunstâncias piores, a classificação requer O (n2) comparações, mas isso não é comum. Na verdade, a classificação rápida é geralmente significativamente mais rápida do que outros algoritmos, pois seu loop interno pode ser efetivamente implementado na maioria das arquiteturas.

A classificação rápida usa a estratégia Divideandconquer para dividir uma lista em duas sub-listas.

Algoritmo:

• 1, escolha um elemento da matriz, chamado pivô de referência,

• 1. Reorganize a matriz, colocando todos os elementos menores do que o valor de referência na frente da matriz, e todos os elementos maiores do que o valor de referência colocando-os atrás da matriz (o mesmo número pode ir para qualquer lado). Após a saída desta divisão, a matriz está no meio da matriz.
• 1. Recursivo: ordenação de subconjuntos menores que o elemento de referência e maiores que o elemento de referência.

  A situação mais básica de uma regressão é que o tamanho da matriz é zero ou um, ou seja, sempre foi ordenado. Apesar de regressar para baixo, o algoritmo sempre sai, porque em cada iteração ele coloca pelo menos um elemento em sua última posição.

• ### Algoritmo 2: Algoritmo de classificação em pilha

O Heapsort é um algoritmo de classificação projetado para usar esta estrutura de dados. O Heapsort é uma estrutura que se aproxima da estrutura de uma árvore binária completa e, ao mesmo tempo, satisfaz a propriedade do Heapsort: o valor de chave ou índice de um sub-nó sempre é menor que (ou maior que) seu pai.

A complexidade média de tempo de ordenação de uma pilha é O (nlogn) 。

Algoritmo:

• 1, criar uma pilha H.[0..n-1]

• 2 - Troque o topo (o valor máximo) e o fim da pilha

• 3 - Reduzir o tamanho da pilha para 1 e chamar shift_down ((0)) para ajustar os dados do topo da nova matriz para a posição correspondente

• 4 Repita o passo 2 até que a pilha tenha o tamanho de 1

• Algoritmo 3: Reagrupamento e ordenação

Mergesort é um algoritmo de classificação eficaz baseado na operação de fusão. O algoritmo é uma aplicação muito típica da divisão e conquista.

Algoritmo:

• 1 - Requer um espaço que tenha o tamanho da soma de duas sequências ordenadas e que seja usado para armazenar as sequências combinadas

• 2 - Configurar dois ponteiros, cada um com a posição inicial de duas sequências ordenadas

• Comparar os elementos apontados pelos dois ponteiros, escolher um elemento relativamente pequeno para o espaço de fusão e mover o ponteiro para a próxima posição

• 4 Repita o passo 3 até que um dos ponteiros chegue ao fim da sequência

• 5 - Copiar todos os elementos restantes de outra sequência diretamente para o final da sequência de fusão

• Algoritmo 4: Algoritmo de busca binária

O algoritmo de busca binária é um algoritmo de busca para encontrar um determinado elemento em uma matriz ordenada. O processo de busca começa no elemento médio da matriz e termina se o elemento médio for exatamente o elemento a ser encontrado; se um determinado elemento for maior ou menor que o elemento médio, a busca começa na metade da matriz maior ou menor que o elemento médio e a comparação começa no elemento médio como no início. Se em algum passo o número de etapas for nulo, o representante não pode ser encontrado.

• ### Algoritmo 5: BFPRT (algorithm de busca linear)

O problema que o BFPRT resolve é muito clássico, ou seja, a escolha do k maior (ou k menor) elemento de uma sequência de n elementos, por meio de uma análise engenhosa, o BFPRT pode garantir a complexidade de tempo linear no pior dos casos. A idéia do algoritmo é semelhante à idéia de classificação rápida, e, claro, os cinco autores do algoritmo fizeram um tratamento sutil para que o algoritmo, no pior dos casos, ainda possa atingir a complexidade de tempo de o (ou n).

Algoritmo:

• 1 , divida n elementos em um grupo de 5 em n / 5 (limite superior) grupos.

• 1. Retire o número médio de cada grupo e use um método arbitrário de classificação, como inserção de classificação.

• 3, o algoritmo de seleção de chamada recursiva encontra a mediana de todos os dígitos médios do passo anterior, definido como x, e em casos de dígitos médios em pares, é definido como a escolha do menor do meio.

• 4 - Divida o array por x, definindo k números menores que x e n-k números maiores que x.

• 5 , se i == k, retorna x; se i < k, busca recursivamente o elemento menor de i em elementos menores que x; se i> k, busca recursivamente o elemento menor de i-k em elementos maiores que x.

  Condição de término: quando n = 1, o retorno é o elemento menor i.

• Algoritmo seis: DFS (profundidade de pesquisa priorizada)

O Deep-First-Search é um tipo de algoritmo de busca que percorre a profundidade da árvore em todos os nódulos da árvore, procurando o mais profundo possível. Quando todos os lados do nó v são explorados, a pesquisa volta ao ponto de partida do lado onde o nó v foi encontrado. Este processo continua até que todos os nódulos que podem ser alcançados a partir do nó de origem encontrado sejam encontrados. Se ainda existem nó não descoberto, escolha um deles como nó de origem e repita o processo acima, repetindo o processo até que todos os nódulos sejam visitados.

A pesquisa de prioridade de profundidade é um algoritmo clássico da teoria gráfica. Usando algoritmos de pesquisa de prioridade de profundidade, pode-se gerar uma tabela topográfica correspondente ao mapa de destino. Usando uma tabela topográfica, pode-se resolver facilmente muitos problemas de topografia relacionados, como o problema do caminho máximo, etc.

Os algoritmos são seguidos de uma sequência de etapas:

• 1 , acessar o topo v;

• 2o. A partir de pontos vizinhos não-visitados de v, o mapa é percorrido em profundidade; até que todos os vértices do mapa com o caminho correspondente a v sejam visitados;

• 1. Se ainda houver um ponto no mapa que não foi visitado, comece a partir de um ponto que não foi visitado e volte a percorrer a profundidade até que todos os pontos do mapa tenham sido visitados.

  A descrição acima pode ser um pouco abstrata, por exemplo:

  O DFS inicia com um vértice v em um gráfico de acesso, inicia com v e acessa qualquer vértice adjacente a ele w1; em seguida, inicia com w1 e acessa um vértice adjacente a w1 mas que ainda não foi visitado; em seguida, inicia com w2 e faz uma visita semelhante, … e assim por diante, até chegar a todos os vértices adjacentes que foram visitados.

  Em seguida, retroceda um passo para o topo que foi visitado na última vez e veja se há outros topos adjacentes que não foram visitados. Se houver, acesse esse topo e, em seguida, inicie a partir dele uma visita semelhante à anterior; se não houver, retroceda um passo para a busca. Repita o processo acima até que todos os topos do mapa de conexão sejam visitados.

• Algoritmo 7: BFS (Broad Foresight Priority Search)

Breadth-First-Search (BFS) é um algoritmo de busca gráfica. Em termos simples, o BFS é um algoritmo que começa no nó raiz e percorre a largura da árvore ao longo da árvore. Se todos os nódulos forem visitados, o algoritmo é interrompido.

Algoritmo:

• 1 - Coloque primeiro o nó raiz na sequência.

• 1. Retire o primeiro nó da sequência e verifique se ele é o alvo.

  Se o alvo for encontrado, a busca deve ser encerrada e os resultados transmitidos. Caso contrário, adicione todos os seus sub-nodos diretos que ainda não foram examinados à cota.

• 3 , Se a fila está vazia, significa que o mapa inteiro foi examinado por uma barra, ou seja, o mapa não tem o alvo a ser procurado. Concluir a busca e retornar para a barra de busca não encontrou o alvo.

• 4 Repita o passo 2.

• Algoritmo 8: Algoritmo Dijkstra

O Dijkstra-salgoritmo (em neerlandês: Dijkstra-salgoritme) é um algoritmo desenvolvido pelo cientista de computador holandês Eizhel Dijkstra. O Dijkstra-salgoritmo usa a pesquisa de prioridade de amplitude para resolver o problema do caminho mais curto de uma única fonte de um gráfico com direção não-negativa, resultando em uma árvore de caminho mais curto. O algoritmo é frequentemente usado em algoritmos de roteamento ou como um sub-módulo de outros algoritmos gráficos.

A entrada deste algoritmo contém um gráfico orientado G com peso, e um ponto de origem em G, S. Nós representamos o conjunto de todos os pontos em G com V. Os lados de cada gráfico são pares de elementos ordenados formados por dois pontos.[[0,∞] definição.

Assim, w (u,v) é o peso não-negativo de um vértice u até um vértice v. O peso de um lado pode ser imaginado como a distância entre dois vértices. O peso de um caminho entre dois pontos é a soma dos pesos de todos os lados do caminho.

Algoritmo:

• 1 , a ordem inicial S = {V0} , T = { restante vertebrais} , o valor de distância correspondente entre os vértices de T Se houver , d (V0,Vi) é o valor de peso sobre o arco Se não houver , d (V0,Vi) é infinito.

• 2 Selecione um ponto W de T cuja distância é menor e que não está em S, e junte-o a S

• 3 - Modificar o valor da distância dos vértices do resto de T: se adicionar W como um vértice intermediário, reduzir o valor da distância de V0 a Vi, modificar esse valor de distância

  Repetir os passos 2 e 3 acima até que S contenha todos os vértices, ou seja, W = Vi

• Algoritmo 9: Programação Dinâmica

A programação dinâmica é um método usado em matemática, ciência da computação e economia para resolver problemas complexos por meio da decomposição do problema original em subproblemas relativamente simples. A programação dinâmica é frequentemente aplicada a problemas com subproblemas sobrepostos e propriedades de estrutura ótima, e a programação dinâmica geralmente consome muito menos tempo do que a solução simples.

A idéia por trás do planejamento dinâmico é muito simples. Em geral, para resolver um determinado problema, precisamos resolver suas diferentes partes (subproblemas) e, em seguida, combinar as soluções dos subproblemas para obter a solução do problema original. Geralmente, muitos subproblemas são muito semelhantes, para isso o planejamento dinâmico tenta resolver cada subproblemas apenas uma vez, reduzindo a quantidade de cálculo: uma vez que a solução de um determinado subproblemas já foi calculada, ele é armazenado na memória, para que a próxima vez que você precisa resolver o mesmo subproblemas seja diretamente listado.

A questão mais clássica sobre o planejamento dinâmico é a da mochila.

Algoritmo:

1 Propriedades da estrutura ótima Se a solução da solução ótima do problema contém a solução da sub-problemática também é ótima, dizemos que o problema tem propriedades da estrutura ótima (ou seja, satisfaz o princípio da otimização). Propriedades da estrutura ótima fornecem pistas importantes para a resolução do problema com algoritmos de planejamento dinâmico

2 , sobreposição de subproblemas. A sobreposição de subproblemas significa que cada subproblemas gerados não é sempre um novo problema quando o problema é resolvido de cima para baixo com algoritmos de regressão. Alguns subproblemas são repetidamente computados várias vezes. O algoritmo de planejamento dinâmico usa essa sobreposição de subproblemas, calculado apenas uma vez para cada subproblemas, e depois guarda seus resultados em uma tabela.

• ### Algoritmo 10: Algoritmo de classificação simplista de Bayes

O algoritmo de classificação naiva de Bayes é um algoritmo de classificação de probabilidade simples baseado no teorema de Bayes. A classificação de Bayes é baseada na inferência de probabilidade, ou seja, como realizar a tarefa de raciocínio e decisão em caso de incerteza em relação à existência de várias condições, apenas sabendo que a probabilidade de ocorrência é a sua. A inferência de probabilidade é correspondente à inferência de certeza.

Os classificadores naive Bayes dependem de modelos de probabilidade natural precisos, e conseguem classificar muito bem em concentrações de amostras com aprendizado supervisionado. Em muitas aplicações práticas, os parâmetros do modelo naive Bayes são estimados usando o método de estimativa de maior probabilidade, ou seja, o modelo naive Bayes funciona sem usar a probabilidade de Bayes ou qualquer modelo Bayesian.

Apesar das ideias simplistas e das suposições simplistas, o classificador básio simplista pode funcionar muito bem em situações de realidade muito complexas.