Top Algorithms and Data Structures You Really Need To Know

Jeśli chcesz zostać inżynierem oprogramowania, ale nie wiesz, od czego zacząć, oszczędźmy ci napięcia: to algorytmy i struktury danych.

Gdy poznasz sedno tych filarów programowania, zaczniesz je widzieć wszędzie. A im więcej algorytmów i struktur danych poznasz, tym bardziej będą one służyć jako paliwo napędowe w twojej karierze inżyniera oprogramowania.

Abyś mógł zacząć, zanurzmy się najpierw głęboko w Wyszukiwaniu i Sortowaniu, dwóch klasach algorytmów, bez których nie możesz żyć. Następnie dokonamy szybkiego przeglądu reszty krajobrazu, który obejmuje drzewa, grafy, programowanie dynamiczne i wiele innych.

Prawie mówiąc, istnieją dwie kategorie algorytmów wyszukiwania, które musisz poznać od razu: liniowe i binarne. Depth First Search (DFS) i Breadth First Search (BFS) są również superważne, ale zachowamy je dla sekcji dotyczącej przeszukiwania grafów poniżej.

Liniowe algorytmy wyszukiwania

Algorytmy liniowe i binarne zostały nazwane tak, aby opisać jak długo (złożoność czasowa) zajmie wyszukiwanie w oparciu o rozmiar danych wejściowych, które są przeszukiwane.

Na przykład, z liniowymi algorytmami wyszukiwania, jeśli masz 100 elementów do przeszukania, to najgorszy scenariusz wymagałby, abyś spojrzał na każdy element na wejściu, zanim natkniesz się na pożądaną wartość. Nazywa się to liniowym, ponieważ czas wyszukiwania jest dokładnie skorelowany z ilością elementów w wyszukiwaniu (100 elementów / wejście = 100 kontroli / złożoność)

W skrócie, liniowy = prosty (nie ma nic mądrego w algorytmie). Na przykład: wyobraź sobie, że próbujesz znaleźć swojego przyjaciela Lina wśród linii ludzi stojących w nieokreślonej kolejności. Wiesz już jak wygląda Lin, więc po prostu musisz spojrzeć na każdą osobę, jedną po drugiej, w kolejności, aż rozpoznasz lub nie rozpoznasz Lina. To wszystko. W ten sposób postępujesz zgodnie z algorytmem wyszukiwania liniowego

Wyszukiwanie binarne

Wyszukiwanie binarne ma swoją nazwę, ponieważ słowo binarne oznacza „z lub odnoszące się do dwóch rzeczy”, a algorytm działa poprzez dzielenie danych wejściowych na dwie części, dopóki nie znajdzie szukanego elementu. Jedna połowa zawiera szukany element, a druga nie. Proces ten jest kontynuowany do momentu, gdy miejsce, w którym dane wejściowe zostały podzielone, stanie się szukanym elementem. Wyszukiwanie binarne jest w zasadzie tylko wysoce zdyscyplinowanym podejściem do procesu eliminacji. Jest szybsze niż wyszukiwanie liniowe, ale działa tylko z uporządkowanymi sekwencjami.

Przykład powinien to wyjaśnić. Załóżmy, że próbujesz znaleźć swojego przyjaciela Bina (który ma 5’5”) w pojedynczej linii ludzi, którzy zostali uporządkowani według wzrostu od lewej do prawej, od najkrótszego do najwyższego. Jest to naprawdę długa kolejka, a Ty nie masz czasu, aby przejść przez nią jeden po drugim, porównując wzrost każdego z nich z Bin. Co możesz zrobić?

Wybierz wyszukiwanie binarne. Wybierasz osobę w samym środku kolejki i mierzysz jej wzrost. Ma 5’7”. Więc od razu wiesz, że ta osoba, wraz z wszystkimi po jej prawej stronie, nie jest Bin. Teraz, gdy zmniejszyłeś swój problem o połowę, zwróciłeś uwagę na resztę linii i wybrałeś środkową osobę ponownie. Ma ona 5’4”. Możesz więc wykluczyć tę osobę i każdego po jej lewej stronie, ponownie przecinając problem na pół. I tak dalej. Po pięciu lub sześciu takich podziałach, szybko znajdujesz Bina w ułamku czasu, który zajęło ci znalezienie Lina. W ten sposób zastosowałeś algorytm wyszukiwania binarnego.

