Algorytmy i Struktury Danych

Czym są Algorytmy?

Algorytm to skończona, niejednoznaczna sekwencja instrukcji rozwiązująca problem. Badanie algorytmów bada poprawność (czy generuje prawidłową odpowiedź?) oraz wydajność (ile czasu i pamięci zużywa). Struktury danych organizują dane tak, aby algorytmy mogły działać efektywnie. Razem stanowią podstawę informatyki.

Klasy złożoności Big-O

Czas i Złożoność Przestrzenna

Notacja Wielomianowa opisuje górną granicę asymptotyczną czasu wykonywania w funkcji rozmiaru wejścia n, pomijając stałe i wyższe rzędy. Formalnie: f(n) = O(g(n)) jeśli istnieją c i n₀ takie, że f(n) ≤ c·g(n) dla wszystkich n ≥ n₀.

Znaczenie praktyczne: Algorytm O(n²) na n = 10⁶ wymaga około ~10¹² operacji. Algorytm O(n log n) wymaga jedynie ~2×10⁷ — różnica wynosząca 50 000 razy. Wybór algorytmu dominuje prędkość sprzętu. Żaden sprzęt nie sprawi, że algorytm O(n!) będzie wykonalny dla dużych n. Wielomian Wzrostu (Ω) daje dolne ograniczenia; Wielomian Ciągłości (Θ) daje rygorystyczne ograniczenia.

Algorytmy Sortowania

Python wykorzystuje Timsort (hybryda merge sortu i insertion sortu). C++ STL wykorzystuje Introsort (hybryda quicksortu, heapsortu i insertion sortu). W przypadku prawie posortowanych danych, insertion sort wygrywa. Merge sort, gdy potrzebne jest zachowanie kolejności. Heap sort zapewnia gwarantowany czas O(n log n) przy użyciu O(1) pamięci.

Binarne Wyszukiwanie i Podział i Zwycięstwo

Binarne wyszukiwanie znajduje element w posortowanym tablicy w czasie O(log n): porównaj z środkiem; rekurencyjnie przeszukaj odpowiednią połowę. Tylko 20 porównań wystarczy dla 10^6 elementów.

Podział i Zwycięstwo: (1) podziel na podproblemy; (2) rozwiąż rekurencyjnie; (3) połącz. Rekurencja T(n) = 2T(n/2) + O(n) prowadzi do O(n log n) zgodnie z Twierdzeniem Master. Przykłady: FFT (O(n log n)), mnożenie Karatsuba (O(n^1,585)), mnożenie macierzy Strassena (O(n^2,81)).

Algorytmy Grafowe

Grafy G=(V,E) modelują relacje. Większość rzeczywistych problemów związanych z trasowaniem, planowaniem i sieciami redukuje się do problemów grafowych.

BFS — przeszukiwanie wszerz

O(V+E). Odwiedza wszystkie sąsiedzki węzły jako pierwsze; wykorzystuje kolejkę. Znajduje najkrótszą ścieżkę (w niezważających na wagę grafach). Jest używane w wyszukiwarkach internetowych, odległościach w sieciach społecznościowych i algorytmie wypełniania obszarów.

DFS — przeszukiwanie wgłębiące

O(V+E). Eksploruje tak głęboko, jak to możliwe jako pierwsze; wykorzystuje stos lub rekursję. Jest używane do sortowania topologicznego, wykrywania cykli, SCC i rozwiązywania labiryntów.

Algorytm Dijkstry”,

O((V+E) log V) z kolejką priorytetową. Najkrótsza ścieżka z pojedynczego źródła w grafie o nieujemnych wagach. Napędza nawigację GPS i routing OSPF.

Algorytm Bellmana-Ford

O(VE). Obsługuje krawędzie o ujemnej wadze i wykrywa cykle o ujemnej wadze. Jest używany w routingu internetowym BGP. Rozwiązuje wszystkie krawędzie V−1 razy.

