Vysvetlenie algoritmov brutálnej sily

Algoritmy Brute Force sú presne také, aké znejú - priame metódy riešenia problému, ktoré sa spoliehajú na samotný výpočtový výkon a na zlepšenie efektívnosti vyskúšajú skôr všetky možnosti než pokročilé techniky.

Predstavte si napríklad, že máte malý visací zámok so 4 číslicami, každá s číslicami 0-9. Zabudli ste kombináciu, ale nechcete si kúpiť ďalší zámok. Pretože si nemôžete spomenúť na žiadne z číslic, musíte na otvorenie zámku použiť metódu hrubej sily.

Takže nastavíte všetky čísla späť na 0 a postupne ich vyskúšate: 0001, 0002, 0003 atď., Kým sa neotvorí. V najhoršom prípade by hľadanie vašej kombinácie trvalo 104 alebo 10 000 pokusov.

Klasickým príkladom v oblasti informatiky je problém obchodného cestujúceho (TSP). Predpokladajme, že predajca musí navštíviť 10 miest po celej krajine. Ako sa dá určiť poradie, v ktorom by sa mali tieto mestá navštíviť, aby sa minimalizovala celková prejdená vzdialenosť?

Riešením hrubej sily je jednoducho vypočítať celkovú vzdialenosť pre každú možnú trasu a potom zvoliť tú najkratšiu. To nie je nijako zvlášť efektívne, pretože pomocou šikovných algoritmov je možné eliminovať mnoho možných trás.

Časová zložitosť hrubej sily je O (m n ) , ktorá sa niekedy píše ako O (n * m). Ak by sme teda hľadali reťazec znakov „n“ v reťazci znakov „m“ pomocou hrubej sily, trvalo by to n * m pokusov.

Viac informácií o algoritmoch

V počítačovej vede je algoritmus jednoducho súborom postupných postupov na vyriešenie daného problému. Algoritmy môžu byť navrhnuté na vykonávanie výpočtov, spracovania údajov alebo na vykonávanie úloh automatizovaného uvažovania.

Wikipedia ich definuje takto:

Algoritmus je efektívna metóda, ktorú je možné vyjadriť v konečnom množstve času a času a v dobre definovanom formálnom jazyku na výpočet funkcie. Počnúc počiatočným stavom a počiatočným vstupom (možno prázdnym) pokyny popisujú výpočet, ktorý keď sa vykoná, postupuje cez konečný počet dobre definovaných po sebe nasledujúcich stavov, nakoniec produkuje „výstup“ a končí sa konečným konečným stavom. Prechod z jedného štátu do druhého nemusí byť nevyhnutne deterministický; niektoré algoritmy známe ako randomizované algoritmy obsahujú náhodný vstup.

Existujú určité požiadavky, ktoré musí algoritmus dodržiavať:

  1. Definitívnosť: Každý krok procesu je presne uvedený.
  2. Efektívna vypočítateľnosť: Každý krok procesu môže vykonať počítač.
  3. Finiteness: Program sa nakoniec úspešne ukončí.

Niektoré bežné typy algoritmov zahŕňajú:

  • triediace algoritmy
  • vyhľadávacie algoritmy
  • kompresné algoritmy.

Triedy algoritmov zahŕňajú

  • Graf
  • Dynamické programovanie
  • Triedenie
  • Hľadám
  • Struny
  • Matematika
  • Výpočtová geometria
  • Optimalizácia
  • Zmiešaný.

Aj keď to technicky nie je trieda algoritmov, dátové štruktúry sú s nimi často zoskupené.

Účinnosť

Algoritmy sa najčastejšie posudzujú podľa ich efektívnosti a množstva výpočtových zdrojov, ktoré potrebujú na splnenie svojej úlohy.

Bežným spôsobom vyhodnotenia algoritmu je pohľad na jeho časovú zložitosť. To ukazuje, ako čas chodu algoritmu rastie s rastúcou veľkosťou vstupu. Pretože dnešné algoritmy musia pracovať s veľkými dátovými vstupmi, je nevyhnutné, aby mali naše algoritmy primerane rýchly čas behu.

Algoritmy triedenia

Algoritmy triedenia majú rôzne príchute podľa vašej potreby. Niektoré, veľmi bežné a široko používané sú:

Quicksort

Neexistuje žiadna diskusia o triedení, ktorá by sa mohla skončiť bez rýchleho triedenia. Tu je základný koncept: Rýchle triedenie

Mergesort

Triediaci algoritmus, ktorý sa spolieha na koncepciu triedenia polí, sa spojí, aby sa získalo jedno zoradené pole. Prečítajte si o tom viac tu: Mergesort

Osnovy freeCodeCamp veľmi zdôrazňujú tvorbu algoritmov. Je to preto, lebo učenie algoritmov je dobrý spôsob, ako si precvičiť programovacie zručnosti. Anketári najčastejšie testujú kandidátov na algoritmoch počas prijímacích pohovorov pre vývojárov.

Knihy o algoritmoch v jazyku JavaScript:

Dátové štruktúry v JavaScripte

  • Bezplatná kniha, ktorá obsahuje dátové štruktúry v JavaScripte
  • GitBook

Učenie sa dátových štruktúr a algoritmov jazyka JavaScript - druhé vydanie

  • Zahŕňa objektovo orientované programovanie, prototypové dedenie, algoritmy triedenia a vyhľadávania, quicksort, mergesort, binárne vyhľadávacie stromy a koncepty pokročilých algoritmov
  • Amazon
  • ISBN-13: 978-1785285493

Dátové štruktúry a algoritmy s jazykom JavaScript: Prinášame na web klasické výpočtové prístupy

  • Zahŕňa rekurziu, algoritmy triedenia a vyhľadávania, prepojené zoznamy a binárne vyhľadávacie stromy.
  • Amazon
  • ISBN-13: 978-1449364939