Sortowanie

Porządkowanie, inaczej zwane sortowaniem, list elementów jest jednym z najczęstszych zadań programistycznych, jakie będziesz wykonywał jako programista. Tutaj przyjrzymy się dwóm najbardziej użytecznym algorytmom sortowania: MergeSort i QuickSort.

MergeSort

Załóżmy, że zamiast natknąć się na uporządkowaną linię ludzi w powyższym przykładzie, potrzebujesz stworzyć uporządkowaną linię ludzi z nieuporządkowanej grupy. Nie masz zbyt wiele czasu, więc wymyślasz strategię, aby przyspieszyć rzeczy.

Początkowo masz grupę ludzi, którzy są wszyscy skuleni razem, dzielą się na dwie. Następnie każda z tych dwóch grup dzieli się na dwie kolejne, i tak dalej, aż do momentu, gdy masz do czynienia wyłącznie z jednostkami. Wtedy zaczynasz łączyć te osoby w pary i każesz wyższemu z nich stanąć po prawej stronie drugiego. Całkiem szybko każdy jest zorganizowany w te lewe-prawe uporządkowane pary.

Następnie zaczynasz łączyć uporządkowane pary w uporządkowane grupy po cztery; następnie łącząc uporządkowane grupy po cztery w uporządkowane grupy po osiem; i tak dalej. W końcu okazuje się, że masz kompletną, uporządkowaną według wysokości linię ludzi, tak jak ta, którą napotkałeś powyżej. Nie wiedząc o tym, zastosowałeś algorytm MergeSort, aby osiągnąć swój wyczyn.

QuickSort

QuickSort jest trochę zbyt skomplikowany, aby łatwo go zobrazować z ludźmi, więc zbliżmy się trochę do kodu. Na początek, wyobraźmy sobie, że masz nieuporządkowaną listę lub tablicę ośmiu liczb, które chcesz uporządkować.

4 2 13 6 15 12 7 9

Mógłbyś użyć MergeSort, ale słyszałeś, że QuickSort jest generalnie szybszy, więc decydujesz się go wypróbować. Twoim pierwszym krokiem jest wybranie numeru na liście zwanego pivot. Wybór właściwego numeru pivota zrobi różnicę w szybkości działania QuickSort, a istnieją gotowe formuły do naśladowania przy wyborze dobrych pivotów. Na razie jednak, zachowajmy prostotę i wybierzmy ostatnią liczbę w tablicy jako numer pivota: 9.

4 2 13 6 15 12 7 9

Aby ułatwić śledzenie następnego kroku, utworzymy separator na początku tablicy i przedstawimy go za pomocą znaku funta.

# 4 2 13 6 15 12 7 9

Przechodząc od lewej do prawej przez naszą tablicę, naszym celem jest umieszczenie każdej liczby mniejszej niż pivot (9) na lewo od separatora i każdej liczby większej niż (lub równej) pivot na prawo od separatora. Zaczynamy od pierwszej liczby w naszej tablicy: 4. Aby przesunąć ją na lewo od separatora, po prostu przesuwamy separator o jeden element w górę:

4 # 2 13 6 15 12 7 9

To samo robimy z kolejną liczbą: 2.

4 2 # 13 6 15 12 7 9

Ale potem dochodzimy do 13, która jest większa od liczby pivot 9 i już znajduje się po prawej stronie separatora. Więc zostawiamy go w spokoju. Następnie dochodzimy do 6, która musi przejść na lewo od separatora. Więc najpierw zamieniamy ją z 13, aby znalazła się na swoim miejscu:

4 2 # 6 13 15 12 7 9

Następnie przesuwamy separator obok niej:

4 2 6 # 13 15 12 7 9

