A ordenação rápida é um algoritmo de ordenação desenvolvido por Tony Hall. Em condições médias, a ordenação de n objetos requer uma comparação nlogn; em condições piores, uma comparação n2 é necessária, mas isso não é comum. Na verdade, a ordenação rápida geralmente é significativamente mais rápida do que outros algoritmos nlogn, pois seu loop interno pode ser implementado com muita eficiência em a maioria das arquiteturas.
Ordenamento rápido usa a estratégia Divideandconquer para dividir uma lista em duas sub-listas.
O algoritmo segue os seguintes passos:
1, escolher um elemento da coluna numérica, chamado pivô de referência,
2, reordenar a coluna, colocando todos os elementos menores que o valor de referência na frente do valor de referência e todos os elementos maiores que o valor de referência na retaguarda do valor de referência (o mesmo número pode ir para qualquer lado); após a saída deste segmento, o valor de referência fica no meio da coluna; isso é chamado de operação de partição.
3, recursivo: ordenação de subarreixas de elementos menores que o valor de referência e maiores que o valor de referência.
A situação mais básica da regressão é que o tamanho da matriz é zero ou um, ou seja, sempre foi ordenado. Embora a regressão seja contínua, o algoritmo sempre sai, porque em cada iteração, ele coloca pelo menos um elemento em sua posição final.
Heapsort é um algoritmo de classificação projetado para usar este tipo de estrutura de dados. O heapsort é uma estrutura de árvore quase totalmente binária, mas também satisfaz a propriedade do heapsort: o valor de chave ou índice de um sub-nodo é sempre menor que (ou maior que) o de seu pai.
A complexidade média de tempo para a ordenação de pilhas é O (nlogn).
O algoritmo segue os seguintes passos:
1, criar uma pilha H [0...n-1]
2, substituir a cabeça da pilha (max) e a cauda da pilha
3, reduzir o tamanho da pilha para 1 e chamar shift_down ((0), com o objetivo de ajustar os dados do topo da nova matriz para a posição correspondente
4, repita o passo 2 até que o tamanho da pilha seja 1.
Mergesort é um algoritmo de classificação eficaz baseado em operações de agregação. O algoritmo é uma aplicação muito típica do método Divide and Conquer.
O algoritmo segue os seguintes passos:
1, aplicação de um espaço de tamanho igual à soma de duas séries já ordenadas, que é usado para armazenar as séries depois da fusão
2, definir dois ponteiros, com a posição inicial como a posição inicial de duas séries ordenadas
3. Comparar os elementos apontados pelos dois ponteiros, escolher um elemento relativamente pequeno e colocá-lo no espaço de junção e mover o ponteiro para o próximo local
4, repita o passo 3 até que um dos ponteiros chegue ao final da sequência
5, copiar todos os elementos restantes da outra sequência diretamente para a ponta da sequência combinada
Um algoritmo de busca por dois pontos é um algoritmo de busca por um determinado elemento em uma matriz ordenada. O processo de pesquisa começa no elemento intermediário da matriz e termina se o elemento intermediário for exatamente o elemento a ser procurado; se um determinado elemento for maior ou menor que o elemento intermediário, o processo de pesquisa é feito na metade da matriz que é maior ou menor que o elemento intermediário e a comparação começa do mesmo modo.
O BFPRT resolve o clássico problema de escolher o k maior (k menor) elemento de uma sequência de n elementos e, por meio de uma análise habilidosa, garante que o algoritmo permaneça com uma complexidade de tempo linear no pior dos casos. A idéia do algoritmo é semelhante à idéia de ordenação rápida.
O algoritmo segue os seguintes passos:
1, dividindo n elementos em grupos de 5 em grupos de n / 5 (em cima da borda).
2, extrair o número médio de cada grupo, qualquer método de ordenação, como inserir ordenação.
O algoritmo de seleção de chamadas recorrentes, que busca o mediano de todos os medianos do passo anterior, é definido como x e, em casos de medianos pares, é definido como escolher o menor do meio.
4, para dividir um conjunto de números com x, é necessário que os números menores que x sejam k e maiores que x sejam n - k.
5, se i == k, retorna x; se i < k, retorna para encontrar o elemento menor que i em um elemento menor que x; se i > k, retorna para encontrar o elemento menor que i em um elemento maior que x.
Condição de terminação: quando n = 1, o que é devolvido é o elemento i pequeno.
O Deep-First-Search é um algoritmo de pesquisa que percorre os pontos da árvore ao longo da profundidade da árvore e ramifica a árvore o mais profundamente possível. Quando todos os lados do ponto v são explorados, a pesquisa retorna ao ponto inicial do lado do ponto v encontrado. O processo continua até que todos os pontos já encontrados sejam acessados pelo ponto de origem.
A busca de prioridade profunda é um algoritmo clássico em gráficos, que pode ser usado para gerar uma tabela topográfica correspondente a um gráfico de destino. A utilização de tabela topográfica pode ser usada para resolver facilmente muitos problemas gráficos relacionados, como o problema do caminho máximo, etc.
A partir de agora, o Google vai continuar a trabalhar com o Google para criar um algoritmo de gráficos mais rápido.
1, acesso ao topo v;
2, em sequência, a partir de pontos vizinhos não acessados de v, percorre o gráfico com prioridade de profundidade; até que todos os vértices do gráfico com o caminho de v sejam acessados;
3, se ainda houver vertices não visitados no gráfico, recomece a percorrer a profundidade de prioridade a partir de um dos vertices não visitados até que todos os vertices do gráfico tenham sido visitados.
A descrição acima pode ser mais abstrata, como por exemplo:
O DFS, depois de começar em um dos picos v no gráfico de acesso, sai de v, acessa qualquer um dos seus picos adjacentes w1; parte de w1, acessa o pico w2 adjacente a w1 mas que ainda não foi visitado; e parte de w2, faz uma visita semelhante,... e assim por diante, até chegar a um pico u onde todos os picos adjacentes foram visitados.
Em seguida, volte um passo atrás e volte ao topo que você visitou na última vez para ver se há outros picos adjacentes que não foram visitados. Se houver, visite esse topo e, em seguida, continue a partir deste topo para fazer uma visita semelhante à anterior. Se não houver, volte um passo atrás e faça uma pesquisa.
Breadth-First-Search é um algoritmo de busca gráfica. Simplificando, o BFS é um algoritmo de busca gráfica que percorre a largura da árvore, começando no ponto da raiz. Se todos os pontos forem visitados, o algoritmo é interrompido.
O algoritmo segue os seguintes passos:
Primeiro, coloque o nó raiz na fila.
2. Retire o primeiro nó da fila e verifique se ele é um alvo.
Se encontrarmos o alvo, terminamos a busca e enviamos o resultado. Caso contrário, todos os seus sub-nodos diretos que ainda não foram verificados são adicionados à fila.
3, se a fila estiver vazia, significa que o gráfico inteiro foi examinado e que não há nenhum alvo no gráfico.
4, repita o passo 2.
O algoritmo Dijkstra foi desenvolvido pelo cientista de computadores holandês Eichel Dijkstra. O algoritmo Dijkstra usa uma busca de largura de prioridade para resolver o problema do caminho mais curto de um único fonte de um gráfico orientado não-negativo, resultando em uma árvore de caminho mais curto. O algoritmo é frequentemente usado em algoritmos de roteamento ou como um submodular de outros algoritmos gráficos.
A entrada do algoritmo contém um gráfico orientado ponderado G, e um vértice de origem S em G. V representa o conjunto de todos os vértices em G. Cada lado do gráfico é um par de elementos ordenados formados por dois vértices. U, v significa que há um caminho entre os vértices u e v. E representa o conjunto de todos os lados em G, e o peso do lado é definido pela função de ponderação w: E→[0,∞].
Assim, w ((u, v) é o peso não negativo do topo u até o topo v. O peso do lado pode ser imaginado como a distância entre os dois picos. O peso do caminho entre os dois pontos é a soma dos pesos de todos os lados do caminho. Há um topo s e t em V, e o algoritmo de Dijkstra pode encontrar o menor caminho de peso de s a t.
O algoritmo segue os seguintes passos:
1, o valor da distância correspondente ao ponto no T, quando S = {V0}, T = {residual vertices}
Se existirem
2, escolha um topo W de T cujo valor de distância seja o menor e não esteja em S e junte S
3, modificação do valor da distância entre os vértices do resto de T: se adicionar W como um vértice intermediário, reduzindo o valor da distância de V0 para Vi, modifica-se este valor de distância
Repita os passos 2 e 3 até que o S contenha todos os vertices, ou seja, W = Vi.
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 de problemas originais em subproblemas relativamente simples. A programação dinâmica é frequentemente aplicada a problemas com subproblemas sobrepostos e estruturas de suporte ideal, que costumam demorar muito menos do que soluções simples.
A ideia básica por trás do planejamento dinâmico é muito simples. Geralmente, para resolver um problema, precisamos resolver seus diferentes componentes ("problemas de sub-problemas") e resolver subproblemas de recombinação para resolver o problema original. Muitos subproblemas são muito semelhantes, por isso o planejamento dinâmico tenta resolver cada subproblemas apenas uma vez, reduzindo assim o volume de computação: uma vez que a solução de um dado subproblemas foi calculada, ele é armazenado em memória para ser verificado diretamente na próxima vez que for necessário resolver o mesmo subproblemas.
A questão mais clássica do planejamento dinâmico é a questão da mochila.
O algoritmo segue os seguintes passos:
1, Propriedade estrutural ideal. Se a solução para o subproblema que contém a melhor solução do problema também é ideal, o problema é chamado de subestrutural ideal (isto é, satisfaz o princípio da otimização); a estrutura ideal fornece pistas importantes para a solução de problemas em algoritmos de planejamento dinâmico.
2, a sobreposição de subproblemas. A sobreposição de subproblemas refere-se ao fato de que, quando um problema é resolvido de cima para baixo com um algoritmo recursivo, cada vez que um subproblema é gerado, não é sempre um novo problema, e alguns subproblemas são calculados várias vezes. O algoritmo de planejamento dinâmico aproveita a sobreposição de subproblemas, calcula cada subproblema uma vez e mantém seus resultados em uma tabela.
Um algoritmo de classificação de Bayes simples é um algoritmo de classificação de probabilidade simples baseado no teorema de Bayes. O algoritmo de classificação de Bayes baseia-se no raciocínio de probabilidade, ou seja, como realizar as tarefas de raciocínio e de decisão quando as condições são incertas e apenas se sabe que elas ocorrem. O raciocínio de probabilidade corresponde ao raciocínio de certeza.
Os classificadores de Bayes simples dependem de modelos de probabilidade natural precisos e obtêm muito bons efeitos de classificação em conjuntos de amostras com aprendizado supervisionado. Em muitas aplicações práticas, os parâmetros do modelo de Bayes simples são estimados usando o método de estimativa da maior similaridade, ou seja, os modelos de Bayes simples funcionam sem o uso de probabilidades de Bayes ou de qualquer modelo de Bayes.
Apesar dessas idéias simples e suposições muito simplificadas, os classificadores Bayesian simples podem funcionar bastante bem em muitas situações de realidade complexas.