Em programadores de vida algoritmos e estruturas de dados é mais importante do assunto, se eles querem sair no mundo da programação e fazer algum dinheiro. Hoje, veremos o que eles fazem e onde eles são usados com exemplos mais simples. Esta lista é preparada tendo em conta a sua utilização na programação competitiva e nas práticas de desenvolvimento actuais.

ordenação algoritmos

ordenação é o conceito mais estudado em Ciência da Computação. A idéia é organizar os itens de uma lista em uma ordem específica. Embora todas as principais linguagens de programação tenham criado bibliotecas de triagem, é útil se você souber como elas funcionam. Dependendo do requisito você pode querer usar qualquer um destes.

• Merge Sort
• Quick Sort
• Bucket Sort
• Heap Sort
• Counting Sort

o Mais importante deve-se saber quando e onde usá-los. Alguns exemplos de onde você pode encontrar aplicação direta de técnicas de triagem incluem:

• Classificar por preço, popularidade etc., em sites de e-commerce

Algoritmos de Busca

Pesquisa Binária (em estruturas de dados lineares)

pesquisa Binária é utilizada para efectuar uma forma muito eficiente de pesquisa sobre o conjunto de dados classificados. A complexidade de tempo é O (log2N). A idéia é dividir repetidamente em metade a parte da lista que poderia conter o item, até que a reduzamos a um possível item. Algumas aplicações são:

• Quando você procura por um nome de música em uma lista ordenada de músicas, ele realiza busca binária e correspondência de texto para retornar rapidamente os resultados.
• Usado para depurar no git através do git bissetriz

Profundidade/Largura Primeira Pesquisa (no Gráfico estruturas de dados)

DFS e BFS são árvore/gráfico atravessa e a procura de estruturas de dados. Nós não entraríamos profundamente em como DFS / BFS funcionam, mas veremos como eles são diferentes através da animação.

Aplicações:

• Usado pelos mecanismos de busca para web crawling
• Usado em inteligência artificial para criar bots, por exemplo, um jogo de xadrez bot
• Encontrar o caminho mais curto entre duas cidades em um mapa e muitas outras aplicações

Hash

pesquisa de Hash é atualmente o mais amplamente utilizado na técnica para se encontrar de dados apropriado por chave ou ID. Acedemos aos dados pelo seu índice. Anteriormente, dependíamos da ordenação+busca binária para procurar o índice, enquanto agora usamos o hashing.

A estrutura de dados é referida como Hash-Map ou hash-Table ou dicionário que mapeia chaves de valores, de forma eficiente. Podemos realizar pesquisas de valor usando chaves. Idea is to use an appropriate hash function which does the key -> value mapping. Escolher uma boa função de hash depende do cenário.aplicações:

• em roteadores, para guardar o endereço IP -> par de localização para mecanismos de encaminhamento
• para efectuar a verificação se já existe um valor numa lista. A pesquisa Linear seria cara. Também podemos usar a estrutura de dados do conjunto para esta operação.

Programação Dinâmica

Programação Dinâmica (DP) é um método para resolver um problema complexo, dividindo-o em subproblemas mais simples. Resolvemos os subproblemas, lembramos de seus resultados e os usamos para resolver o problema complexo, rapidamente.

*escreve “1+1+1+1+1+1+1+1 =” numa folha de papel* o que é isso igual?
*Contagem* oito!
*another “1+” on the left * What about That?* * quickly * Nine!como sabias que eram nove tão rápido?você acabou de adicionar mais um, então você não precisa recontar porque se lembrou que havia oito! A programação dinâmica é apenas uma maneira chique de dizer ‘lembrando coisas para poupar tempo mais tarde’

aplicações:

• Existem muitos algoritmos e Aplicações DP, mas eu diria um e o mataria, o método Duckworth-Lewis em críquete.

exponenciação pela quadratura

digamos que você quer calcular 232. Normalmente iterávamos 32 vezes e encontrávamos o resultado. E se eu te disser que pode ser feito em 5 iterações?

exponenciação por exponenciação quadrada ou binária é um método geral para computação rápida de grandes potências inteiros positivos de um número em O(log2N). Não só isso, o método também é usado para computação de poderes de polinômios e matrizes quadradas.

Application:

• Calculation of large powers of a number is mostly required in RSA encryption. RSA também usa aritmética modular junto com exponenciação binária.

correspondência e Análise de texto

correspondência / pesquisa de padrões é um dos problemas mais importantes na ciência da Computação. Tem havido muita pesquisa sobre o tema, mas vamos recrutar apenas duas necessidades básicas para qualquer programador.o algoritmo de

KMP (correspondência de cadeias de caracteres)

O algoritmo de Knuth-Morris-Pratt é usado nos casos em que temos de corresponder a um padrão curto numa cadeia longa. Por exemplo, quando nós Ctrl+F uma palavra-chave em um documento, nós executamos o padrão correspondente em todo o documento.

expressão Regular (Análise de cadeia de caracteres)

muitas vezes temos de validar uma cadeia de caracteres analisando uma restrição predefinida. Ele é fortemente usado no desenvolvimento da web para o processamento de URL e correspondência.

algoritmos de teste de Primalidade

Existem formas determinísticas e probabilísticas de determinar se um dado número é primo ou não. Veremos ambos os caminhos determinísticos e probabilísticos (não determinísticos).

Sieve of Eratosthenes (deterministic)

If we have certain limit on the range of numbers, say determine all primes within range 100 to 1000 then Sieve is a way to go. O comprimento do intervalo é um fator crucial, porque temos que alocar certa quantidade de memória de acordo com o intervalo.

para qualquer número n, incrementalmente testando upto sqrt (n) (deterministic)

no caso de você querer verificar alguns números que são esparsamente espalhados por um longo intervalo (digamos 1 a 1012), Sieve não será capaz de alocar memória suficiente. Você pode verificar para cada número n atravessando apenas até sqrt (n) e realizar uma verificação de divisibilidade em n.

Fermat teste de primalidade e Miller–Rabin teste de primalidade (ambos são não determinísticos)

ambos são testes de compostura. Se um número é provado ser composto, então certamente não é um número primo. Miller-Rabin é um jogo mais sofisticado do que o de Fermat. na verdade, Miller-Rabin também tem uma variante determinística, mas então é um jogo de comércio entre a complexidade do tempo e precisão do algoritmo.aplicação:

• o uso mais importante dos números primos é na criptografia. Mais precisamente, eles são usados em criptografia e descriptografia no algoritmo RSA, que foi a primeira implementação de Criptosistemas de Chave Pública
• Outro uso é em funções de Hash usado em Tabelas de Hash