Žiaurios jėgos algoritmai paaiškinti

Brutalios jėgos algoritmai yra būtent tokie, kokie jie skamba - nesudėtingi problemos sprendimo metodai, kuriais remiamasi tik skaičiavimo galia ir išbandomos visos galimybės, o ne pažangios technikos efektyvumui padidinti.

Pvz., Įsivaizduokite, kad turite mažą spyną su 4 skaitmenimis, kurių kiekvienas yra nuo 0 iki 9. Pamiršote savo derinį, bet nenorite pirkti kitos spynos. Kadangi negalite prisiminti nė vieno skaitmens, spynai atidaryti turite naudoti grubios jėgos metodą.

Taigi nustatykite visus skaičius atgal į 0 ir bandykite juos po vieną: 0001, 0002, 0003 ir t. T., Kol jis atsidarys. Blogiausiu atveju prireiktų 104 arba 10 000 bandymų rasti jūsų derinį.

Klasikinis informatikos pavyzdys yra keliaujančio pardavėjo problema (TSP). Tarkime, pardavėjui reikia aplankyti 10 šalies miestų. Kaip galima nustatyti tų miestų lankymo tvarką, kad bendras atstumas būtų kuo mažesnis?

Žiaurios jėgos sprendimas yra tiesiog apskaičiuoti bendrą atstumą kiekvienam įmanomam maršrutui ir tada pasirinkti trumpiausią. Tai nėra ypač efektyvu, nes protingais algoritmais įmanoma pašalinti daugybę galimų maršrutų.

Žiaurios jėgos laiko sudėtingumas yra O (m n ) , kuris kartais rašomas kaip O (n * m). Taigi, jei mes ieškotume „n“ simbolių eilutės „m“ simbolių eilutėje, naudodami grubią jėgą, mums prireiktų n * m bandymų.

Daugiau informacijos apie algoritmus

Informatikos srityje algoritmas yra tiesiog žingsnis po žingsnio procedūrų rinkinys, skirtas išspręsti tam tikrą problemą. Algoritmai gali būti suprojektuoti atlikti skaičiavimus, apdoroti duomenis ar atlikti automatizuotas argumentavimo užduotis.

Štai kaip juos apibrėžia Vikipedija:

Algoritmas yra efektyvus metodas, kurį galima išreikšti per ribotą erdvės ir laiko kiekį bei tiksliai apibrėžta oficialia kalba, norint apskaičiuoti funkciją. Pradedant nuo pradinės būsenos ir pradinio įvedimo (galbūt tuščio), instrukcijose aprašomas skaičiavimas, kuris, įvykdytas, vyksta per baigtinį skaičių tiksliai apibrėžtų vienas po kito einančių būsenų, galiausiai sukuriant „išvestį“ ir baigiantis galutine pabaigos būsena. Perėjimas iš vienos būsenos į kitą nebūtinai yra deterministinis; kai kuriuose algoritmuose, vadinamuose atsitiktinių imčių algoritmais, yra atsitiktinis įvestis.

Yra tam tikrų reikalavimų, kurių algoritmas turi laikytis:

  1. Apibrėžtumas: kiekvienas proceso etapas yra tiksliai nurodytas.
  2. Efektyvus skaičiuojamumas: kiekvieną proceso etapą gali atlikti kompiuteris.
  3. Baigtumas: programa galiausiai sėkmingai baigsis.

Kai kurie įprasti algoritmų tipai yra šie:

  • rūšiavimo algoritmai
  • paieškos algoritmai
  • suspaudimo algoritmai.

Algoritmų klasės apima

  • Grafikas
  • Dinaminis programavimas
  • Rūšiavimas
  • Ieškoma
  • Stygos
  • Matematika
  • Skaičiavimo geometrija
  • Optimizavimas
  • Įvairūs.

Nors techniškai tai nėra algoritmų klasė, duomenų struktūros dažnai yra grupuojamos su jais.

Efektyvumas

Algoritmai dažniausiai vertinami pagal jų efektyvumą ir skaičiavimo išteklių kiekį, kurio jiems reikia užduočiai atlikti.

Dažnas būdas įvertinti algoritmą yra pažvelgti į jo laiko sudėtingumą. Tai rodo, kaip algoritmo veikimo laikas auga, kai įvesties dydis auga. Kadangi šiandien algoritmai turi veikti su dideliais duomenų įvestimis, būtina, kad mūsų algoritmai veiktų pakankamai greitai.

Algoritmų rūšiavimas

Rūšiavimo algoritmai būna įvairaus skonio, priklausomai nuo jūsų poreikio. Kai kurie, labai paplitę ir plačiai naudojami, yra šie:

„Quicksort“

Nėra rūšiavimo diskusijos, kuri būtų baigta be greito rūšiavimo. Čia yra pagrindinė koncepcija: greitas rūšiavimas

Susijungimas

Rūšiavimo algoritmas, kuris remiasi koncepcija, kaip surikiuoti masyvus, sujungiamas, kad gautų vieną rūšiuojamą masyvą. Daugiau apie tai skaitykite čia: „Mergesort“

„freeCodeCamp“ mokymo programoje labai akcentuojamas algoritmų kūrimas. Taip yra todėl, kad algoritmų mokymasis yra geras būdas praktikuoti programavimo įgūdžius. Interviu dalyviai dažniausiai išbando algoritmus per kūrėjo darbo pokalbius.

Knygos apie algoritmus „JavaScript“:

Duomenų struktūros „JavaScript“

  • Nemokama knyga, apimanti „JavaScript“ duomenų struktūras
  • „GitBook“

„JavaScript“ duomenų struktūrų ir algoritmų mokymasis - antrasis leidimas

  • Apima į objektą orientuotą programavimą, prototipinį paveldėjimą, rūšiavimo ir paieškos algoritmus, „quicksort“, „mergesort“, dvejetainius paieškos medžius ir išplėstines algoritmo koncepcijas.
  • „Amazon“
  • ISBN-13: 978-1785285493

Duomenų struktūros ir algoritmai su „JavaScript“: klasikinių skaičiavimo būdų pateikimas žiniatinkliui

  • Apima rekurso, rūšiavimo ir paieškos algoritmus, susietus sąrašus ir dvejetainius paieškos medžius.
  • „Amazon“
  • ISBN-13: 978-1449364939