Klasyfikacja algorytmów w C#

Skoro wiesz już, czym jest algorytm i jakie cechy powinien spełniać, czas na pytanie praktyczne: jak algorytmy dzieli się na kategorie? Ta klasyfikacja nie jest akademicką ciekawostką — rozpoznanie, do jakiej kategorii pasuje Twój problem, od razu podpowiada, jakiej techniki szukać. Istnieje kilka niezależnych sposobów klasyfikacji algorytmów — ze względu na metodę konstrukcji, kolejność wykonywania działań, sposób wykonywania operacji oraz obszar zastosowań.

Klasyfikacja ze względu na metodę konstrukcji

To najbardziej praktyczny podział — mówi, jak algorytm podchodzi do rozwiązania problemu:

Dziel i zwyciężaj (divide and conquer)

Problem jest dzielony na kilka mniejszych, niezależnych podproblemów, te znów dzielone są dalej, aż do uzyskania przypadków trywialnych do rozwiązania — wyniki cząstkowe są następnie łączone w rozwiązanie całości. To jedna z najskuteczniejszych metod projektowania algorytmów. Klasyczne przykłady na tym blogu: Merge Sort i Quick Sort — oba dzielą tablicę na mniejsze fragmenty, sortują je osobno, a potem łączą wynik.

Metoda zachłanna (greedy)

Algorytm nie analizuje całego problemu — na każdym kroku wybiera rozwiązanie, które w danym momencie wygląda na najkorzystniejsze, licząc, że lokalnie optymalne wybory złożą się na dobre rozwiązanie globalne. Nie zawsze tak jest, ale gdy działa, bywa bardzo wydajny. Przykład: algorytm Kruskala do budowy minimalnego drzewa rozpinającego — na każdym kroku dobiera najtańszą krawędź, która nie tworzy cyklu.

Poszukiwanie i wyliczanie (brute-force)

Zbiór danych jest przeszukiwany aż do znalezienia rozwiązania — bez żadnych skrótów. Przykłady: wyszukiwanie liniowe (sprawdzasz element po elemencie) i, choć nieco sprytniejsze, wyszukiwanie binarne (dzielisz przeszukiwany zakres na pół w każdym kroku).

Programowanie dynamiczne

Podobnie jak w metodzie dziel i zwyciężaj, problem dzielony jest na mniejsze podproblemy — kluczowa różnica polega na tym, że wyniki podproblemów są zapamiętywane i ponownie wykorzystywane, zamiast liczone od nowa za każdym razem, gdy się powtarzają. Pełne omówienie tej techniki (wraz z klasycznym przykładem ciągu Fibonacciego) znajdziesz w artykule Opanowanie programowania dynamicznego.

Heurystyka

Na podstawie niepełnych danych tworzony jest algorytm, który działa w sposób najbardziej prawdopodobny. Metody heurystyczne nie gwarantują poprawnego rozwiązania — dają rozwiązania przybliżone, ale często wystarczająco dobre, gdy dokładne rozwiązanie byłoby zbyt kosztowne obliczeniowo (np. w problemach klasy NP-trudnych).

Klasyfikacja ze względu na kolejność wykonywania działań

• Liniowy — kolejne kroki wykonywane są dokładnie w kolejności, w jakiej zostały zapisane. Żaden krok nie może być pominięty ani powtórzony.
• Warunkowy — wykonanie poleceń zależy od spełnienia (lub nie) określonego warunku — rozgałęzienie if/else.
• Iteracyjny — grupa poleceń jest powtarzana wielokrotnie, z góry określoną liczbę razy albo aż do spełnienia warunku. Pełne omówienie znajdziesz w artykule o pętlach w C#.

Klasyfikacja ze względu na sposób wykonania operacji

• Sekwencyjne — operacje wykonywane są w kolejności, w jakiej zostały napisane, bez powtórzeń.
• Iteracyjne — niektóre kroki powtarzane są aż do spełnienia wymaganego warunku.
• Rekurencyjne — algorytm odwołuje się sam do siebie dla mniejszej wersji tego samego problemu, aż do osiągnięcia warunku zakończenia (przypadku bazowego). Zobacz na przykładzie algorytmu Euklidesa (największy wspólny dzielnik) albo ciągu Fibonacciego.

Klasyfikacja ze względu na obszar zastosowań

• Matematyczne — wykonują obliczenia numeryczne, np. algorytm Euklidesa czy ciąg Fibonacciego.
• Przeszukujące — znajdują konkretny element w zbiorze danych: wyszukiwanie liniowe, wyszukiwanie binarne.
• Porządkujące (sortujące) — ustawiają elementy zbioru w określonej kolejności. Na blogu znajdziesz kilka podejść o różnej złożoności: sortowanie bąbelkowe, sortowanie przez wstawianie, selection sort, bucket sort, merge sort i quick sort.
• Szyfrujące — kodują dane tak, że ich odczyt bez znajomości klucza jest niemożliwy (poza zakresem tego bloga, ale warto wiedzieć, że to osobna, ogromna gałąź algorytmiki).

Dlaczego ta klasyfikacja się przydaje

Rozpoznanie kategorii problemu zawęża przestrzeń rozwiązań. Jeśli widzisz, że problem naturalnie dzieli się na niezależne podproblemy — myśl “dziel i zwyciężaj” albo, jeśli podproblemy się powtarzają, “programowanie dynamiczne”. Jeśli szukasz elementu w posortowanych danych — myśl “przeszukiwanie”, konkretnie wyszukiwanie binarne zamiast liniowego. Ta intuicja jest tym, czego szukają rekruterzy podczas rozmów technicznych: nie znajomości gotowych rozwiązań na pamięć, tylko umiejętności rozpoznania, do jakiej kategorii pasuje nowy, nieznany wcześniej problem.