Raa'an voiman algoritmit selitetty

Raakavoiman algoritmit ovat juuri sellaisia ​​kuin ne kuulostavat - suoraviivaisista ongelmanratkaisumenetelmistä, jotka perustuvat pelkkään laskentatehoon ja yrittävät parantaa kaikkia tehokkuutta pikemminkin kuin edistyneiden tekniikoiden avulla.

Kuvittele esimerkiksi, että sinulla on pieni lukko, jossa on 4 numeroa, kukin 0-9. Unohdit yhdistelmän, mutta et halua ostaa toista riippulukkoa. Koska et muista yhtään numeroa, sinun on käytettävä raakaa voimamenetelmää lukon avaamiseksi.

Joten asetat kaikki numerot takaisin 0: ksi ja kokeile niitä yksitellen: 0001, 0002, 0003 ja niin edelleen, kunnes se avautuu. Pahimmassa tapauksessa yhdistelmän löytäminen vaatii 104 tai 10000 yritystä.

Klassinen esimerkki tietojenkäsittelytieteessä on matkustava myyjäongelma (TSP). Oletetaan, että myyjän on käytävä 10 kaupungissa eri puolilla maata. Kuinka määritetään järjestys, jossa näissä kaupungeissa tulisi käydä niin, että kokonaismatka minimoidaan?

Raa'an voiman ratkaisu on yksinkertaisesti laskea kokonaismatka jokaiselle mahdolliselle reitille ja valita sitten lyhin. Tämä ei ole erityisen tehokasta, koska on mahdollista poistaa monia mahdollisia reittejä älykkäillä algoritmeilla.

Raa'an voiman aikakompleksi on O (m n ) , joka kirjoitetaan joskus nimellä O (n * m). Joten jos etsimme "n" merkkijonoa "m" merkkijonosta käyttämällä raakaa voimaa, se vie meidät n * m yrittää.

Lisätietoja algoritmeista

Tietojenkäsittelytieteessä algoritmi on yksinkertainen joukko vaiheittaisia ​​menettelyjä tietyn ongelman ratkaisemiseksi. Algoritmit voidaan suunnitella suorittamaan laskutoimituksia, käsittelemään tietoja tai suorittamaan automaattisia päättelytehtäviä.

Näin Wikipedia määrittelee ne:

Algoritmi on tehokas menetelmä, joka voidaan ilmaista rajallisessa määrin tilaa ja aikaa ja tarkoin määritellyllä muodollisella kielellä funktion laskemiseksi. Alkuarvot alkutilasta ja alkusyötöstä (kenties tyhjästä), ohjeet kuvaavat laskennan, joka suoritettuna suoritetaan lopullisen määrän tarkkaan määriteltyjä peräkkäisiä tiloja läpi, mikä lopulta tuottaa "ulostulon" ja päättyy lopulliseen lopputilaan. Siirtyminen tilasta toiseen ei välttämättä ole deterministinen; jotkut algoritmit, jotka tunnetaan satunnaisalgoritmeina, sisältävät satunnaisen syötteen.

Algoritmin on noudatettava tiettyjä vaatimuksia:

  1. Tarkkuus: Jokainen prosessin vaihe on määritelty tarkasti.
  2. Tehokas laskettavuus: Jokainen prosessin vaihe voidaan suorittaa tietokoneella.
  3. Lopullisuus: Ohjelma lopulta lopetetaan onnistuneesti.

Joitakin yleisiä algoritmityyppejä ovat:

  • lajittelualgoritmit
  • hakualgoritmit
  • pakkausalgoritmit.

Algoritmien luokat sisältävät

  • Kaavio
  • Dynaaminen ohjelmointi
  • Lajittelu
  • Etsitään
  • Jouset
  • Matematiikka
  • Laskennallinen geometria
  • Optimointi
  • Sekalaiset.

Vaikka tekniset tiedot eivät ole algoritmien luokka, tietorakenteet ryhmitellään usein niiden kanssa.

Tehokkuus

Algoritmeja arvioidaan yleisimmin niiden tehokkuuden ja tehtävän suorittamiseen tarvittavien laskentaresurssien määrän perusteella.

Yleinen tapa algoritmin arvioimiseksi on tarkastella sen aikakompleksuutta. Tämä osoittaa kuinka algoritmin ajoaika kasvaa syötteen koon kasvaessa. Koska algoritmien on nykyään toimittava suurilla datatuloilla, on välttämätöntä, että algoritmeillamme on kohtuullisen nopea ajoaika.

Algoritmien lajittelu

Lajittelualgoritmeja on eri makuja tarpeen mukaan. Jotkut hyvin yleiset ja laajalti käytetyt ovat:

Quicksort

Ei ole lajittelukeskustelua, joka voisi päättyä ilman nopeaa lajittelua. Tässä on peruskäsite: Nopea lajittelu

Yhdistä lajittelu

Lajittelualgoritmi, joka perustuu käsitteeseen, kuinka lajitella taulukot, yhdistetään yhdeksi lajitelluksi taulukoksi. Lue lisää täältä: Mergesort

freeCodeCampin opetussuunnitelmassa korostetaan voimakkaasti algoritmien luomista. Tämä johtuu siitä, että algoritmien oppiminen on hyvä tapa harjoitella ohjelmointitaitoja. Haastattelijat testasivat yleisimmin ehdokkaita algoritmeilla kehittäjän työhaastattelujen aikana.

Kirjat algoritmeista JavaScriptissä:

Tietorakenteet JavaScriptissä

  • Ilmainen kirja, joka kattaa JavaScript-tietorakenteet
  • GitBook

JavaScript-tietorakenteiden ja algoritmien oppiminen - toinen painos

  • Kattaa olio-ohjelmoinnin, prototyyppisen perimisen, lajittelu- ja hakualgoritmit, pikalajittelun, yhdistämislajittelun, binäärihakupuut ja edistyneet algoritmikäsitteet
  • Amazon
  • ISBN-13: 978-1785285493

Tietorakenteet ja algoritmit JavaScriptillä: Klassisten laskentamenetelmien tuominen verkkoon

  • Kattaa rekursio-, lajittelu- ja hakualgoritmit, linkitetyt luettelot ja binaariset hakupuut.
  • Amazon
  • ISBN-13: 978-1449364939