Teoria złożoności obliczeniowej

Wprowadzenie

Wraz z rozwojem informatyki, a tym samym algorytmiki, narastała potrzeba oceny jakości algorytmów. Na przełomie wielu lat pojawiło się bowiem wiele algorytmów rozwiązujących te same problemy na różne sposoby. Narastająca potrzeba oceny jakości algorytmów przyczyniła się do powstania teorii złożoności obliczeniowej, która na dzień dzisiejszy jest powszechnie stosowaną i uznawaną techniką do porównywania wydajności algorytmów. Wydajność algorytmów z kolei rozpatrywana jest obecnie według dwóch wiodących kryteriów tj. wg złożoności czasowej oraz wg złożoności pamięciowej.

Złożoność algorytmów

Niezależnie od rozpatrywanego rodzaju złożoności obliczeniowej, tj. złożoności czasowej czy też złożoności pamięciowej; u podstaw znajduje się teoria będąca częścią wspólną dla obu wymienionych zagadnień. Celem złożoności obliczeniowej jest de-facto możliwość oszacowania teoretycznej pesymistycznej, średniej oraz optymistycznej wydajności danego algorytmu. Aby istniała możliwość szacowania złożoności obliczeniowej, koniecznym było zdefiniowanie wspólnej miary algorytmów, która byłaby niezależna od zastosowanego języka programowania, sprzętu czy też kompilatora. Miara taka została zdefiniowana i jest nią liczba danych wejściowych przekazywanych do algorytmu.

Złożoność czasowa

Kluczową rolę w dziedzinie algorytmiki pełni złożoność czasowa algorytmów. Za pomocą niej określamy jak długo dany algorytm musi pracować aby wykonał swoje zadanie. Czas pracy algorytmu nie jest wyrażany w sekundach, lecz w jednostkach, którym nie jest przypisana żadna rzeczywista miara. Czas pracy algorytmu jest więc w praktyce liczbą, której wartość jest uzależniona od liczby danych wejściowych oraz zasad opisujących sposób ich przetwarzania przez dany algorytm. Warto również wiedzieć, że złożoność czasową algorytmów oznacza się zawsze dużą literą O.

Złożoność pamięciowa

Celem złożoności pamięciowej jest oszacowanie zużycia pamięci przez dany algorytm. Złożoność pamięciową podobnie jak w przypadku złożoności obliczeniowej szacuje się na podstawie liczby danych wejściowych, przekazanych do algorytmu oraz sposobu ich przetwarzania przez dany algorytm. W przypadku szacowania złożoności pamięciowej rozpatruje się tylko i wyłącznie pamięć, którą należy dodatkowo zaalokować w trakcie pracy algorytmu tak, aby było możliwe jego wykonanie zgodnie z zasadami określającymi sposób działania algorytmu. Do złożoności pamięciowej nie wlicza się więc rozmiaru danych wejściowych, które zostały przekazane do danego algorytmu. Na koniec warto jeszcze wspomnieć o jednostce miary stosowanej do mierzenia zużycia pamięci. W przypadku szacowania złożoności pamięciowej, za miarę generalnie przyjmuje się liczbę pamięci RAM, jaką należy dodatkowo zaalokować na abstrakcyjnej maszynie. Zapotrzebowanie pamięci RAM w teorii złożoności obliczeniowej wyrażane jest więc w bitach lub bajtach.