Brute Force algoritmusok magyarázata

A nyers erő algoritmusai pontosan olyanok, amilyennek hangzanak - a probléma megoldásának egyszerű módszerei, amelyek puszta számítási teljesítményre támaszkodnak, és a hatékonyság javításához fejlett technikák helyett minden lehetőséget kipróbálnak.

Képzelje el például, hogy van egy kis lakat 4 számjegyből, mindegyik 0–9. Elfelejtette a kombinációját, de nem szeretne újabb lakatot vásárolni. Mivel egyik számjegyre sem emlékszik, a zár kinyitásához nyers erő módszerrel kell eljárnia.

Tehát visszaállítja az összes számot 0-ra, és egyenként próbálja ki őket: 0001, 0002, 0003 és így tovább, amíg meg nem nyílik. A legrosszabb esetben 104 vagy 10 000 próbálkozásra lenne szükség a kombináció megtalálásához.

A számítástechnika klasszikus példája az utazó eladó problémája (TSP). Tegyük fel, hogy egy eladónak meg kell látogatnia az ország 10 városát. Hogyan lehet meghatározni annak sorrendjét, amelyben ezeket a városokat meg kell látogatni, hogy a teljes megtett távolság minimális legyen?

A nyers erő megoldása egyszerűen az összes lehetséges útvonal teljes távolságának kiszámítása, majd a legrövidebb kiválasztása. Ez nem különösebben hatékony, mert okos algoritmusok révén sok lehetséges útvonal kiküszöbölhető.

A nyers erő időbeli összetettsége O (m n ) , amelyet néha O (n * m) néven írnak. Tehát, ha nyers erővel "n" karakterláncot keresnénk az "m" karakterláncokba, akkor n * m próbálkozásra lenne szükségünk.

További információ az algoritmusokról

A számítástechnikában az algoritmus egyszerűen lépésről lépésre halad egy adott probléma megoldására. Az algoritmusok megtervezhetők számítások elvégzésére, adatok feldolgozására vagy automatizált érvelési feladatok végrehajtására.

Így határozza meg őket a Wikipedia:

Az algoritmus egy hatékony módszer, amely véges térben és időben és pontosan definiált formális nyelven kifejezhető egy függvény kiszámításához. A kezdeti állapotból és a kezdeti (lehet, hogy üres) bemenetből kiindulva az utasítások olyan számítást írnak le, amely végrehajtáskor véges számú, jól definiált, egymást követő állapoton megy keresztül, végül „kimenetet” állít elő és végső végállapotban fejeződik be. Az egyik állapotból a másikba való átmenet nem feltétlenül meghatározó; egyes algoritmusok, úgynevezett randomizált algoritmusok, véletlenszerű bevitelt tartalmaznak.

Bizonyos követelmények, amelyeket egy algoritmusnak be kell tartania:

  1. Határozottság: A folyamat minden lépése pontosan meg van határozva.
  2. Hatékony számíthatóság: A folyamat minden lépését számítógéppel lehet végrehajtani.
  3. Végesség: A program végül sikeresen leáll.

Néhány általános algoritmustípus a következőket tartalmazza:

  • rendezési algoritmusok
  • keresési algoritmusok
  • tömörítési algoritmusok.

Az algoritmusok osztályai tartalmazzák

  • Grafikon
  • Dinamikus programozás
  • Válogatás
  • Keresés
  • Húrok
  • Math
  • Számítási geometria
  • Optimalizálás
  • Vegyes.

Bár technikailag nem algoritmusok osztálya, az adatstruktúrákat gyakran velük csoportosítják.

Hatékonyság

Az algoritmusokat leggyakrabban hatékonyságuk és a feladatuk elvégzéséhez szükséges számítási erőforrások mennyisége alapján ítélik meg.

Az algoritmus értékelésének egyik általános módja annak időbeli összetettségének vizsgálata. Ez megmutatja, hogyan növekszik az algoritmus futási ideje a bemeneti méret növekedésével. Mivel az algoritmusoknak manapság nagy adatbeviteleken kell működniük, elengedhetetlen, hogy algoritmusainknak meglehetősen gyors futási ideje legyen.

Algoritmusok rendezése

A rendezési algoritmusok különböző ízűek, az Ön szükségességétől függően. Néhány, nagyon gyakori és széles körben használt:

Quicksort

Nincs rendezési beszélgetés, amely gyors rendezés nélkül befejeződhet. Itt van az alapkoncepció: Gyors rendezés

Mergesort

A rendezési algoritmus, amely a tömbök rendezésének koncepciójára támaszkodik, összevonva egyetlen rendezett tömböt kap. További információ itt: Mergesort

A freeCodeCamp tanterve nagy hangsúlyt fektet az algoritmusok létrehozására. Az algoritmusok tanulása ugyanis jó módszer a programozási képességek gyakorlására. Az interjúztatók leggyakrabban algoritmusokon tesztelik a jelölteket a fejlesztői állásinterjúk során.

Könyvek algoritmusokról a JavaScript-ben:

Adatszerkezetek a JavaScript-ben

  • Ingyenes könyv, amely az adatszerkezeteket tartalmazza JavaScript-ben
  • GitBook

JavaScript adatszerkezetek és algoritmusok elsajátítása - második kiadás

  • Felöleli az objektum-orientált programozást, a prototípusos öröklődést, a rendezési és keresési algoritmusokat, a quicksort, mergesort, a bináris keresési fákat és a fejlett algoritmus-fogalmakat
  • amazon
  • ISBN-13: 978-1785285493

Adatszerkezetek és algoritmusok JavaScript-sel: Klasszikus számítástechnikai megközelítések eljuttatása az internethez

  • Felöleli a rekurziós, rendezési és keresési algoritmusokat, a kapcsolt listákat és a bináris keresési fákat.
  • amazon
  • ISBN-13: 978-1449364939