Izskaidroti brutālu spēku algoritmi

Brutālu spēku algoritmi ir tieši tādi, kādi tie izklausās - vienkāršas problēmas risināšanas metodes, kuru efektivitātes uzlabošanai paļaujas uz milzīgu skaitļošanas jaudu un izmēģina visas iespējas, nevis uzlabotas metodes.

Piemēram, iedomājieties, ka jums ir maza piekaramā atslēga ar 4 cipariem, katrs no 0 līdz 9. Jūs aizmirsāt savu kombināciju, bet nevēlaties iegādāties citu piekaramo atslēgu. Tā kā jūs nevarat atcerēties nevienu ciparu, slēdzenes atvēršanai jāizmanto brutāla spēka metode.

Tātad jūs iestatāt visus skaitļus atpakaļ uz 0 un mēģiniet tos pa vienam: 0001, 0002, 0003 un tā tālāk, līdz tas tiek atvērts. Sliktākajā gadījumā jūsu kombinācijas atrašanai būtu nepieciešami 104 vai 10 000 mēģinājumi.

Klasisks piemērs datorzinātnēs ir ceļojošā pārdevēja problēma (TSP). Pieņemsim, ka pārdevējam jāapmeklē 10 pilsētas visā valstī. Kā var noteikt kārtību, kādā šīs pilsētas jāapmeklē, lai kopējais nobrauktais attālums būtu minimāls?

Brutālā spēka risinājums ir vienkārši aprēķināt kopējo attālumu katram iespējamam maršrutam un pēc tam izvēlēties īsāko. Tas nav īpaši efektīvi, jo ar gudru algoritmu palīdzību ir iespējams novērst daudzus iespējamos maršrutus.

Brutālā spēka laika sarežģītība ir O (m n ) , ko dažreiz raksta kā O (n * m). Tātad, ja mēs meklētu "n" rakstzīmju virkni "m" rakstzīmju virknē, izmantojot brutālu spēku, tas prasītu mums n * m mēģinājumus.

Plašāka informācija par algoritmiem

Datorzinātnēs algoritms ir vienkārši soli pa solim noteiktas procedūras kopums, lai atrisinātu konkrēto problēmu. Algoritmus var izstrādāt aprēķinu veikšanai, datu apstrādei vai automatizētu spriešanas uzdevumu veikšanai.

Lūk, kā Vikipēdija tos definē:

Algoritms ir efektīva metode, kuru funkcijas aprēķināšanai var izteikt ierobežotā telpā un laikā un precīzi definētā formālā valodā. Sākot ar sākotnējo stāvokli un sākotnējo ievadi (iespējams, tukšu), instrukcijās aprakstīts aprēķins, kas, izpildot, notiek caur noteiktu skaitu skaidri definētu secīgu stāvokļu, galu galā radot “izvadi” un beidzot ar galīgo beigu stāvokli. Pāreja no viena stāvokļa uz nākamo ne vienmēr ir deterministiska; daži algoritmi, kas pazīstami kā randomizēti algoritmi, ietver nejaušu ievadi.

Algoritmam ir jāievēro noteiktas prasības:

  1. Noteiktība: katrs procesa posms ir precīzi noteikts.
  2. Efektīva skaitāmība: katru procesa posmu var veikt ar datoru.
  3. Galīgums: programma galu galā tiks veiksmīgi pārtraukta.

Daži no izplatītākajiem algoritmu veidiem ir:

  • šķirošanas algoritmi
  • meklēšanas algoritmi
  • saspiešanas algoritmi.

Algoritmu klases ietver

  • Grafiks
  • Dinamiskā programmēšana
  • Šķirošana
  • Meklēšana
  • Stīgas
  • Matemātika
  • Skaitļotā ģeometrija
  • Optimizācija
  • Dažādi.

Lai arī tehniski tā nav algoritmu klase, datu struktūras bieži tiek grupētas kopā ar tām.

Efektivitāte

Algoritmus visbiežāk vērtē pēc to efektivitātes un skaitļošanas resursu apjoma, kas tiem nepieciešams uzdevuma izpildei.

Parasti algoritma novērtēšanas veids ir tā laika sarežģītības pārbaude. Tas parāda, kā algoritma darbības laiks pieaug, pieaugot ievades lielumam. Tā kā algoritmiem šodien ir jādarbojas ar lielām datu ievadēm, ir svarīgi, lai mūsu algoritmiem būtu pietiekami ātrs darbības laiks.

Algoritmu šķirošana

Šķirošanas algoritmiem ir dažādas garšas iespējas atkarībā no jūsu nepieciešamības. Daži ļoti izplatīti un plaši izmantoti ir:

Quicksort

Nav šķirošanas diskusiju, kuru varētu pabeigt bez ātras kārtošanas. Šeit ir pamatjēdziens: ātra kārtošana

Apvienot

Šķirošanas algoritms, kas balstās uz koncepciju, kā kārtot masīvus, tiek apvienots, lai iegūtu vienu sakārtotu masīvu. Vairāk par to lasiet šeit: Mergesort

freeCodeCamp mācību programma ļoti uzsver algoritmu izveidi. Tas ir tāpēc, ka algoritmu apguve ir labs veids, kā praktizēt programmēšanas prasmes. Intervētāji izstrādātāju darba intervijās visbiežāk pārbauda kandidātus uz algoritmiem.

Grāmatas par algoritmiem JavaScript valodā:

Datu struktūras JavaScript

  • Bezmaksas grāmata, kas aptver JavaScript datu struktūras
  • GitBook

JavaScript datu struktūru un algoritmu apgūšana - otrais izdevums

  • Ietver objektorientētu programmēšanu, prototipa mantošanu, šķirošanas un meklēšanas algoritmus, ātrsortu, apvienoto šķirošanu, bināros meklēšanas kokus un uzlabotos algoritmu jēdzienus
  • Amazon
  • ISBN-13: 978-1785285493

Datu struktūras un algoritmi ar JavaScript: klasisko skaitļošanas pieeju ieviešana tīmeklī

  • Ietver rekursijas, šķirošanas un meklēšanas algoritmus, saistītos sarakstus un bināros meklēšanas kokus.
  • Amazon
  • ISBN-13: 978-1449364939