Brute Force algoritmer forklaret

Brute Force-algoritmer er nøjagtigt, hvad de lyder som - enkle metoder til at løse et problem, der er afhængig af ren computerkraft og forsøger enhver mulighed snarere end avancerede teknikker for at forbedre effektiviteten.

Forestil dig f.eks. At du har en lille hængelås med 4 cifre, hver fra 0-9. Du har glemt din kombination, men du vil ikke købe en anden hængelås. Da du ikke kan huske nogen af ​​cifrene, skal du bruge en brute force-metode til at åbne låsen.

Så du sætter alle numrene tilbage til 0 og prøver dem en efter en: 0001, 0002, 0003 og så videre, indtil den åbner. I værste fald tager det 104 eller 10.000 forsøg at finde din kombination.

Et klassisk eksempel inden for datalogi er rejsendesælgerproblemet (TSP). Antag, at en sælger skal besøge 10 byer over hele landet. Hvordan bestemmer man rækkefølgen, i hvilken disse byer skal besøges, således at den samlede tilbagelagte afstand minimeres?

Brute force-løsningen er simpelthen at beregne den samlede afstand for hver mulig rute og derefter vælge den korteste. Dette er ikke særlig effektivt, fordi det er muligt at eliminere mange mulige ruter gennem smarte algoritmer.

Tidenes kompleksitet af brute force er O (m n ) , som undertiden skrives som O (n * m). Så hvis vi skulle søge efter en streng af "n" tegn i en streng af "m" tegn ved hjælp af brutal kraft, ville det tage os n * m forsøg.

Flere oplysninger om algoritmer

I datalogi er en algoritme simpelthen et sæt trin for trin-procedure for at løse et givet problem. Algoritmer kan designes til at udføre beregninger, behandle data eller udføre automatiserede ræsonnementsopgaver.

Sådan definerer Wikipedia dem:

En algoritme er en effektiv metode, der kan udtrykkes inden for en begrænset mængde plads og tid og i et veldefineret formelt sprog til beregning af en funktion. Startende fra en indledende tilstand og indledende input (måske tom), beskriver instruktionerne en beregning, der, når den udføres, fortsætter gennem et endeligt antal veldefinerede successive tilstande, og til sidst producerer "output" og afsluttes ved en endelig afslutningstilstand. Overgangen fra en tilstand til en anden er ikke nødvendigvis deterministisk; nogle algoritmer, kendt som randomiserede algoritmer, indeholder tilfældig input.

Der er visse krav, som en algoritme skal overholde:

  1. Definitivitet: Hvert trin i processen er nøjagtigt angivet.
  2. Effektiv beregningsevne: Hvert trin i processen kan udføres af en computer.
  3. Endelighed: Programmet afsluttes til sidst med succes.

Nogle almindelige typer algoritmer inkluderer:

  • sorteringsalgoritmer
  • søgealgoritmer
  • komprimeringsalgoritmer.

Klasser af algoritmer inkluderer

  • Kurve
  • Dynamisk programmering
  • Sortering
  • Søger
  • Strenge
  • Matematik
  • Computational Geometry
  • Optimering
  • Diverse.

Selvom det teknisk set ikke er en klasse af algoritmer, grupperes datastrukturer ofte med dem.

Effektivitet

Algoritmer bedømmes oftest ud fra deres effektivitet og mængden af ​​computerressourcer, de har brug for for at fuldføre deres opgave.

En almindelig måde at evaluere en algoritme på er at se på dens tidskompleksitet. Dette viser, hvordan algoritmens driftstid vokser, når inputstørrelsen vokser. Da algoritmerne i dag skal operere på store dataindgange, er det vigtigt for vores algoritmer at have en rimelig hurtig driftstid.

Sorteringsalgoritmer

Sorteringsalgoritmer findes i forskellige varianter afhængigt af din nødvendighed. Nogle, meget almindelige og meget anvendte, er:

Quicksort

Der er ingen sorteringsdiskussion, som kan afslutte uden hurtig sortering. Her er det grundlæggende koncept: Hurtig sortering

Fusion

En sorteringsalgoritme, der er afhængig af konceptet, hvordan arrangerede sorteres, flettes for at give en sorteret række. Læs mere om det her: Mergesort

freeCodeCamp's læseplan lægger stærkt vægt på at skabe algoritmer. Dette skyldes, at indlæringsalgoritmer er en god måde at øve programmeringsfærdigheder på. Interviewere tester oftest kandidater på algoritmer under udviklerjobsinterviews.

Bøger om algoritmer i JavaScript:

Datastrukturer i JavaScript

  • Gratis bog, der dækker datastrukturer i JavaScript
  • GitBook

Læring af JavaScript-datastrukturer og algoritmer - Anden udgave

  • Dækker objektorienteret programmering, prototypisk arv, sorterings- og søgealgoritmer, quicksort, mergesort, binære søgetræer og avancerede algoritmekoncepter
  • Amazon
  • ISBN-13: 978-1785285493

Datastrukturer og algoritmer med JavaScript: Bringer klassiske computingstilgange til Internettet

  • Dækker rekursions-, sorterings- og søgealgoritmer, sammenkædede lister og binære søgetræer.
  • Amazon
  • ISBN-13: 978-1449364939