w programistach algorytmy życia i struktury danych są najważniejszym tematem, jeśli chcą wyjść z programowania świat i zarobić trochę kasy. Dziś zobaczymy, co robią i gdzie są używane na najprostszych przykładach. Lista ta jest przygotowana z myślą o ich wykorzystaniu w konkurencyjnym programowaniu i aktualnych praktykach programistycznych.

algorytmy sortowania

sortowanie jest najszerzej badaną koncepcją w informatyce. Ideą jest ułożenie elementów listy w określonej kolejności. Chociaż każdy większy język programowania ma wbudowane biblioteki sortowania, przydaje się, jeśli wiesz, jak działają. W zależności od wymagań możesz użyć dowolnego z nich.

• Scalanie Sortuj
• szybkie sortowanie
• sortowanie kubełkowe
• sortowanie sterty
• liczenie Sortuj

co ważniejsze, należy wiedzieć, kiedy i gdzie ich użyć. Przykłady, w których można znaleźć bezpośrednie zastosowanie technik sortowania to:

• sortowanie według ceny, popularności itp.w serwisach e-commerce

Algorytmy wyszukiwania

Wyszukiwanie binarne (w liniowych strukturach danych)

Wyszukiwanie binarne służy do bardzo efektywnego wyszukiwania posortowanych zbiorów danych. Złożoność czasowa wynosi O (log2N). Chodzi o to, aby wielokrotnie dzielić na pół część listy, która może zawierać element, dopóki nie zawęzimy jej do jednego możliwego elementu. Niektóre aplikacje to:

• podczas wyszukiwania nazwy utworu na posortowanej liście utworów, wykonuje wyszukiwanie binarne i dopasowywanie ciągów znaków, aby szybko zwrócić wyniki.
• używane do debugowania w git poprzez Git bisect

Depth/Width First Search (w graph data structures)

DFS i BFS są tree / graph traversing i przeszukiwanie struktur danych. Nie zagłębimy się w to, jak działają DFS/BFS, ale zobaczymy, jak się różnią dzięki poniższej animacji.

Aplikacje:

• używane przez wyszukiwarki do indeksowania stron internetowych
• używane w sztucznej inteligencji do budowy botów, na przykład bota szachowego
• znajdującego najkrótszą ścieżkę między dwoma miastami na mapie i wiele innych tego typu aplikacji

Hashing

hash Lookup jest obecnie najczęściej stosowaną techniką wyszukiwania odpowiednich danych według klucza lub identyfikatora. Uzyskujemy dostęp do danych poprzez ich indeks. Wcześniej polegaliśmy na sortowaniu + wyszukiwaniu binarnym, aby szukać indeksu, a teraz używamy hashowania.

struktura danych jest określana jako Hash-Map lub Hash-Table lub słownik, który skutecznie mapuje Klucze do wartości. Możemy wykonywać wyszukiwanie wartości za pomocą kluczy. Ideą jest użycie odpowiedniej funkcji skrótu, która wykonuje mapowanie wartości klucza ->. Wybór dobrej funkcji skrótu zależy od scenariusza.

Aplikacje:

• w routerach, aby zapisać adres IP- > para ścieżek dla mechanizmów routingu
• , aby wykonać sprawdzenie, czy wartość już istnieje na liście. Wyszukiwanie liniowe byłoby kosztowne. Do tej operacji możemy również użyć ustawionej struktury danych.

Programowanie dynamiczne

Programowanie dynamiczne (DP) jest metodą rozwiązywania złożonego problemu poprzez rozbicie go na prostsze podproblemy. Rozwiązujemy podproblemy, pamiętamy ich wyniki i wykorzystując je, szybko rozwiązujemy złożony problem.

