Brute Force-algoritmer forklart

Brute Force-algoritmer er akkurat det de høres ut som - enkle metoder for å løse et problem som er avhengig av ren datakraft og prøver alle muligheter i stedet for avanserte teknikker for å forbedre effektiviteten.

Tenk deg for eksempel at du har en liten hengelås med 4 sifre, hver fra 0-9. Du glemte kombinasjonen din, men du vil ikke kjøpe en annen hengelås. Siden du ikke kan huske noen av sifrene, må du bruke en brute force-metode for å åpne låsen.

Så du setter alle tallene tilbake til 0 og prøver dem en etter en: 0001, 0002, 0003 og så videre til den åpnes. I verste fall vil det ta 104 eller 10 000 forsøk å finne din kombinasjon.

Et klassisk eksempel innen informatikk er reisendeselgerproblemet (TSP). Anta at en selger må besøke 10 byer over hele landet. Hvordan bestemmer man rekkefølgen som byene skal besøkes i, slik at den totale tilbakelagte avstanden minimeres?

Brute force-løsningen er ganske enkelt å beregne den totale avstanden for hver mulig rute og deretter velge den korteste. Dette er ikke spesielt effektivt fordi det er mulig å eliminere mange mulige ruter gjennom smarte algoritmer.

Tidskompleksiteten til brute force er O (m n ) , som noen ganger skrives som O (n * m). Så hvis vi skulle søke etter en streng med "n" -tegn i en streng med "m" -tegn ved hjelp av brute force, ville det tatt oss n * m forsøk.

Mer informasjon om algoritmer

I datavitenskap er en algoritme rett og slett et trinnvis fremgangsmåte for å løse et gitt problem. Algoritmer kan utformes for å utføre beregninger, behandle data eller utføre automatiserte resoneringsoppgaver.

Slik definerer Wikipedia dem:

En algoritme er en effektiv metode som kan uttrykkes innen en begrenset tid og tid og i et veldefinert formelt språk for beregning av en funksjon. Fra en starttilstand og innledende inngang (kanskje tom), beskriver instruksjonene en beregning som, når den utføres, fortsetter gjennom et endelig antall veldefinerte suksessive tilstander, og til slutt produserer "utdata" og avsluttes i en endelig slutttilstand. Overgangen fra en tilstand til en annen er ikke nødvendigvis deterministisk; noen algoritmer, kjent som randomiserte algoritmer, inneholder tilfeldig inngang.

Det er visse krav som en algoritme må overholde:

  1. Definitivitet: Hvert trinn i prosessen er presist oppgitt.
  2. Effektiv beregnbarhet: Hvert trinn i prosessen kan utføres av en datamaskin.
  3. Finhet: Programmet vil til slutt avsluttes.

Noen vanlige typer algoritmer inkluderer:

  • sorteringsalgoritmer
  • søkealgoritmer
  • komprimeringsalgoritmer.

Klasser av algoritmer inkluderer

  • Kurve
  • Dynamisk programmering
  • Sortering
  • Søker
  • Strenger
  • Matte
  • Computational Geometry
  • Optimalisering
  • Diverse.

Selv om det teknisk sett ikke er en klasse algoritmer, er datastrukturer ofte gruppert med dem.

Effektivitet

Algoritmer blir oftest bedømt av effektiviteten og mengden databehandlingsressurser de trenger for å fullføre oppgaven.

En vanlig måte å evaluere en algoritme på er å se på tidskompleksiteten. Dette viser hvordan algoritmens kjøretid vokser når inngangsstørrelsen vokser. Siden algoritmene i dag må operere på store datainnganger, er det viktig at algoritmene våre har en rimelig rask kjøretid.

Sorteringsalgoritmer

Sorteringsalgoritmer kommer i forskjellige smaker, avhengig av din nødvendighet. Noen, veldig vanlige og mye brukt er:

Quicksort

Det er ingen sorteringsdiskusjon som kan avsluttes uten rask sortering. Her er grunnkonseptet: Rask sortering

Fusjonssort

En sorteringsalgoritme som er avhengig av konseptet hvordan man sorterer matriser blir slått sammen for å gi en sortert matrise. Les mer om det her: Mergesort

freeCodeCamps læreplan legger vekt på å lage algoritmer. Dette er fordi læringsalgoritmer er en god måte å øve på programmeringsferdigheter på. Intervjuer tester oftest kandidater på algoritmer under utviklerjobbintervjuer.

Bøker om algoritmer i JavaScript:

Datastrukturer i JavaScript

  • Gratis bok som dekker datastrukturer i JavaScript
  • GitBook

Learning JavaScript Datastrukturer og algoritmer - Andre utgave

  • Dekker objektorientert programmering, prototypisk arv, sorterings- og søkealgoritmer, kviksort, sammenslåing, binære søketrær og avanserte algoritmekonsepter
  • Amazon
  • ISBN-13: 978-1785285493

Datastrukturer og algoritmer med JavaScript: Bringer klassiske databehandlingsmetoder til Internett

  • Dekker rekursjons-, sorterings- og søkealgoritmer, koblede lister og binære søketrær.
  • Amazon
  • ISBN-13: 978-1449364939