Przypuśćmy, że pracujemy w zespole programistów, który otrzymał od szefa zadanie do wykonania. Każdy z programistów ma inny pomysł na napisanie algorytmu. Każda z przedstawionych solucji zwraca prawidłowe wyniki. Jednak niektórzy z nich czekali dłużej niż pozostali, aż komputer wyliczył odpowiedź. Szef postanowił wybrać najlepszy algorytm wyliczając jego efektywność na podstawie złożoności obliczeniowej algorytmu.
W skład złożoności obliczeniowej wchodzi czas wykonywania programu oraz określa liczbę zasobów komputera potrzebnych do wykonania algorytmu.
Złożoność obliczeniową możemy podzielić na dwa główne typy:
Powyższy podział możemy zastosować do poniższych kategorii złożoności. W tym przypadku dzielimy rodzaje złożoności na podstawie używanych zasobów komputera:
Wyznaczając złożoność czasową należy określić operację dominującą. Jest to operacja, która najczęściej jest wykonywana dla każdego elementu danych. Zazwyczaj są to operacje arytmetyczne, przypisania lub porównania (najlepszy przykład to sortowanie). Kolejnym krokiem jest przeanalizowanie działanie algorytmu. Określamy ilość wykonanych operacji dominujących dla określonego zestawu danych. Następnie uogólniamy przypadek dla danych o rozmiarze n.
Jeśli chcemy wyliczyć dokładne złożoności oczekiwane i pesymistyczne to należy rozważyć dla jakich danych algorytm odpowiednio wykonuje się najkrócej / najdłużej. W celu przybliżenia sposobu wyznaczani taki danych warto przyjrzeć się algorytmowi Sortowania Szybkiego, którego złożoność (oczekiwana) to Θ(nlog(n)), ale dla niektórych złożoność (pesymistyczna) wynosi Θ(n2).
Dla określonego zestawu danych określamy ile dla każdego elementu będziemy potrzebowali użyć pamięci w komputerze. W ten sposób będziemy mogli określić np. ile pamięci w komputerze musimy zarezerwować pod działanie naszego programu. W przypadku większych ilości danych złożoność pamięciowa pozwala szybko uzyskać odpowiedź czy program ma szanse na wykonanie się na wybranym komputerze. Problem ten nie występuje w przypadku złożoności obliczeniowej, gdzie dla większego rozmiaru danych będziemy jedynie dłużej czekać na zwrócenie wyniku.
Najbardziej efektywny jest algorytm, którego złożoność czasowa i pamięciowa jest najniższa. W niektórych przypadkach różne rozwiązania algorytmów pozwalając uzyskać szybkie obliczenie przy dużym zużyciu pamięci, a niektóre pozwalają na wolne wykonanie algorytmu, ale praktycznie nie używając do tego pamięci.
Jeśli algorytm spełnia wszystkie powyższe kryteria to możemy nazwać optymalnym. Oznacza to, że nie istnieje lepszy algorytm / metoda, która rozwiązuje postawiony problem.
| Nazwa | Θ | O złożoności | Przykład |
|---|---|---|---|
| Logarytmiczna | logn | algorytmy zmniejszające rozmiar podanych danych w każdej iteracji o połowę | Wyszukiwanie binarne |
| Pierwiastkowa | √n | algorytmy głównie związane z liczbami, które wykonują operację dominujące w zależności od pierwiastka podanych liczb | Wyszukiwanie liczb pierwszych |
| Liniowa | n | algorytmy, które dla każdej danej wykonują operację dominującą | Liniowe wyszukiwanie MAX i MIN |
| Liniowo-logarytmiczna | nlog(n) | algorytmy dzielące dane w każdej iteracji na dwa równe podzbiory i wykonują na nich operacje | Sortowanie przez Scalanie |
| Kwadratowa | n2 | zazwyczaj algorytmy, które wykonują operację dominującą dla każdej pary danych | Sortowanie Bąbelkowe |
Należy pamiętać, że rodzajów złożoności czasowej jest znacznie więcej i zależy to od rozpatrywanego algorytmu