*zapisuje „1+1+1+1+1+1+1+1 =” na kartce papieru * ile to się równa?
* liczymy * osiem!
* zapisuje kolejne „1+” po lewej* co z tym?
* szybko * 9!
skąd wiedziałeś, że tak szybko jest 9?
właśnie dodałeś jeszcze jeden
więc nie musiałeś wyliczać, bo pamiętałeś, że jest ich osiem! Programowanie dynamiczne jest po prostu fantazyjnym sposobem na powiedzenie „zapamiętywanie rzeczy, aby zaoszczędzić czas później”

Aplikacje:

• istnieje wiele algorytmów i aplikacji DP, ale nazwałbym jeden i rozwaliłbym Cię, metoda Duckwortha-Lewisa w krykiecie.

wykładnik przez kwadrat

powiedzmy, że chcesz obliczyć 232. Normalnie powtórzylibyśmy to 32 razy i znaleźliśmy wynik. Co jeśli powiem ci, że można to zrobić w 5 iteracjach?

wykładnik przez wykładnik kwadratowy lub binarny jest ogólną metodą szybkiego obliczania dużych dodatnich mocy całkowitych liczby w o(log2N). Nie tylko to, metoda ta jest również stosowana do obliczania potęg wielomianów i macierzy kwadratowych.

zastosowanie:

• Obliczanie dużych potęg liczby jest najczęściej wymagane w szyfrowaniu RSA. RSA używa również arytmetyki modularnej wraz z wykładnikiem binarnym.

Dopasowanie i parsowanie łańcuchów

dopasowanie / wyszukiwanie wzorców jest jednym z najważniejszych problemów w informatyce. Było wiele badań na ten temat, ale będziemy pobierać tylko dwie podstawowe potrzeby dla każdego programisty.

algorytm KMP (String Matching)

algorytm Knutha-Morrisa-Pratta jest używany w przypadkach, gdy musimy dopasować krótki wzór do długiego ciągu. Na przykład, gdy Ctrl + F słowo kluczowe w dokumencie, wykonujemy dopasowanie wzorca w całym dokumencie.

Wyrażenie regularne (parsowanie łańcuchów)

wiele razy musimy zweryfikować łańcuch przez parsowanie nad predefiniowanym ograniczeniem. Jest szeroko stosowany w tworzeniu stron internetowych do parsowania i dopasowywania adresów URL.

algorytmy testowania pierwotności

istnieją deterministyczne i probabilistyczne sposoby określania, czy dana liczba jest pierwsza, czy nie. Zobaczymy zarówno deterministyczne, jak i probabilistyczne (niedeterministyczne) sposoby.

Sito Eratostenesa (deterministyczne)

Jeśli mamy pewną granicę zakresu liczb, powiedzmy, że wyznaczamy wszystkie liczby pierwsze w zakresie od 100 do 1000, to sito jest drogą. Długość zakresu jest kluczowym czynnikiem, ponieważ musimy przydzielać określoną ilość pamięci zgodnie z zakresem.

dla dowolnej liczby n, stopniowo testując do sqrt(n) (deterministyczne)

w przypadku, gdy chcesz sprawdzić kilka liczb, które są słabo rozłożone w długim zakresie (powiedzmy 1 do 1012), Sieve nie będzie w stanie przydzielić wystarczającej ilości pamięci. Możesz sprawdzić dla każdej liczby n przechodząc tylko do sqrt (n) i wykonać kontrolę podzielności na n.

test pierwotności Fermata i test pierwotności Millera–Rabina (oba są nieterministyczne)

oba są testami składowości. Jeśli udowodniono, że liczba jest złożona, to na pewno nie jest liczbą pierwszą. Miller-Rabin jest bardziej wyrafinowany niż Fermata. w rzeczywistości Miller-Rabin ma również wariant deterministyczny, ale wtedy jest to gra handlowa między złożonością czasu a dokładnością algorytmu.

zastosowanie:

• najważniejszym zastosowaniem liczb pierwszych jest Kryptografia. Dokładniej, są one wykorzystywane w szyfrowaniu i deszyfrowaniu w algorytmie RSA, który był pierwszą implementacją Kryptosystemów klucza publicznego
• innym zastosowaniem są funkcje skrótu używane w tabelach skrótów