Algorytmy krok po kroku w C#

Ten artykuł to przegląd tematów algorytmicznych, których nie znajdziesz w pojedynczym, dedykowanym wpisie na blogu — przede wszystkim algorytmów grafowych i klas złożoności problemów. Jeśli szukasz definicji algorytmu i jego podstawowych cech, zajrzyj do artykułu Algorytm w programowaniu. Jeśli chcesz wiedzieć, jak algorytmy dzieli się na kategorie i który wpis pasuje do którego typu problemu, zobacz Klasyfikację Algorytmów.

Złożoność czasowa i przestrzenna — szybkie przypomnienie

Złożoność czasowa opisuje, jak czas działania algorytmu rośnie wraz z rozmiarem danych wejściowych (n). Złożoność przestrzenna opisuje analogicznie zużycie pamięci. Zapis Big O (np. O(n), O(log n), O(n²)) mówi o zachowaniu w najgorszym przypadku, gdy n rośnie do nieskończoności — nie o dokładnym czasie w sekundach.

Podstawowe struktury danych — w skrócie

Algorytmy operują na strukturach danych, które organizują informacje pod kątem konkretnych operacji. Na blogu każda ma swój dedykowany artykuł z pełnym API i analizą złożoności: Stack<T> (LIFO), Queue<T> (FIFO), HashSet<T> (unikalne elementy, O(1) wyszukiwanie), SortedSet<T> (posortowany zbiór unikalny). Dwie z nich — stos i kolejka — są też fundamentem algorytmów grafowych opisanych niżej.

Sortowanie i wyszukiwanie — pełna lista na blogu

Zamiast powtarzać przykłady, oto komplet dedykowanych artykułów, każdy z analizą złożoności krok po kroku: sortowanie bąbelkowe, sortowanie przez wstawianie, selection sort, bucket sort, merge sort, quick sort, a z wyszukiwania — wyszukiwanie liniowe i wyszukiwanie binarne.

Rekurencja — kiedy się przydaje i na co uważać

Algorytm rekurencyjny rozwiązuje problem, odwołując się do rozwiązań mniejszych wystąpień tego samego problemu — dokładnie jak w algorytmie Euklidesa czy ciągu Fibonacciego. Mechanizmem, który to umożliwia, jest stos wywołań (call stack) — każde wywołanie odkłada na niego swoją ramkę, a powrót z funkcji ją zdejmuje. Zbyt głęboka rekurencja bez warunku stopu zapełnia ten stos i kończy się StackOverflowException — pełne wyjaśnienie mechanizmu znajdziesz w artykule o Stack<T>.

Algorytmy grafowe: DFS, BFS, Dijkstra

Graf to struktura złożona z wierzchołków (węzłów) połączonych krawędziami — modeluje sieci, mapy dróg, relacje w mediach społecznościowych czy zależności między zadaniami. W C# graf najczęściej reprezentuje się jako słownik list sąsiedztwa:

var graph = new Dictionary<int, List<int>>
{
    [1] = new List<int> { 2, 3 },
    [2] = new List<int> { 1, 4 },
    [3] = new List<int> { 1, 4 },
    [4] = new List<int> { 2, 3 }
};

Dwie podstawowe strategie przechodzenia po grafie różnią się kolejnością odwiedzania węzłów:

• DFS (Depth-First Search) — przeszukiwanie w głąb, zagłębia się jak najdalej jedną gałęzią, zanim się cofnie. Naturalnie realizowane przez stos (albo rekurencję). Pełny przykład z kodem znajdziesz w artykule o Stack<T>.
• BFS (Breadth-First Search) — przeszukiwanie wszerz, odwiedza wszystkich najbliższych sąsiadów, zanim przejdzie dalej. Naturalnie realizowane przez kolejkę. Pełny przykład z kodem znajdziesz w artykule o Queue<T>.

BFS ma istotną, praktyczną przewagę nad DFS: dla grafu bez wag krawędzi gwarantuje znalezienie najkrótszej ścieżki (najmniejszej liczby krawędzi) między dwoma węzłami — bo odwiedza węzły warstwa po warstwie, w kolejności rosnącej odległości od startu.

Algorytm Dijkstry — najkrótsza ścieżka z wagami

Gdy krawędzie mają różne “koszty” (odległości, czas, cenę), zwykłe BFS już nie wystarczy — potrzebny jest algorytm Dijkstry, który zawsze rozwija następny najtańszy dotychczas znaleziony węzeł. W .NET najwygodniej zaimplementować go za pomocą wbudowanej kolejki priorytetowej:

