Razloženi algoritmi surove sile

Algoritmi Brute Force so točno takšni, kot se slišijo - enostavne metode reševanja problema, ki se zanašajo na čisto računalniško moč in preizkušanje vseh možnosti in ne naprednih tehnik za izboljšanje učinkovitosti.

Na primer, predstavljajte si majhno ključavnico s štirimestnimi številkami, od 0 do 9. Pozabili ste svojo kombinacijo, vendar ne želite kupiti nove ključavnice. Ker se nobene številke ne morete spomniti, morate za odpiranje ključavnice uporabiti metodo surove sile.

Torej nastavite vse številke nazaj na 0 in jih preizkusite eno za drugo: 0001, 0002, 0003 in tako naprej, dokler se ne odpre. V najslabšem primeru bi trajalo 104 ali 10.000 poskusov, da bi našli vašo kombinacijo.

Klasičen primer v računalništvu je problem trgovskega potnika (TSP). Recimo, da mora prodajalec obiskati 10 mest po državi. Kako določiti vrstni red obiska teh mest, tako da je skupna prevožena razdalja čim manjša?

Rešitev surove sile je preprosto izračunati skupno razdaljo za vsako možno pot in nato izbrati najkrajšo. To ni posebej učinkovito, ker je s pametnimi algoritmi mogoče odpraviti številne možne poti.

Časovna zapletenost surove sile je O (m n ) , kar včasih zapišemo kot O (n * m). Torej, če bi iskali niz znakov "n" v nizu znakov "m" z uporabo surove sile, bi to potrebovalo n * m poskusov.

Več informacij o algoritmih

V računalništvu je algoritem preprosto niz postopnih postopkov za rešitev danega problema. Algoritmi so lahko zasnovani za izvajanje izračunov, obdelavo podatkov ali izvajanje avtomatiziranih nalog sklepanja.

Wikipedia jih definira tako:

Algoritem je učinkovita metoda, ki jo lahko izrazimo v končni količini prostora in časa ter v natančno določenem formalnem jeziku za izračun funkcije. Navodila opisujejo izračun, ki se začne od začetnega stanja in začetnega vnosa (morda prazen), ki po končanem številu natančno definiranih zaporednih stanj sčasoma ustvari "izhod" in konča v končnem končnem stanju. Prehod iz enega stanja v naslednje ni nujno determinističen; nekateri algoritmi, znani kot naključni algoritmi, vključujejo naključne vnose.

Obstajajo nekatere zahteve, ki jih mora izpolnjevati algoritem:

  1. Določenost: Vsak korak v postopku je natančno naveden.
  2. Učinkovita izračunljivost: Vsak korak v procesu lahko izvede računalnik.
  3. Končnost: Program se bo sčasoma uspešno zaključil.

Nekatere pogoste vrste algoritmov vključujejo:

  • algoritmi za razvrščanje
  • algoritmi iskanja
  • algoritmi stiskanja.

Razredi algoritmov vključujejo

  • Graf
  • Dinamično programiranje
  • Razvrščanje
  • Iskanje
  • Strune
  • Matematika
  • Računalniška geometrija
  • Optimizacija
  • Razno.

Čeprav tehnično niso razred algoritmov, so z njimi pogosto združene podatkovne strukture.

Učinkovitost

Algoritme najpogosteje presojamo po njihovi učinkovitosti in količini računalniških virov, ki jih potrebujejo za dokončanje svoje naloge.

Pogost način ocenjevanja algoritma je pogled na njegovo časovno zapletenost. To kaže, kako se čas delovanja algoritma povečuje z naraščanjem vhodne velikosti. Ker morajo algoritmi danes delovati na velikih vnosih podatkov, je za naše algoritme nujno, da imajo razmeroma hiter čas delovanja.

Algoritmi za razvrščanje

Algoritmi za razvrščanje so različnih okusov, odvisno od vaše potrebe. Nekateri zelo pogosti in široko uporabljeni so:

Quicksort

Ni razprave o razvrščanju, ki bi se lahko končala brez hitrega razvrščanja. Tu je osnovni koncept: hitro razvrščanje

Mergesort

Algoritem za razvrščanje, ki se opira na koncept razvrščanja nizov, se združi, da se dobijo razvrščena polja. Več o tem preberite tukaj: Mergesort

Učni načrt freeCodeCampa močno poudarja ustvarjanje algoritmov. To je zato, ker je učenje algoritmov dober način za vadbo programiranja. Anketarji najpogosteje preizkušajo kandidate na algoritmih med razgovori za delo razvijalcev.

Knjige o algoritmih v JavaScript:

Podatkovne strukture v JavaScript

  • Brezplačna knjiga, ki zajema podatkovne strukture v JavaScript
  • GitBook

Učenje struktur in algoritmov podatkov JavaScript - druga izdaja

  • Zajema objektno usmerjeno programiranje, prototipsko dedovanje, algoritme za razvrščanje in iskanje, hitro sortiranje, spajanje, binarna drevesa iskanja in napredne koncepte algoritmov
  • Amazonka
  • ISBN-13: 978-1785285493

Podatkovne strukture in algoritmi z JavaScriptom: prinašanje klasičnih računalniških pristopov v splet

  • Zajema algoritme za rekurzijo, razvrščanje in iskanje, povezane sezname in binarna drevesa iskanja.
  • Amazonka
  • ISBN-13: 978-1449364939