Objašnjeni algoritmi grube sile

Algoritmi grube sile upravo su ono što zvuče - izravne metode rješavanja problema koje se oslanjaju na čistu računarsku snagu i iskušavanje svake mogućnosti, a ne naprednih tehnika za poboljšanje učinkovitosti.

Na primjer, zamislite da imate mali lokot s 4 znamenke, svaka od 0 do 9. Zaboravili ste svoju kombinaciju, ali ne želite kupiti još jedan lokot. Budući da se ne možete sjetiti niti jedne znamenke, morate otvoriti bravu metodom grube sile.

Dakle, vratite sve brojeve na 0 i pokušajte ih jedan po jedan: 0001, 0002, 0003 i tako dalje dok se ne otvori. U najgorem slučaju trebalo bi 104 ili 10 000 pokušaja da pronađete vašu kombinaciju.

Klasičan primjer u računalnoj znanosti je problem trgovačkog putnika (TSP). Pretpostavimo da prodavač mora posjetiti 10 gradova diljem zemlje. Kako odrediti redoslijed po kojem te gradove treba posjetiti tako da se ukupna prijeđena udaljenost svede na najmanju moguću mjeru?

Rješenje grube sile jednostavno je izračunati ukupnu udaljenost za svaku moguću rutu, a zatim odabrati najkraću. To nije osobito učinkovito jer je moguće pametne algoritme ukloniti mnoge moguće rute.

Vremenska složenost grube sile je O (m n ) , što se ponekad zapisuje kao O (n * m). Dakle, ako bismo tražili niz znakova "n" u nizu znakova "m" koristeći grubu silu, trebalo bi nam n * m pokušaja.

Više informacija o algoritmima

U računalnoj znanosti algoritam je jednostavno skup postupaka za rješavanje zadanog problema. Algoritmi mogu biti dizajnirani za obavljanje izračune, procesne podatke ili izvođenje automatskih rasuđivanje zadatke.

Evo kako ih Wikipedia definira:

Algoritam je učinkovita metoda koja se može izraziti u konačnoj količini prostora i vremena i na točno definiranom formalnom jeziku za izračunavanje funkcije. Polazeći od početnog stanja i početnog unosa (možda praznog), upute opisuju proračun koji se, kada se izvrši, odvija kroz konačan broj dobro definiranih uzastopnih stanja, dajući na kraju "izlaz" i završavajući u konačnom završnom stanju. Prijelaz iz jednog stanja u drugo nije nužno deterministički; neki algoritmi, poznati kao randomizirani algoritmi, uključuju slučajni unos.

Postoje određeni zahtjevi kojih se algoritam mora pridržavati:

  1. Definitivnost: Svaki je korak u procesu precizno naveden.
  2. Učinkovita izračunljivost: Svaki korak u procesu može izvršiti računalo.
  3. Konačnost: Program će na kraju uspješno završiti.

Neke uobičajene vrste algoritama uključuju:

  • algoritmi za sortiranje
  • algoritmi pretraživanja
  • algoritmi kompresije.

Klase algoritama uključuju

  • Grafikon
  • Dinamičko programiranje
  • Sortiranje
  • Traženje
  • Žice
  • Matematika
  • Računalna geometrija
  • Optimizacija
  • Razno.

Iako tehnički nisu klasa algoritama, strukture podataka često su grupirane s njima.

Učinkovitost

Algoritmi se najčešće procjenjuju prema njihovoj učinkovitosti i količini računalnih resursa potrebnih za izvršavanje zadatka.

Uobičajeni način procjene algoritma je promatranje njegove vremenske složenosti. To pokazuje kako vrijeme izvođenja algoritma raste kako raste veličina ulaza. Budući da algoritmi danas moraju raditi na velikim ulazima podataka, neophodno je da naši algoritmi imaju relativno brzo vrijeme rada.

Algoritmi sortiranja

Algoritmi sortiranja dolaze u raznim okusima, ovisno o vašoj potrebi. Neke, vrlo česte i široko korištene su:

Quicksort

Ne postoji rasprava o sortiranju koja se može završiti bez brzog sortiranja. Evo osnovnog koncepta: Brzo sortiranje

Mergesort

Algoritam sortiranja koji se oslanja na koncept kako se sortirani nizovi spajaju kako bi se dobili jedan sortirani nizovi. Više o tome pročitajte ovdje: Mergesort

Nastavni plan i program freeCodeCampa jako naglašava stvaranje algoritama. To je zato što su algoritmi učenja dobar način za vježbanje vještina programiranja. Ispitivači najčešće testiraju kandidate na algoritmima tijekom razgovora za posao programera.

Knjige o algoritmima u JavaScript-u:

Strukture podataka u JavaScript-u

  • Besplatna knjiga koja pokriva strukture podataka u JavaScript-u
  • GitBook

Učenje JavaScript struktura podataka i algoritama - drugo izdanje

  • Obuhvaća objektno orijentirano programiranje, prototipsko nasljeđivanje, algoritme sortiranja i pretraživanja, brzo sortiranje, spajanje, binarno stablo pretraživanja i napredne koncepte algoritama
  • Amazon
  • ISBN-13: 978-1785285493

Strukture podataka i algoritmi s JavaScriptom: Dovođenje klasični računanje pristupa webu

  • Pokriva algoritme rekurzije, sortiranja i pretraživanja, povezane popise i binarna stabla pretraživanja.
  • Amazon
  • ISBN-13: 978-1449364939