Szukałem dobrego kursu online w strukturach danych, ale odkryłem, że Google zwraca również wyniki kursów z algorytmów, które mówią:

Na tym kursie poznasz kilka podstawowych zasad projektowania algorytmów: metody dziel i zwyciężaj, algorytmy graficzne, praktyczne struktury danych (sterty, tabele skrótów, drzewa wyszukiwania) , algorytmy losowe i inne. [źródło]

i

Pod koniec tej klasy zrozumiesz kluczowe pojęcia potrzebne do opracowania nowych algorytmów dla wykresów i innych ważnych struktur danych oraz do oceny wydajności tych algorytmów. [źródło]

i

Kurs stanowi wprowadzenie do modelowania matematycznego problemów obliczeniowych. Obejmuje typowe algorytmy, paradygmaty algorytmiczne i struktury danych stosowane do rozwiązywania tych problemów . [źródło]

Moje pytanie brzmi: czy algorytmy i struktury danych są ze sobą ściśle powiązane, co oznacza, że ​​należy je rozumieć razem, czy też jeden temat jest bardziej fundamentalny niż drugi?

EDYCJA: Aby głosujący mogli zamknąć to pytanie, czy możesz mi powiedzieć, dlaczego i jak je poprawić? Nauka zadawania właściwych pytań jest częścią procesu edukacyjnego.

Istnieją różne rodzaje mieszanin. Masz struktury danych, które nie są powiązane z algorytmami, algorytmy, które nie wymagają (rzeczywistych) struktur danych, ale najczęściej oba są w jednym pakiecie.

Edycja: jak słusznie wskazano @Doval, struktury danych same w sobie nie są powiązane z żadnymi operacjami. Akt łączenia struktury danych i algorytmu tworzy abstrakcyjny typ danych.

Struktury danych bez algorytmów

Rozważmy na przykład strukturę danych do przechowywania współrzędnych dwuwymiarowych, odpowiednio nazwaną Point. Algorytmy nie mają wiele do zrobienia dla punktu, a tak naprawdę to tylko kontener dla wartości xi y. Oczywiście, nadając tę ​​strukturę danych, możesz teraz dodawać do niej wszelkiego rodzaju algorytmy (obliczanie odległości, wypukłe kadłuby, co masz).

Możesz pomyśleć o wielu strukturach danych, które są po prostu nagromadzeniem pojedynczych danych. Chociaż występują one często w praktyce, nie stanowią dobrego materiału dydaktycznego, ponieważ nie można się z nich niczego nauczyć, po zrozumieniu, że pojedyncze elementy danych można akumulować w nową strukturę danych (np. Czego się uczysz po powyższym Pointprzykładzie, jeśli dostarczę ci tę niesamowitą strukturę danych Point3D, która może zrobić to samo w przypadku przestrzeni trójwymiarowej?)

Algorytmy bez (rzeczywistych) struktur danych

„Rzeczywisty”, ponieważ oczywiście każdy interesujący algorytm potrzebuje prymitywnych typów danych, takich jak liczby całkowite lub logiczne, i nie chcemy uwzględniać ich jako struktur danych w tym kontekście. Podobnie jak powyżej, algorytmy te są zazwyczaj dość proste. W szczególności nie mają one żadnego skomplikowanego stanu, ponieważ zwykle wchodzi w strukturę danych (patrz następny rozdział).

Przykładem takiego algorytmu może być obliczenie największego wspólnego dzielnika dwóch liczb. Algorytmy Euklid dla gcd naprawdę potrzebują tylko dwóch liczb całkowitych i manipulują nimi.

Gdy sprawy stają się coraz bardziej interesujące, bardzo szybko wkraczasz w świat abstrakcyjnych typów danych. Na przykład sito Eratostenesa opiera się na tablicy. Moglibyśmy teraz porozmawiać, czy tablica nadal jest prymitywna, czy w rzeczywistości możesz porozmawiać, jeśli liczba całkowita nie jest już strukturą danych. Tak czy inaczej, algorytmy, które istnieją całkowicie bez struktur danych, są nudne, nawet jeśli zaakceptujesz ich izolowane istnienie.

Algorytmy połączone ze strukturami danych, czyli abstrakcyjne typy danych

Teraz są to interesujące, ale z dwóch bardzo różnych powodów. Zazwyczaj można do nich podejść z dwóch kierunków: najpierw struktury danych lub najpierw algorytmu.

Podczas gdy abstrakcyjny typ danych jest definiowany przez kombinację struktury danych + algorytmy / operacje, często oglądamy je, koncentrując się na jednym z nich, i uważamy drugi za czynnik umożliwiający.

Struktura danych, a następnie algorytm

