złożoność obliczeniowa

Złożoność obliczeniowa – omówienie i przykłady

Na łamach blogu często pojawiało się wyrażenie „złożoność obliczeniowa” – zwłaszcza przy algorytmach sortujących. Określeniu temu towarzyszył, zazwyczaj, z pozoru dziwny wzór przy literce O. Jest to istotne zagadnienie, które jest przydatne na maturze z informatyki. Omówimy więc dzisiaj czym jest złożoność obliczeniowa, a także w jaki sposób możemy ją wyrażać.

Pojęcie złożoności

Zanim przejdziemy do złożoności obliczeniowej, warto najpierw wyjaśnić, czym jest sama złożoność. Odkąd komputery istniały, potrzeba było sposobu na określenie zasobów potrzebnych do wykonania programu. Było to szczególnie ważne, gdyż dawniej urządzenia miały ograniczoną moc obliczeniową – wielokrotnie niższą niż dzisiejsze smartfony. Aby uprać się z tym problemem powstały takie pojęcia, jak złożoność obliczeniowa, która określa ilość operacji wymaganych do wykonania całego programu, czy złożoność pamięciowa, która określa ilość pamięci operacyjnej wymaganej do wykonania programu.

Ale po co się martwić?

A no trzeba się martwić – gdy algorytm wykonujący 1000 operacji zostanie uruchomiony 10^7 razy, to zapewniam Cię, że zauważysz jak wolno on działa :).  Innymi słowy, pojedyncze uruchomienie algorytmu o wysokiej złożoności obliczeniowej nie spowoduje zauważalnego spadku wydajności programu, jednak jego implementacja w projektach przetwarzających duże ilości danych będzie już odczuwalna. Krócej mówiąc: optymalizacja tego wymaga, moi drodzy.

Jak obliczyć złożoność obliczeniową algorytmu?

Aby określić złożoność obliczeniową algorytmu, musimy zliczyć ilość wykonywanych przez niego operacji. Za pojedynczą operację uznajemy każdą, prostą instrukcję jak inicjalizacja zmiennej, wykonanie działania, czy zwrócenie wyniku metody. Przyjmijmy że f(n) to funkcja zwracająca ilość operacji, w zależności od ilości wprowadzanych danych n. Spójrzmy na poniższe przykłady:

C++

Java

Python

Powyższe funkcje wykonują dokładnie jedną operację. Oznacza to, że ich złożoność obliczeniową możemy wyrazić jako f(n) = 1 (niezależnie od n funkcja print zawsze wykona się raz).

C++

Java

Python

Funkcja wypisz wywołuje teraz pętlę, która iteruje n razy. Następnie wykonujemy jeszcze jedną operację poza pętlą. Oznacza to, że nasz algorytm jest teraz zależny od wprowadzonych danych. Jego złożoność obliczeniową możemy więc wyrazić jako f(n) = n + 1.

Idąc tym samym tokiem rozumowania, możemy wyznaczyć ilość wykonywanych operacji dla nieco bardziej skomplikowanych algorytmów. Przyjrzyj się poniższym przykładom:

C++

  Java

Python 

Powyższy program wydrukuje tekst w konsoli n3+2n2+3n+3 razy – jego dokładna złożoność będzie określona więc funkcją f(n) = n3+2n2+3n+3.

W informatyce jednak rzadko kiedy wyznacza się dokładną złożoność obliczeniową. Zamiast tego korzysta się z oszacowań – tzw. notacji O (wielkiego O), Ω(omegi), bądź Θ(theta).

grupa wsparcia matura z informatyki

Notacja O

Najczęściej używana notacja, w której złożoność obliczeniowa jest oszacowywana z góry. Notacja ta jest zgodna z poniższym wzorem:

f(n) = O(g(n))

Oznacza on, że dla dowolnego n istnieje takie n0, dla którego spełniona jest nierówność f(n)<c*g(n). Funkcja f(n) jest co najwyżej rzędu funkcji g(c). Liczba c we wzorze jest pewną, stałą liczbą. Weźmy pod lupę powyższą funkcję f(n) = n3+2n2+3n+3. W notacji wielkiego O pod uwagę bierzemy tylko najistotniejszy wyraz (zazwyczaj z największą potęgą). Szacując złożoność odrzucamy również współczynniki przy wyrazach. Sprawdźmy więc, który wyraz ma największy wpływ na wartość funkcji dla wystarczająco dużego argumentu, np. 10000:

WyrazWartość
n3=1000031000000000000
n2=100002100000000
n=1000010000
33

Wartość wyrazu n3 wzrasta zdecydowanie szybciej od pozostałych, mając coraz to większy wpływ na finalną wartość złożoności obliczeniowej. Oznacza to, że wraz ze wzrostem ilości wprowadzanych danych złożoność obliczeniowa będzie zbliżać się do wartości n3 – dlatego funkcja f(n) ma złożoność O(n3).