Floyd-Warshall (all-pairs shortest paths): O(V^3) for k in 1..V: for i in 1..V: for j in 1..V: dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]) Minimum Spanning Tree: Kruskal's: O(E log E) - sort edges, add if no cycle (union-find) Prim's: O((V+E) log V) - grow MST from a seed vertex

Programowanie Dynamiczne

Programowanie dynamiczne (DP) rozwiązuje problemy optymalizacyjne poprzez rozbijanie ich na nakładające się podproblemy i przechowywanie rozwiązań, aby uniknąć ponownego obliczania. Dwa podejścia:

Memoizacja (top-down): rekurencyjnie rozwiązuj, kacheguj wyniki (np. Fibonacciego z memoizacją: O(n) zamiast O(2^n)).

Tabulacja (bottom-up): wypełniaj tabelę od najmniejszych podproblemów w górę; eliminuje ryzyko przepełnienia stosu.

Classic DP problems: Fibonacci: F(n) = F(n-1) + F(n-2) O(n) time, O(n) space 0/1 Knapsack: dp[i][w] = max(dp[i-1][w], v_i + dp[i-1][w-w_i]) O(nW) Longest Common dp[i][j] = dp[i-1][j-1]+1 (match) Subsequence: = max(dp[i-1][j], dp[i][j-1]) (no match) Edit Distance: dp[i][j] = min(insert, delete, replace) Coin Change: dp[i] = min dp[i-c] + 1 for each coin c

Algorytmy Greedy

Algorytmy greedy podejmują lokalnie optymalne decyzje na każdym kroku, licząc na osiągnięcie globalnego optimum. Są prostsze i szybsze niż algorytmy DP, ale działają poprawnie tylko dla specyficznych struktur problemów.

Poprawne algorytmy greedy: minimalny koszt drzewa rozpinającego Kruskala, minimalne drzewo rozpinające Prima, algorytm Dijkstry (z ujemnymi wagami), kodowanie Huffmana (optymalne kody prefiksowe), planowanie przedziałów czasowych (wybierz według najwcześniejszego czasu zakończenia).

Niepoprawne algorytmy greedy: plecak 0/1 (wersja frakcyjna jest rozwiązywalna przez algorytm greedy; wersja całkowita nie jest), najkrótsza ścieżka z ujemnymi krawędziami, optymalizacja zmian z arbitralnych systemów monet.

Niezmienniczość NP

Pytanie o P kontra NP jest centralnym nierozwiązanym problemem w informatyce komputerowej. Definicje:

P: problemy decyzyjne, które można rozwiązać w czasie wielomianowym.

NP: problemy decyzyjne, których rozwiązania można zweryfikować w czasie wielomianowym (ale niekoniecznie je rozwiązać w czasie wielomianowym).

Niezmienniczość NP: problemy, które należą do NP i każdy problem z klasy NP można do nich zredukować w czasie wielomianowym.

Niezmienniczość NP-hard: problemy, które są co najmniej tak trudne jak problemy niezmienniczości NP; niekoniecznie należą do NP.

Słynne problemy niezmienniczości NP: Zadowalająca Wariacja (SAT), Problem Turisty, Kolorowanie Grafu, Szlak Hamiltona, Suma Podzbiorów, Torba z Ograniczeniami. Jeśli P = NP, wszystkie te problemy miałyby rozwiązania w czasie wielomianowym — większość bezpieczeństwa kryptograficznego uległaby upadkowi. Większość teoretyków złożoności uważa, że P ≠ NP, ale pytanie pozostaje otwarte (Problem Milenialularza Clay, nagroda 1 mln dolarów).

Wypróbuj na żywo

Wszystko powyżej działa bezpośrednio w Twojej przeglądarce — otwórz Hash Function Avalanche Visualizer i zmieniaj parametry podczas działania. Nic nie jest instalowane ani przesyłane na serwer, cały model działa w jednej karcie.