Spotkasz abstrakcyjne typy danych, które są raczej proste w użyciu, ale wymagają mniej lub bardziej skomplikowanych algorytmów, aby działały wewnętrznie. Na przykład, a HashMapjest trywialny w użyciu, ale wymaga sprytnej funkcji skrótu i ​​radzenia sobie z kolizjami skrótu wewnątrz. Jednak z twojego punktu widzenia jako użytkownika zależy Ci na tym, że jest to coś, co przechowuje dane dla Ciebie, a nie coś, co coś dla Ciebie robi.

W przeciwieństwie do ostatniej grupy poniżej, te struktury danych nie narażają użytkowników na te algorytmy. Nie musisz wiedzieć ani przejmować się HashMapwewnętrzną funkcją skrótu, aby móc z niej korzystać. (Aby jednak efektywnie z niego korzystać, możesz chcieć poznać te rzeczy;)

Algorytm, a następnie struktura danych

Drugi kierunek oznacza, że ​​masz algorytm, którego chcesz po prostu użyć, ale który potrzebuje wewnętrznych struktur danych, aby działał zgodnie z przeznaczeniem. Przykładem może być algorytm partycjonowania przestrzeni binarnej (BSP), który można po prostu poprosić o dwuwymiarowy Pointz dużego zestawu punktów najbliższego danemu punktowi zapytania. Jednak potrzebujesz struktury drzewa (a nawet dodatkowych algorytmów, takich jak obliczanie odległości) od wewnątrz, aby faktycznie napisać algorytm.

Ogólnie można powiedzieć, że algorytmy w tej grupie wykorzystują struktury danych do reprezentacji ich stanu wewnętrznego. Twierdziłbym, że ta grupa algorytmów jest najbardziej różnorodna i znajdziesz wiele różnych, które pasują do tego ogólnego schematu. Jeśli chodzi o punkt widzenia, uważamy je za interesujące, ponieważ robią dla nas coś (np. Sortowanie) i nie dbają tak bardzo o część przechowującą dane.

Ściśle powiązane struktury danych i algorytmy

Wreszcie, masz struktury danych, które są bardzo blisko związane z algorytmami, które bezpośrednio z nimi odpowiadają. Typowym przykładem jest drzewo binarne, które, gdy chcesz zrobić z nim coś sensownego, wymusza na tobie temat algorytmów chodzenia po drzewie (najpierw głębokość, najpierw szerokość, cokolwiek).

W takich przypadkach co jakiś czas zmieniamy skupienie naszego widoku na wynikowe abstrakcyjne typy danych. Czasami zależy Ci na strukturze drzewa, kilka minut później zależy Ci na możliwości uruchomienia operacji wyszukiwania, potem zastanawiasz się nad usunięciem węzła i od razu widać, jak potem wygląda struktura. Chociaż wszystko to obowiązuje również w innych sekcjach powyżej, nie jest to coś, na czym koncentruje się twój umysł, na przykład, gdy przechowujesz / odzyskujesz dane do / z Maplub sortujesz połączoną listę.

Struktury danych często wpływają na szczegóły algorytmu. Z tego powodu często idą w parze.

Rozważ na przykład algorytm koszenia trawnika. Rzeczywista struktura trawnika może mieć wpływ na sposób, w jaki kosisz trawnik. Jeśli mieszkasz w małym domu na gęsto zabudowanym przedmieściu, a Twój trawnik jest tylko małym prostokątem o powierzchni kilku metrów kwadratowych, prawdopodobnie wolisz kosić trawnik za pomocą kosiarki zamiast traktora / kosiarki. Jeśli Twój trawnik obejmuje wiele akrów płaskiej łąki, możesz preferować kosiarkę jeżdżącą, a nie kosiarkę pchającą (chociaż każda kosiarka może ostatecznie wykonać pracę). Jeśli Twój trawnik obejmuje akry ziemi z dużymi płaskimi obszarami, ale z kilkoma małymi wzgórzami i wieloma drzewami, możesz opracować bardziej interesujący algorytm cięcia trawnika, który obejmuje zarówno kosiarkę jeżdżącą, jak i kosiarkę pchającą lub inną trawę techniki cięcia.

Ostatecznie jednak struktura danych może mieć znaczący wpływ na decyzje dotyczące sposobu opracowania algorytmu (lub algorytmów, które należy zastosować). Z tego powodu te dwa tematy często idą w parze.

I odwrotnie: czasami algorytm, który chcemy zastosować, wpływa (przynajmniej na początku obliczeń) na struktury danych opracowane w celu obsługi algorytmu. Na przykład przejście od listy tablic do pomysłu listy połączonej i ostatecznie do BST do przechowywania uporządkowanej listy, która pozwoli na szybkie znalezienie.