Złożoność obliczeniowa - notacja wielkiego O
Fioletowa linia oznacza naszą f(n) = n3+2n2+3n+3, zaś niebieska 20 * g(n) = x3 – liczba 20 jest tu stałą c.

Zwróć uwagę, że jest to tylko oszacowanie. Dla funkcji f(n)=2n+5 oszacowanie O(n^6), będzie jak najbardziej poprawne, aczkolwiek mało precyzyjne.

Notacja Ω

Notacja omega jest przeciwieństwem notacji wielkiego O. Wzór:

f(n)=Ω(g(c)) 

jest prawdziwy, gdy istnieje takie n0, od którego wartość f(n) jest większa od c*g(n). W tym przypadku funkcja f(n) jest co najmniej rzędu funkcji g(n). Dokonujemy więc tu dolnego oszacowania funkcji f(n). Podobnie jak poprzednio nie interesują nas współczynniki stojące przy wyrazach funkcji. Oszacowanie naszej funkcji f(n)=n3+2n2+3n+3 będzie więc wynosiło Ω(n2).

Złożoność obliczeniowa - notacja omega
Fioletowa linia oznacza naszą f(n) = n3+2n2+3n+3, zaś niebieska g(n) = x2 – liczba 1 jest tu stałą c.

Ponownie zwracam uwagę, iż jest to jedynie oszacowanie. Moglibyśmy tutaj podać nawet Ω(n), jednak ponownie, będzie to mało precyzyjne.

Notacja Θ

Notację theta można właściwie traktować jako pewnego rodzaju ciekawostkę. Jest ona połączeniem notacji wielkiego O i omegi. Wzór:

f(n) = Θ(g(n))

jest prawdziwy, gdy c1 * g(n) < f(n) < c2 * g(n). Wyrazy c1 i c2 to pewne, stałe liczby. Wydawać by się mogło, że notacja ta oszacuje najprecyzyjniej złożoność obliczeniową, jednak nie przewiduje ona sytuacji optymistycznych, przez co nieraz oszacowanie może być błędne. Przykładem notacji theta dla naszej funkcji może być Θ(n2):

Złożoność obliczeniowa - notacja theta
Fioletowa linia oznacza naszą f(n) = n3+2n2+3n+3, zaś czerwona g(n) = x2 – stała c1 ma wartość 1. Zielona linia to wykres funkcji 25*g(n) – stała c2 ma więc wartość 25.


Dowiedz się więcej o złożoności obliczeniowej z tej tablicy

Złożoność obliczeniowa – przykłady

Pokażemy teraz przykładowe algorytmy i ich złożoności obliczeniowe, za pomocą notacji wielkiego O.

Stała złożoność obliczeniowa O(1)

Przykład stałej złożoności obliczeniowej pokazaliśmy już dzisiaj przy pierwszym przykładzie. W praktyce złożoność taką osiągają jedynie funkcje, mające za zadanie jedynie zwrócenie pojedynczej wartości.

Liniowa złożoność obliczeniowa O(n)

Program osiąga złożoność O(n), gdy ilość wykonywanych operacji jest wprost proporcjonalna do ilości wprowadzanych danych. Złożoność taką osiągają np. programy mające za zadanie wyszukanie najmniejszego elementu w tablicy:

C++

Java

Python

Kwadratowa złożoność obliczeniowa O(n2)

Kwadratowa złożoność osiągana jest poprzez zagnieżdżenie pętli w pętli. Zabieg taki spotykamy w, owianym złą sławą, algorytmie sortowania bąbelkowego. Przeczytać możesz o nim tutaj. Złożoność O(n2) ma również algorytm sortowania przez wstawianie.

Logarytmiczna złożoność obliczeniowa O(log(n))

Algorytmy o złożoności logarytmicznej są z jednymi z szybszych. Złożoność taka osiągana jest zazwyczaj poprzez dzielenie zadania na mniejsze części, jak ma to np. miejsce w wyszukiwaniu binarnym. Logarytmiczną złożoność obliczeniową osiąga również algorytm sortowania przez scalanie.

Pierwiastkowa złożoność obliczeniowa O(√n)

Podobnie jak w przypadku logarytmicznej złożoności, algorytmy bazujące na pierwiastkowej są uznawane za dosyć szybkie. Złożoność pierwiastkowa osiągana jest zazwyczaj w wyniku pojedynczej iteracji do pierwiastka z n. Przykładem takiego algorytmu jest sprawdzanie, czy liczba jest pierwsza.

Podsumowanie

Jak pewnie sami zauważyliście, złożoność obliczeniowa gra ważną rolę w optymalizacji programów. Niejednokrotnie jej zastosowanie pojawiało się również na maturze z informatyki. Jeżeli więc chcesz się do niej jak najlepiej przygotować, zajrzyj koniecznie do tego wpisu.

You Might Also Like
Dodaj komentarz

icon