programátoři život algoritmů a datových struktur je velmi důležité téma, pokud chtějí jít ven v programovém světě a vydělat nějaké prachy. Dnes uvidíme, co dělají a kde jsou používány s nejjednoduššími příklady. Tento seznam je připraven s ohledem na jejich použití v konkurenčním programování a současných vývojových postupech.

Seřadit algoritmy

třídění je nejvíce studovaný koncept v informatice. Myšlenka je uspořádat položky seznamu v určitém pořadí. Ačkoli každý hlavní programovací jazyk má vestavěné třídící knihovny, hodí se, pokud víte, jak fungují. V závislosti na požadavku budete chtít použít některý z nich.

• sloučit řazení
• Quick Sort
• Bucket Sort
• Heap Sort
• počítání řazení

ještě důležitější je vědět, kdy a kde je použít. Některé příklady, kde můžete najít přímé použití třídící techniky patří:

• Třídění podle ceny, popularity atd. v e-commerce webové stránky

Vyhledávací Algoritmy

Binární Vyhledávání (v lineární datové struktury)

Binární vyhledávání je použit k provedení velmi efektivní vyhledávání na tříděný datový soubor. Časová složitost je O (log2N). Myšlenka je opakovaně rozdělit na polovinu části seznamu, která by mohla obsahovat položku, dokud ji zúžíme na jednu možnou položku. Některé aplikace jsou:

• Při hledání na název písně v seřazený seznam skladeb, provádí binární hledání, a řetězec, odpovídající rychle vrátit výsledky.
• Používá se k ladění v systému git prostřednictvím git půlí

Hloubka/Šířka Nejprve Hledat (v Grafu datové struktury)

DFS a BFS jsou strom/graf křížení a vyhledávání datových struktur. Nechtěli bychom jít hluboko do toho, jak DFS/BFS práce, ale uvidíme, jak se liší prostřednictvím následující animace.

Aplikace:

• Používá vyhledávače pro procházení webu
• Používají v umělé inteligenci, aby se budovat roboty, například šachy bot
• Nalezení nejkratší cesty mezi dvěma městy na mapě a mnoho dalších takových aplikací

Hash

Hash vyhledávání je v současné době nejpoužívanější technikou pro nalezení vhodných dat pomocí klíče nebo ID. K datům přistupujeme podle jeho indexu. Dříve jsme se spoléhali na třídění + binární vyhledávání hledat index, zatímco nyní používáme hashing.

datová struktura je označována jako Hash-Map nebo Hash-Table nebo slovník, který mapuje klíče k hodnotám, efektivně. Vyhledávání hodnot můžeme provádět pomocí kláves. Myšlenka je použít vhodnou hašovací funkci, která dělá klíč – > mapování hodnot. Výběr dobré hašovací funkce závisí na scénáři.

aplikace:

• V routerech, ukládat IP adresu -> Cestou pár pro směrování mechanismy
• provést zkontrolujte, zda hodnota již existuje v seznamu. Lineární vyhledávání by bylo drahé. Pro tuto operaci můžeme také použít nastavenou datovou strukturu.

Dynamické Programování

Dynamické programování (DP) je metoda pro řešení složitých problém tím, rozebrat to do jednodušších dílčích problémů. Řešíme dílčí problémy, pamatujeme si jejich výsledky a pomocí nich se rychle snažíme vyřešit složitý problém.

* zapisuje „1+1+1+1+1+1+1+1 =“ na listu papíru* čemu se to rovná?
* počítání * osm!
* zapíše další „1+“ vlevo* co s tím?
* rychle * devět!
Jak jste věděl, že je devět tak rychle?
právě jste přidali ještě jeden
takže jste nemuseli přepočítávat, protože jste si pamatovali, že jich bylo osm! Dynamické Programování je jen ozdobný způsob, jak říkat ‚vzpomínat na věci, ušetřit čas později‘

Aplikace:

• Existuje mnoho DP algoritmů a aplikací, ale já bych jméno jednoho a vyhodit vás, Duckworth-Lewis metoda v kriketu.

umocnění umocněním

Řekněme, že chcete vypočítat 232. Normálně bychom iterovali 32krát a našli výsledek. Co kdybych vám řekl, že to lze provést v 5 iteracích?

umocnění pomocí umocnění nebo binární umocnění je obecná metoda pro rychlý výpočet velkých kladných celočíselných mocnin čísla v O (log2N). Nejen to, metoda se také používá pro výpočet mocnin polynomů a čtvercových matic.

aplikace:

• výpočet velkých výkonů čísla je většinou vyžadován v šifrování RSA. RSA také používá modulární aritmetiku spolu s binární umocnění.

string Matching and Parsing

Pattern matching / vyhledávání je jedním z nejdůležitějších problémů v informatice. Na toto téma bylo hodně výzkumu, ale pro každého programátora získáme pouze dvě základní potřeby.

algoritmus KMP (String Matching)

algoritmus Knuth-Morris-Pratt se používá v případech, kdy musíme porovnávat krátký Vzor v dlouhém řetězci. Například, když jsme Ctrl + F Klíčové slovo v dokumentu, provádíme odpovídající vzor v celém dokumentu.

Regulární výraz (String Parsing)

mnohokrát musíme ověřit řetězec analýzou nad předdefinovaným omezením. To je silně používán ve vývoji webových stránek pro URL parsování a párování.

algoritmy testování Primality

existují deterministické a pravděpodobnostní způsoby určení, zda je dané číslo prvočíslo nebo ne. Uvidíme jak deterministické, tak pravděpodobnostní (nedeterministické) způsoby.

síto Eratosthenes (deterministické)

Pokud máme určitý limit na rozsah čísel, řekněme určit všechny prvočísla v rozmezí 100 až 1000 pak síto je způsob, jak jít. Délka rozsahu je rozhodujícím faktorem, protože musíme přidělit určité množství paměti podle rozsahu.

Pro jakékoli číslo n, postupně testování aľ sqrt(n) (deterministický)

V případě, že chcete podívejte se na pár čísel, která jsou řídce rozloženy na dlouhé vzdálenosti (řekněme 1 až 1012), Síto nebude moci přidělit dostatek paměti. Můžete se podívat na každé číslo n pojížděním pouze aľ sqrt(n) a provedení dělitelnost podívejte se na n.

Fermat primality test a Miller–Rabin primality test (oba jsou nedeterministické)

Obě z nich jsou compositeness testy. Pokud se ukáže, že číslo je složené, pak to určitě není prvočíslo. Miller-Rabin je sofistikovanější než Fermatův. Infact, Miller-Rabin má také deterministickou variantu, ale pak je to hra obchodu mezi časovou složitostí a přesností algoritmu.

aplikace:

• nejdůležitější použití prvočísel je v kryptografii. Přesněji řečeno, používají se v šifrování a dešifrování v RSA algoritmus, který byl první implementace Kryptosystémy s Veřejným Klíčem
• Další použití, je Hash funkce používá Hash Tabulky