Złożoność Obliczeniowa

Złożoność obliczeniowa to zagadnienie, który warto poznać, gdy wkraczamy w świat algorytmów. Jest to jeden z tematów, który pojawiają się na rozmowach. Warto się z nim zapoznać, dlatego dzisiaj specjalnie dla Ciebie bierzemy go na tapet. To również pierwszy, ale z pewnością nie ostatni artykuł na naszym portalu, który zgłębia tajniki algorytmów. Zaczynajmy!

Najpierw był Algorytm

Zanim przejdziemy bezpośrednio do omawiania Złożoności Obliczeniowej, zacznijmy od krótkiej definicji, czym w ogóle jest algorytm.

Algorytm to zestaw instrukcji, który opisuje jak rozwiązać zadany problem.

Przełóżmy to na sytuacje z codziennego życia.

Jeśli lubisz gotować, prawdopodobnie niejednokrotnie korzystałeś z książki kucharskiej lub przeglądałeś Internet w poszukiwaniu nowych przepisów. Gdy analizujesz dany przepis, zauważasz, że składa się on z kroków, które trzeba wykonać, aby przygotować opisywany posiłek. Właśnie zbiór tych kroków można porównać do kuchennego algorytmu.

Każdy algorytm potrzebuje odpowiednich zasobów do wykonania. Są to czas i pamięć. Ich wymagana ilość możemy zmierzyć za pomocą:

• złożoności czasowej, czyli ilości czasu potrzebnego do wykonania algorytmu w zależności od liczby danych wejściowych
• złożoności pamięciowej, analogicznie jak wyżej, tylko tym razem zamiast czasu mierzymy ilość potrzebnej pamięci

Duże "O"

W celu określenia szybkości i złożoności algorytmów używa się Notacji dużego O. Jej formalna, matematyczna definicja może brzmieć dość skomplikowane, dlatego nie będziemy się nią tutaj zajmować. Opiszemy to prostszymi słowami:

Notacja dużego O mówi nam, jak bardzo czas działania lub zużycie pamięci algorytmu rośnie wraz z ilością danych wejściowych.

Pewnie dalej nie brzmi jasno?

Mówiąc jeszcze prościej, ta notacja określa ilość operacji, potrzebną do wykonania całego algorytmu.

Posłużmy się przykładem, pewnie kojarzysz taką strukturę danych jak tablica. Elementy tablicy mają przypisane odpowiednie indeksy. W momencie gdy chcemy coś z niej wyciągnąć posługujemy się właśnie nimi np:

const elements = ["Element1", "Element2", "Element3"];
console.log(elements[0]); // wypisze na konsoli “Element1”

Czas potrzebny do pobrania elementu nie zależy w tym momencie od liczby elementów w tablicy. **Jest stały. **

Dlaczego?

Tablice są implementowane jako struktury danych, które pozwalają na bezpośredni dostęp do elementów poprzez ich indeksy. Dlatego czas dostępu do danych jest niezależny od liczby elementów.

W notacji dużego O oznaczamy to jako O(1), zamiast 1 możesz podstawić dowolną inną stałą. Dla lepszego zobrazowania popatrzmy na wykres takiej funkcji:

Praktyka czyni mistrza, więc popatrzmy na jeszcze jeden przykład. Tym razem na tapet weźmiemy złożonośc oznaczoną jako O(n). Takie oznaczenie mówi nam o tym, że algorytm, wykona tyle operacji, ile dostanie elementów na wejściu. Czyli może to być najprostsze wypisanie wartości tablicy na konsole:

const elements = ["Element1", "Element2", "Element3"];
for (let i = 0; i < elements.length; i++) {
	console.log(elements[i]);
}

Powyższy kod wykona tyle printów na konsole, ile będzie elementów w tablicy elements.

Ponownie popatrzmy sobie na wykres takiej funkcji:

Ważna rzecz, którą warto zapamiętać:

Złożoność obliczeniowa określa najgorszy przypadek dla zadanego algorytmu!

Co to oznacza?

Posłużmy się przykładem, wykorzystując jeszcze raz fragment kodu z przykładu ze złożonością O(n). Wyobraź sobie, że teraz chciałbyś go lekko zmodyfikować. Zamiast wypisywać elementy, chcesz sprawdzać czy istnieją konkretne wartości w podanej kolekcji:

const elements = ["Element1", "Element2", "Element3"];

const checkIfExists = (searchedElement, arrayToSearch) => {
	for (const item of arrayToSearch) {
		if (item === searchedElement) {
			return true;
		}
	}
	return false;
}

console.log(checkIfExists("Element1", elements));

Patrząc na powyższy fragment, wystarczy tylko jedna iteracja pętli i znajdziemy poszukiwany element. Trafiliśmy szukaną wartość za pierwszym razem, nie oznacza to jednak, że algorytm ma złożoność O(1).

Zmieńmy teraz poszukiwaną wartość na "Element3". W tym momencie potrzeba już 3 iteracji, żeby znaleźć taki element. Jest to najgorszy przypadek dla podanych danych wyjściowych. Algorytm musiał wykonać tyle operacji, ile jest elementów w przekazanej kolekcji.

Najlepsi i najgorsi

Algorytmy jakie spotkasz na swojej drodze mogę mieć jeszcze inne oznaczenia złożoności. Dla ułatwienia, poniżej przygotowaliśmy infografikę z najpopularniejszymi z nich. Zostały przedstawione od najwolniejszej do najszybszej:

A dla tych, którzy wolą bardziej opisową formę:

• Złożoność silniowa (O(n!)): Czas wykonania algorytmu rośnie w sposób silniowy wraz z rozmiarem danych wejściowych.

• Złożoność wykładnicza (O(2^n)): Czas wykonania algorytmu rośnie wykładniczo wraz z rozmiarem danych wejściowych.

• Złożoność kwadratowa (O(n^2)): Czas wykonania algorytmu rośnie kwadratowo wraz z rozmiarem danych wejściowych.

• Złożoność liniowo-logarytmiczna (O(n log n)): Czas wykonania algorytmu rośnie w sposób liniowo-logarytmiczny wraz ze wzrostem danych wejściowych. Jest to często spotykana złożoność w algorytmach sortowania i wyszukiwania.

• Złożoność liniowa (O(n)): Czas wykonania algorytmu rośnie liniowo wraz z rozmiarem danych wejściowych.

• Złożoność logarytmiczna (O(log n)): Czas wykonania algorytmu rośnie w sposób logarytmiczny wraz ze wzrostem danych wejściowych.

• Złożoność stała (O(1)): Czas wykonania algorytmu jest niezależny od wielkości danych wejściowych.

Podsumowanie

W ramach tego wpisu przyjęliśmy pewne uproszczenia. Między innymi nie zagłębialiśmy się w matematyczne podstawy dotyczące złożoności obliczeniowej. To co zostało opisane wyżej to pigułka. Pomoże Ci lepiej zrozumieć świat algorytmów oraz zapunktować na rozmowie.