static Dictionary<int, int> Dijkstra(
    Dictionary<int, List<(int Node, int Weight)>> graph, int start)
{
    var distances = graph.Keys.ToDictionary(node => node, _ => int.MaxValue);
    distances[start] = 0;

    var queue = new PriorityQueue<int, int>();
    queue.Enqueue(start, 0);

    while (queue.TryDequeue(out var current, out var currentDistance))
    {
        if (currentDistance > distances[current]) continue; // nieaktualny wpis

        foreach (var (neighbor, weight) in graph[current])
        {
            int newDistance = currentDistance + weight;

            if (newDistance < distances[neighbor])
            {
                distances[neighbor] = newDistance;
                queue.Enqueue(neighbor, newDistance);
            }
        }
    }

    return distances;
}

PriorityQueue<TElement, TPriority> (dostępna od .NET 6) zawsze zwraca element o najniższym priorytecie — tu: węzeł o najmniejszym dotychczas znanym dystansie. To sedno algorytmu Dijkstry: zachłannie rozwijaj najbliższy nieodwiedzony węzeł, aktualizując dystanse sąsiadów, aż przetworzysz cały graf (lub osiągniesz cel).

Blisko spokrewniony jest algorytm Prima do budowy minimalnego drzewa rozpinającego — działa podobnie zachłannie, krok po kroku dobierając najtańszą krawędź łączącą drzewo z resztą grafu. Na tym blogu opisany jest alternatywny algorytm do tego samego celu — algorytm Kruskala, który zamiast rozbudowywać jedno drzewo, sortuje wszystkie krawędzie i dobiera najtańsze, które nie tworzą cyklu.

Algorytmy zachłanne w praktyce — problem wydawania reszty

Klasyczny przykład zachłannego podejścia: wydawanie reszty jak najmniejszą liczbą monet. Algorytm zawsze wybiera największy nominał, który się jeszcze mieści w pozostałej kwocie:

static List<int> MakeChange(int amount, int[] nominaly)
{
    var result = new List<int>();

    foreach (var nominal in nominaly.OrderDescending())
    {
        while (amount >= nominal)
        {
            result.Add(nominal);
            amount -= nominal;
        }
    }

    return result;
}

// MakeChange(68, [50, 20, 10, 5, 1]) => [50, 10, 5, 1, 1, 1]

Dla “typowych” systemów monetarnych (jak polski) podejście zachłanne daje optymalny wynik. Ale to ważna pułapka: przy dowolnym zestawie nominałów zachłanność nie zawsze daje najmniejszą możliwą liczbę monet — np. dla nominałów {1, 3, 4} i kwoty 6, zachłannie dostaniesz 4 + 1 + 1 (3 monety), podczas gdy optymalne jest 3 + 3 (2 monety). To dobra ilustracja tego, dlaczego “lokalnie najlepszy wybór” nie zawsze prowadzi do globalnie najlepszego rozwiązania — dokładny wynik dla dowolnych nominałów wymaga już programowania dynamicznego, opisanego w osobnym artykule.

Klasy złożoności: P, NP, NP-zupełne, NP-trudne

To rozróżnienie odpowiada na pytanie: które problemy da się rozwiązać “szybko”, a które prawdopodobnie nigdy?

• P — problemy rozwiązywalne w czasie wielomianowym (np. sortowanie, wyszukiwanie binarne, najkrótsza ścieżka Dijkstrą).
• NP — problemy, których zaproponowane rozwiązanie da się szybko zweryfikować, nawet jeśli samo jego znalezienie może być bardzo kosztowne (np. sprawdzenie, czy dana trasa komiwojażera jest krótsza niż X, jest szybkie — znalezienie najkrótszej trasy w ogóle, nie).
• NP-zupełne — najtrudniejsze problemy w klasie NP; znalezienie szybkiego rozwiązania dla jednego z nich (np. problemu spełnialności formuł logicznych, SAT) automatycznie dałoby szybkie rozwiązanie dla wszystkich problemów NP. Nikt dotąd tego nie znalazł — to jeden z siedmiu Problemów Milenijnych (P vs NP).
• NP-trudne — co najmniej tak trudne jak najtrudniejsze problemy NP, ale niekoniecznie same należą do NP (bo ich rozwiązania mogą nie dać się szybko zweryfikować).

W praktyce, gdy trafisz na problem NP-zupełny (np. wariant plecakowy, problem komiwojażera), nie szukaj dokładnego, szybkiego rozwiązania dla dużych danych wejściowych — to prawdopodobnie ślepy zaułek. Zamiast tego sięgnij po algorytm zachłanny lub heurystykę dającą dobre, choć nie zawsze optymalne, rozwiązanie w rozsądnym czasie.

Podsumowanie

Ten przegląd celowo nie powtarza szczegółów, które mają już swoje dedykowane artykuły na blogu — sortowania, wyszukiwania, struktur danych, programowania dynamicznego. Jego rolą jest domknięcie obrazu o tematy, które inaczej byłyby rozproszone: złożoność obliczeniowa jako wspólny język do porównywania algorytmów, przechodzenie grafów (DFS, BFS, Dijkstra), praktyczne ograniczenia podejścia zachłannego oraz granice tego, co w ogóle da się efektywnie policzyć (P vs NP).