Złożoność obliczeniowa

Jak mierzyć trudność problemów? Trudność albo, inaczej mówiąc, ich skomplikowanie, złożoność. To nie jest łatwe pytanie. Aby móc na nie chociaż nieco sensownie odpowiedzieć, skupimy się tu na tzw. problemach decyzyjnych, czyli takich, na które odpowiedź zawsze brzmi "tak" lub "nie". Żeby określić, jak złożone są te problemy, przyjmuje się zasadę, że problem jest tak trudny, jak jego najlepsze rozwiązanie. Innymi słowy mówimy, że złożoność problemu jest równa złożoności najlepszego algorytmu, który go rozwiązuje.

Jak jednak określić złożoność algorytmu? Pierwszy sposób mierzenia, który przychodzi nam do głowy, a mianowicie czas działania, ma duże wady. Zależy on bardzo od tego, na jak szybkim komputerze działa algorytm i od tego, jak duże są dane wejściowe (np. czy liczba, którą badamy, ma 10 cyfr, czy też 1 000 000). Rozwiązaniem pierwszej z tych wad jest mierzenie czasu nie w sekundach, ale w liczbie operacji wykonanych przez dany algorytm - ona nie zależy już od tego, na jakim sprzęcie wykonujemy algorytm. Z drugą wadą trudniej sobie poradzić. Najbardziej popularnym rozwiązaniem jest tzw. pesymistyczna złożoność czasowa. Mówimy, że dany algorytm ma pesymistyczną złożoność czasową $| f N N,$ jeśli maksymalna liczba operacji, którą wykonuje dla danych wejściowych o rozmiarze $|n,$ to $| f(n).$ Zazwyczaj nie interesuje nas dokładna wartość $f,$ wiedza, że przykładowo $2 f(n) = 3n + 5n + 17,$ tylko raczej to, jak $| f$ zachowuje się dla dużych danych, czyli dużych $n.$ W naszym przypadku powiemy, że $| f$ jest proporcjonalne do $n2$ dla dużych $n,$ i zapiszemy $f(n) = Θ$ Często przy badaniu złożoności nie umiemy poznać dokładnego zachowania algorytmu, a jesteśmy w stanie jedynie ustalić pewne górne oszacowanie na liczbę operacji, które ten algorytm wykonuje. Wówczas używamy tak zwanej notacji $O,$ piszemy na przykład, że $f (n) = O(n3),$ co oznacza, że dla dużych $n$ funkcja $f$ jest proporcjonalna do $n3$ lub od niej mniejsza.

Wypada przy okazji wspomnieć, że pesymistyczna złożoność czasowa to najpopularniejszy sposób mierzenia złożoności programów, ale dalece nie jedyny. Dość często używa się średniej złożoności czasowej, która to dla $|n∈ N$ zwraca średnią liczbę operacji, jakie algorytm wykonuje dla danych wejściowych rozmiaru $| n.$ Nieraz bada się też inne parametry algorytmu, często zamiast liczby wykonywanych operacji rozważa się rozmiar pamięci, której używa dany algorytm. Wówczas mówimy o złożoności pamięciowej; znów może być ona pesymistyczna, średnia albo jeszcze inna. Można też iść dużo dalej, istnieje cały dział informatyki teoretycznej, złożoność obliczeniowa, który zajmuje się próbą zrozumienia, jak złożone są różne problemy. Jest tam wiele fascynujących tematów i pytań, które wciąż czekają na rozwiązanie.