Spiegazione degli algoritmi di forza bruta

Gli algoritmi di forza bruta sono esattamente come suonano: metodi semplici per risolvere un problema che si basano sulla pura potenza di calcolo e provano ogni possibilità piuttosto che tecniche avanzate per migliorare l'efficienza.

Ad esempio, immagina di avere un piccolo lucchetto con 4 cifre, ciascuna da 0 a 9. Hai dimenticato la tua combinazione, ma non vuoi comprare un altro lucchetto. Dal momento che non ricordi nessuna delle cifre, devi usare un metodo di forza bruta per aprire il lucchetto.

Quindi reimposti tutti i numeri su 0 e provali uno per uno: 0001, 0002, 0003 e così via fino a quando non si apre. Nel peggiore dei casi, ci vorrebbero 104 o 10.000 tentativi per trovare la tua combinazione.

Un classico esempio in informatica è il problema del venditore ambulante (TSP). Supponiamo che un venditore debba visitare 10 città in tutto il paese. Come si determina l'ordine in cui quelle città dovrebbero essere visitate in modo tale da ridurre al minimo la distanza totale percorsa?

La soluzione della forza bruta consiste semplicemente nel calcolare la distanza totale per ogni percorso possibile e quindi selezionare quello più breve. Ciò non è particolarmente efficiente perché è possibile eliminare molti percorsi possibili tramite algoritmi intelligenti.

La complessità temporale della forza bruta è O (m n ) , che a volte è scritta come O (n * m). Quindi, se dovessimo cercare una stringa di caratteri "n" in una stringa di caratteri "m" usando la forza bruta, ci vorrebbero n * m tentativi.

Ulteriori informazioni sugli algoritmi

In informatica, un algoritmo è semplicemente un insieme di procedure passo passo per risolvere un dato problema. Gli algoritmi possono essere progettati per eseguire calcoli, elaborare dati o eseguire attività di ragionamento automatizzate.

Ecco come li definisce Wikipedia:

Un algoritmo è un metodo efficace che può essere espresso in una quantità finita di spazio e tempo e in un linguaggio formale ben definito per il calcolo di una funzione. Partendo da uno stato iniziale e da un input iniziale (forse vuoto), le istruzioni descrivono un calcolo che, una volta eseguito, procede attraverso un numero finito di stati successivi ben definiti, producendo eventualmente “output” e terminando in uno stato finale finale. Il passaggio da uno stato all'altro non è necessariamente deterministico; alcuni algoritmi, noti come algoritmi randomizzati, incorporano input casuale.

Ci sono alcuni requisiti che un algoritmo deve rispettare:

  1. Definitività: ogni fase del processo è definita con precisione.
  2. Calcolabilità effettiva: ogni fase del processo può essere eseguita da un computer.
  3. Finitezza: il programma alla fine terminerà con successo.

Alcuni tipi comuni di algoritmi includono:

  • algoritmi di ordinamento
  • algoritmi di ricerca
  • algoritmi di compressione.

Le classi di algoritmi includono

  • Grafico
  • Programmazione dinamica
  • Ordinamento
  • Ricerca
  • stringhe
  • Matematica
  • Geometria computazionale
  • Ottimizzazione
  • Miscellanea.

Sebbene tecnicamente non sia una classe di algoritmi, le strutture dati sono spesso raggruppate con essi.

Efficienza

Gli algoritmi vengono più comunemente giudicati in base alla loro efficienza e alla quantità di risorse di elaborazione necessarie per completare il loro compito.

Un modo comune per valutare un algoritmo è guardare alla sua complessità temporale. Questo mostra come il tempo di esecuzione dell'algoritmo cresce al crescere della dimensione dell'input. Poiché gli algoritmi oggi devono operare su grandi input di dati, è essenziale che i nostri algoritmi abbiano un tempo di esecuzione ragionevolmente veloce.

Algoritmi di ordinamento

Gli algoritmi di ordinamento sono disponibili in vari gusti a seconda delle tue necessità. Alcuni, molto comuni e ampiamente utilizzati sono:

Quicksort

Non esiste una discussione sull'ordinamento che possa terminare senza l'ordinamento rapido. Ecco il concetto di base: Ordinamento rapido

Mergesort

Un algoritmo di ordinamento che si basa sul concetto di come gli array ordinati vengono uniti per fornire un array ordinato. Per saperne di più qui: Mergesort

Il curriculum di freeCodeCamp enfatizza fortemente la creazione di algoritmi. Questo perché gli algoritmi di apprendimento sono un buon modo per esercitare le abilità di programmazione. Gli intervistatori testano più comunemente i candidati sugli algoritmi durante i colloqui di lavoro con gli sviluppatori.

Libri sugli algoritmi in JavaScript:

Strutture dati in JavaScript

  • Libro gratuito che copre le strutture dati in JavaScript
  • GitBook

Apprendimento di strutture dati e algoritmi JavaScript - Seconda edizione

  • Copre la programmazione orientata agli oggetti, l'ereditarietà prototipale, gli algoritmi di ordinamento e ricerca, quicksort, mergesort, alberi di ricerca binari e concetti avanzati di algoritmi
  • Amazon
  • ISBN-13: 978-1785285493

Strutture dati e algoritmi con JavaScript: portare gli approcci informatici classici al Web

  • Copre la ricorsione, l'ordinamento e la ricerca di algoritmi, elenchi collegati e alberi di ricerca binari.
  • Amazon
  • ISBN-13: 978-1449364939