Algoritmos de força bruta explicados

Algoritmos de força bruta são exatamente o que parecem - métodos diretos de resolver um problema que dependem de poder de computação absoluto e tentar todas as possibilidades em vez de técnicas avançadas para melhorar a eficiência.

Por exemplo, imagine que você tem um pequeno cadeado com 4 dígitos, cada um de 0-9. Você esqueceu sua combinação, mas não quer comprar outro cadeado. Já que você não consegue se lembrar de nenhum dos dígitos, você tem que usar um método de força bruta para abrir a fechadura.

Portanto, você define todos os números de volta para 0 e os tenta um por um: 0001, 0002, 0003 e assim por diante até que seja aberto. Na pior das hipóteses, seriam necessárias 104, ou 10.000 tentativas para encontrar sua combinação.

Um exemplo clássico em ciência da computação é o problema do caixeiro viajante (TSP). Suponha que um vendedor precise visitar 10 cidades em todo o país. Como determinar a ordem em que essas cidades devem ser visitadas de forma que a distância total percorrida seja minimizada?

A solução de força bruta é simplesmente calcular a distância total para cada rota possível e então selecionar a mais curta. Isso não é particularmente eficiente porque é possível eliminar muitas rotas possíveis por meio de algoritmos inteligentes.

A complexidade de tempo da força bruta é O (m n ) , que às vezes é escrita como O (n * m). Portanto, se tivéssemos que pesquisar uma seqüência de caracteres "n" em uma seqüência de caracteres "m" usando força bruta, seriam necessárias n * m tentativas.

Mais informações sobre algoritmos

Em ciência da computação, um algoritmo é simplesmente um conjunto de procedimentos passo a passo para resolver um determinado problema. Algoritmos podem ser projetados para executar cálculos, processar dados ou executar tarefas de raciocínio automatizadas.

Veja como a Wikipedia os define:

Um algoritmo é um método eficaz que pode ser expresso em uma quantidade finita de espaço e tempo e em uma linguagem formal bem definida para o cálculo de uma função. A partir de um estado inicial e entrada inicial (talvez vazio), as instruções descrevem um cálculo que, quando executado, prossegue por meio de um número finito de estados sucessivos bem definidos, eventualmente produzindo "saída" e terminando em um estado final final. A transição de um estado para o próximo não é necessariamente determinística; alguns algoritmos, conhecidos como algoritmos randomizados, incorporam entrada aleatória.

Existem certos requisitos que um algoritmo deve cumprir:

  1. Definição: cada etapa do processo é definida com precisão.
  2. Computabilidade efetiva: Cada etapa do processo pode ser realizada por um computador.
  3. Finitude: O programa será encerrado com sucesso.

Alguns tipos comuns de algoritmos incluem:

  • algoritmos de classificação
  • algoritmos de busca
  • algoritmos de compressão.

Classes de algoritmos incluem

  • Gráfico
  • Programaçao dinamica
  • Ordenação
  • Procurando
  • Cordas
  • Matemática
  • Geometria Computacional
  • Otimização
  • Diversos.

Embora tecnicamente não seja uma classe de algoritmos, as estruturas de dados costumam ser agrupadas com eles.

Eficiência

Os algoritmos são mais comumente julgados por sua eficiência e a quantidade de recursos de computação de que precisam para concluir sua tarefa.

Uma maneira comum de avaliar um algoritmo é observar sua complexidade de tempo. Isso mostra como o tempo de execução do algoritmo aumenta conforme o tamanho da entrada aumenta. Como os algoritmos hoje precisam operar em grandes entradas de dados, é essencial que nossos algoritmos tenham um tempo de execução razoavelmente rápido.

Algoritmos de classificação

Os algoritmos de classificação vêm em vários sabores, dependendo da sua necessidade. Alguns, muito comuns e amplamente utilizados são:

Ordenação rápida

Não há discussão de classificação que possa terminar sem uma classificação rápida. Aqui está o conceito básico: Classificação Rápida

Mergesort

Um algoritmo de classificação que se baseia no conceito de como as matrizes classificadas são mescladas para fornecer uma matriz classificada. Leia mais sobre isso aqui: Mergesort

O currículo do freeCodeCamp enfatiza fortemente a criação de algoritmos. Isso ocorre porque o aprendizado de algoritmos é uma boa maneira de praticar as habilidades de programação. Os entrevistadores costumam testar os candidatos em algoritmos durante as entrevistas de emprego do desenvolvedor.

Livros sobre algoritmos em JavaScript:

Estruturas de dados em JavaScript

  • Livro grátis que cobre estruturas de dados em JavaScript
  • GitBook

Aprendendo Estruturas de Dados e Algoritmos de JavaScript - Segunda Edição

  • Abrange programação orientada a objetos, herança prototípica, algoritmos de classificação e pesquisa, classificação rápida, classificação combinada, árvores de pesquisa binárias e conceitos de algoritmo avançado
  • Amazonas
  • ISBN-13: 978-1785285493

Estruturas de dados e algoritmos com JavaScript: trazendo abordagens clássicas de computação para a web

  • Abrange algoritmos de recursão, classificação e pesquisa, listas vinculadas e árvores de pesquisa binárias.
  • Amazonas
  • ISBN-13: 978-1449364939