A programozók életét algoritmusok, valamint az adatok struktúrák legfontosabb téma, ha azt akarják, hogy menjen ki a programozási világ, hogy néhány dollárt. Ma látni fogjuk, hogy mit csinálnak, és hol használják őket a legegyszerűbb példákkal. Ez a lista a versenyképes programozásban és a jelenlegi fejlesztési gyakorlatokban való felhasználásukat szem előtt tartva készül.

rendezési algoritmusok

a rendezés a számítástechnika leginkább vizsgált koncepciója. Az ötlet az, hogy a lista elemeit egy adott sorrendben rendezzük el. Bár minden nagyobb programozási nyelv beépített rendezési könyvtárak, jól jön, ha tudod, hogyan működnek. Attól függően, hogy követelmény érdemes használni ezeket.

• Merge Rendezés
• gyors rendezés
• vödör Rendezés
• Heap Rendezés
• számolás Rendezés

fontosabb tudni kell, hogy mikor és hol kell használni őket. Néhány példa, ahol megtalálhatja a rendezési technikák közvetlen alkalmazását:

• Rendezés ár, népszerűség stb az e-kereskedelmi webhelyeken

keresési algoritmusok

bináris keresés (lineáris adatstruktúrákban)

A bináris keresés nagyon hatékony keresést végez a rendezett adatkészleten. Az idő összetettsége O (log2N). Az ötlet az, hogy ismételten felosztjuk a lista azon részének felét, amely tartalmazhatja az elemet, amíg egy lehetséges elemre nem szűkítjük. Néhány alkalmazás a következő:

• amikor egy dal nevét keresi a dalok rendezett listájában, bináris keresést hajt végre, majd karakterlánc-illesztést végez az eredmények gyors visszaküldéséhez.
• Használt debug a git keresztül git felezik

Mélység/Szélesség az Első Keresés (a Grafikon adatszerkezetek)

DFS pedig BFS vagy fa/grafikon áthaladó, keresés, adatszerkezetek. Mi nem megy mélyen, hogyan DFS / BFS munka, de látni fogja, hogyan különböznek a következő animáció.

az Alkalmazás:

• által Használt keresőmotorok a web-tele
• Használt mesterséges intelligencia építeni botok, például egy sakk-bot
• Megtalálni a legrövidebb utat, a két város között egy térkép, valamint sok más ilyen alkalmazás

Hasító

Hash keresési jelenleg a legszélesebb körben használt technikát, hogy megtalálja a megfelelő adatok gombot, vagy ID. Az adatokat az index alapján érjük el. Korábban támaszkodtunk Válogatás + bináris keresés keresni index mivel most használjuk hashing.

az adatstruktúrát Hash-Map vagy Hash-táblának vagy szótárnak nevezik, amely hatékonyan leképezi az értékek kulcsait. Az értékkeresést kulcsokkal tudjuk végrehajtani. Idea, hogy egy megfelelő hash funkció, amely nem a kulcs – > érték leképezés. A jó hash funkció kiválasztása a forgatókönyvtől függ.

Alkalmazások:

• útválasztókban az IP-cím tárolásához – > Útvonalpár a
• útvonalválasztási mechanizmusokhoz annak ellenőrzéséhez, hogy létezik-e már érték a listában. A lineáris keresés drága lenne. Ehhez a művelethez a beállított adatstruktúrát is felhasználhatjuk.

Dynamic Programming

Dynamic programming (DP) egy módszer egy összetett probléma megoldására azáltal, hogy egyszerűbb alproblémákra bontja. Megoldjuk az alproblémákat, emlékezünk az eredményeikre, és ezek felhasználásával gyorsan megoldjuk a komplex problémát.

* írja le “1+1+1+1+1+1+1+1 =” egy papírlapon * mi ez egyenlő?
* számolás * nyolc!
* ír le egy másik” 1+ ” a bal oldalon* mi van ezzel?
*gyorsan * kilenc!
Honnan tudtad, hogy kilenc ilyen gyors?
csak még egy
– t adott hozzá, így nem kellett újraszámlálnia, mert eszébe jutott, hogy nyolc volt! Dinamikus programozás csak egy divatos módja annak, hogy azt mondják, “emlékezés dolgokat, hogy időt takaríthat meg később”

Alkalmazások:

• Sok DP algoritmusok és alkalmazások, de én nevezzek egyet, és fúj el, Duckworth-Lewis módszer krikett.

exponenciáció a

négyzetével azt mondja, hogy 232-et szeretne kiszámítani. Általában 32-szer ismételjük meg az eredményt. Mi van, ha azt mondom, hogy meg lehet csinálni 5 ismétlések?

a négyzetes vagy bináris exponenciációval történő Exponencia egy általános módszer az O-ban(log2N) lévő nagy pozitív egész számok gyors kiszámítására. Nem csak ezt, a módszert is használják számítási hatáskörét polinomok, négyzet mátrixok.

alkalmazás:

• egy szám nagyhatalmának kiszámítása többnyire az RSA titkosításban szükséges. Az RSA moduláris aritmetikát is alkalmaz a bináris exponenciával együtt.

String Matching and Parsing

Pattern matching / search is one of the most important problem in Computer Science. Sok kutatás történt a témában, de csak két alapvető szükségletet fogunk igénybe venni minden programozó számára.

KMP algoritmus (String Matching)

Knuth-Morris-Pratt algoritmust használnak olyan esetekben, amikor egy rövid mintának kell megfelelnünk egy hosszú karakterláncban. Például, amikor egy dokumentumban Ctrl+f egy kulcsszót használunk, akkor a teljes dokumentumban minta-illesztést végzünk.

reguláris kifejezés (String Parsing)

sokszor ellenőriznünk kell egy karakterláncot egy előre definiált korlátozás elemzésével. Ez erősen használják a webes fejlesztés URL elemzés és megfelelő.

Primality Testing Algorithms

determinisztikus és valószínűségi módszerek vannak annak meghatározására, hogy egy adott szám prím-e vagy sem. Mind determinisztikus, mind valószínűségi (nem determinisztikus) módszereket fogunk látni.

Eratosthenes Szita (determinisztikus)

ha van bizonyos határ a számtartományban, mondjuk határozza meg az összes prímet a 100-1000 tartományon belül, akkor a szita egy út. A tartomány hossza döntő tényező, mivel bizonyos mennyiségű memóriát kell elosztanunk a tartomány szerint.

bármely n számhoz, fokozatosan tesztelve akár sqrt (n) (determinisztikus)

abban az esetben, ha néhány olyan számot szeretne ellenőrizni, amelyek ritkán vannak elosztva egy hosszú tartományban (mondjuk 1-1012), a szita nem képes elegendő memóriát kiosztani. Ellenőrizze az egyes szám n áthaladó csak max sqrt(n), majd hajtsa végre a oszthatóság ellenőrizze a n.

Fermat primality teszt, Miller–Rabin primality teszt (mindkettő nondeterministic)

Mindkettő compositeness vizsgálatok. Ha egy szám kompozitnak bizonyul, akkor az biztos, hogy nem prímszám. Miller-Rabin egy kifinomultabb, mint Fermat. valójában, Miller-Rabin is van egy determinisztikus változata, de akkor a játék a kereskedelem idő összetettsége és pontossága az algoritmus.

alkalmazás:

• a prímszámok egyetlen legfontosabb használata a kriptográfia. Pontosabban, ők használják a titkosítás, dekódolás RSA algoritmus, amely a legelső végrehajtása nyilvános kulcs Cryptosystems
• egy másik felhasználás a Hash függvények használt Hash táblák