Artigo original: https://www.freecodecamp.org/news/brute-force-algorithms-explained/

Algoritmos de força bruta são exatamente o que parecem – métodos diretos de resolver um problema que dependem de poder computacional puro e de 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 uma combinação 4 números, cada um deles indo de 0 a 9. Você esquece sua combinação, mas você não quer comprar outro cadeado. Como você não consegue se lembrar de nenhum dos números, precisa usar um método de força bruta para abrir a fechadura.

Você, então, insere todos os números no cadeado a partir do zero e os experimenta um a um: 0001, 0002, 0003 e assim sucessivamente até que ele abra. Na pior das hipóteses, seriam necessárias 104, ou 10 mil 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 precisa visitar 10 cidades em todo o país. Como determinar a ordem em que essas cidades devem ser visitadas de modo que a distância total percorrida seja minimizada?

A solução da força bruta é simplesmente calcular a distância total para toda possibilidade de rota possível e, depois, selecionar a mais curta. Isso não é particularmente eficiente, pois é possível eliminar muitas rotas através algoritmos inteligentes.

A complexidade de tempo da força bruta é O(mn), que às vezes é escrito como O(n*m) . Então, se fôssemos procurar uma string de "n" caracteres em uma string de "m" caracteres usando força bruta, faríamos n * m tentativas.

Mais informações sobre algoritmos

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

Veja como a Wikipédia 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 calcular uma função. Partindo de um estado e de uma entrada (talvez vazia) iniciais, as instruções descrevem uma computação que, quando executada, prossegue através de um número finito de estados sucessivos bem definidos, eventualmente produzindo uma "saída" e terminando em um estado final. A transição de um estado para o seguinte não é necessariamente determinista; alguns algoritmos, conhecidos como algoritmos aleatórios, incorporam entradas aleatórias.

Existem certos requisitos que um algoritmo deve cumprir:

  1. Definitividade: cada etapa do processo é declarada com precisão.
  2. Computabilidade efetiva: cada etapa do processo pode ser realizada por um computador.
  3. Finitude: o programa terminará eventualmente com sucesso.

Alguns tipos comuns de algoritmos incluem:

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

As classes de algoritmos incluem:

  • de grafos
  • de programação dinâmica
  • de ordenação
  • de busca
  • de cordas (strings)
  • matemáticos
  • de geometria computacional
  • de otimização
  • diversas

Embora tecnicamente não sejam uma classe de algoritmos, as estruturas de dados são frequentemente agrupadas com eles.

Eficiência

Os algoritmos são mais comumente julgados por sua eficiência e pela quantidade de recursos de computação necessários 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 à medida que o tamanho da entrada aumenta. Como os algoritmos de hoje precisam operar em grandes entradas de dados, é essencial que nossos algoritmos tenham um tempo de execução razoavelmente rápido.

Algoritmos de ordenação

Os algoritmos de ordenação são de vários tipos, dependendo de sua necessidade. Alguns, muito comuns e amplamente utilizados, são:

Quicksort (Ordenação rápida)

Não há discussão sobre ordenação que possa terminar sem a ordenação rápida. Aqui está o conceito básico (em inglês): Quick Sort

Mergesort

Um algoritmo de ordenação que se baseia no conceito de como os arrays ordenados são mesclados para gerar um array ordenado. Leia mais sobre isso aqui (em inglês): Mergesort

O currículo do freeCodeCamp enfatiza fortemente a criação de algoritmos. Isso ocorre porque aprender algoritmos é uma boa maneira de praticar suas habilidades em programação. Os entrevistadores geralmente testam os candidatos quanto aos algoritmos durante as entrevistas de emprego para desenvolvedores.

Livros sobre algoritmos em JavaScript (em inglês):

Data Structures in JavaScript

  • Livro gratuito que cobre as estruturas de dados em JavaScript
  • GitBook

Learning JavaScript Data Structures and Algorithms - Second Edition

  • Trata de programação orientada a objetos, herança prototípica, algoritmos de ordenação e busca, quicksort, mergesort, árvores binárias de busca e conceitos avançados de algoritmos
  • Amazon
  • ISBN-13: 978-1785285493

Data Structures and Algorithms with JavaScript: Bringing classic computing approaches to the Web

  • Trata de recursão, algoritmos de ordenação e busca, listas vinculadas e árvores binárias de busca.
  • Amazon
  • ISBN-13: 978-1449364939