Następnie mamy 15, która jest już po prawej stronie separatora, więc zostawiamy ją w spokoju. Następnie mamy 12. To samo. Ale 7, nasz ostatni numer przed osiągnięciem pivota, potrzebuje tego samego rodzaju pomocy w poruszaniu się, co 6. Więc zamieniamy 7 z 13, aby ustawić go na pozycji:

4 2 6 # 7 15 12 13 9

Potem, po raz kolejny, przesuwamy separator obok niego:

4 2 6 7 # 15 12 13 9

W końcu dochodzimy do naszego numeru pivot: 9. Podążając tą samą logiką, co powyżej, zamieniamy 15 z 9, aby uzyskać liczbę przestawną tam, gdzie powinna być:

4 2 6 7 # 9 12 13 15

Ponieważ wszystkie liczby na lewo od 9 są teraz mniejsze niż 9, a wszystkie liczby na prawo od 9 są większe niż 9, zakończyliśmy nasz pierwszy cykl QuickSort. Następnie, potraktujemy każdy zestaw czterech liczb po obu stronach separatora jako nową tablicę, do której zastosujemy QuickSort. Oszczędzimy Ci szczegółów, ale następna runda da nam cztery pary liczb, do których z łatwością zastosujemy ostatnią rundę QuickSort. Końcowym rezultatem będzie następująca uporządkowana lista, której wygenerowanie zajęło nam mniej czasu niż przy użyciu prostszego MergeSort:

2 4 6 7 9 12 13 15

Sorting algorithms cheat sheet

To są najbardziej powszechne algorytmy sortowania z zaleceniami, kiedy ich używać. Zapamiętaj je! Są one używane wszędzie!

Heap sort: Kiedy nie potrzebujesz stabilnego sortowania i bardziej zależy ci na wydajności najgorszego przypadku niż na wydajności średniego przypadku. Gwarantowane jest O(N log N) i używa O(1) przestrzeni pomocniczej, co oznacza, że nie zabraknie ci miejsca na stercie lub stosie na bardzo dużych danych wejściowych.

Introsort: Jest to szybkie sortowanie, które przełącza się na sortowanie sterty po pewnej głębokości rekurencji, aby obejść najgorszy przypadek O(N²) szybkiego sortowania. Jest to prawie zawsze lepsze niż zwykłe stare szybkie sortowanie, ponieważ otrzymujesz średni przypadek szybkiego sortowania, z gwarantowaną wydajnością O(N log N). Prawdopodobnie jedynym powodem, aby użyć sortowania sterty zamiast tego, jest w systemach o bardzo ograniczonej pamięci, gdzie O(log N) przestrzeń stosu jest praktycznie znacząca.

Insertion sort: Kiedy N jest gwarantowane, że jest małe, w tym jako przypadek bazowy szybkiego sortowania lub sortowania scalającego. Podczas gdy jest to O(N²), ma bardzo małą stałą i jest stabilnym sortem.

Sort bąbelkowy, sort selekcyjny: Kiedy robisz coś szybkiego i brudnego i z jakiegoś powodu nie możesz po prostu użyć algorytmu sortowania biblioteki standardowej. Jedyną ich przewagą nad insertion sort jest to, że są nieco łatwiejsze w implementacji.

Quick sort: Kiedy nie potrzebujesz stabilnego sortowania, a wydajność średniego przypadku ma znaczenie bardziej niż wydajność najgorszego przypadku. Szybkie sortowanie jest O(N log N) średnio, O(N²) w najgorszym przypadku. Dobra implementacja używa O(log N) pomocniczej pamięci w postaci przestrzeni stosu dla rekurencji.

Merge sort: Kiedy potrzebujesz stabilnego, O(N log N) sortowania, jest to mniej więcej jedyna opcja. Jedynym minusem jest to, że używa O(N) przestrzeni pomocniczej i ma nieco większą stałą niż szybkie sortowanie. Istnieje kilka sortów scalających in-place, ale AFAIK wszystkie one są albo niestabilne, albo gorsze niż O(N log N). Nawet O(N log N) in place sorts mają tak dużo większą stałą niż zwykły stary merge sort, że są bardziej teoretycznymi ciekawostkami niż użytecznymi algorytmami.