Przeczytaj

Jak zdefiniować złożoność obliczeniową?

Złożoność obliczeniowa algorytmu pozwala określić ilość zasobów komputerowych niezbędnych do wykonania czynności opisanych w algorytmie w zależności od rozmiaru danych wejściowych.

Wyróżnia się złożoność:

czasowązłożoność czasowaczasową;
pamięciowąpamięciowa złożoność obliczeniowapamięciową.

Pierwsza z nich odnosi się do liczby wykonywanych operacji i jest niezależna od komputera oraz języka programowania. Natomiast druga odnosi się do rozmiaru wykorzystywanej pamięci.

Załóżmy, że napisaliśmy program, który przyjmuje od użytkownika $n$ słów, a następnie modyfikuje w pewien sposób wszystkie otrzymane wyrazy i wypisuje ostateczny rezultat przekształceń.

Na każdym słowie wykonywana jest pewna liczba operacji, a zatem szybkość działania programu zależy głównie od rozmiaru danych wejściowych. Opiszmy liczbę wykonywanych operacji. Posłużymy się w tym celu pewną funkcją $f$ . Przyjmijmy, że ma ona następującą postać:

$f(n)=n^2+n+10$

Dla dużych argumentów wartość $n^2$ jest o wiele większa niż $n + 10$ . Wynika z tego, że wartość funkcji $f$ zależy głównie od składnika $n^2$ .

R1LfY8ftdr8mj1

Ilustracja przedstawia układ współrzędnych z poziomą osią od minus dwóch do dwudziestu czterech oraz z pionową osią od zera do sześciuset z podziałką co 50. Na płaszczyźnie narysowano dwa wykresy o bardzo zbliżonym kształcie. Obie funkcje są rosnące, a ich wykresy są łukowate z wybrzuszeniem w prawą dolną stronę. Wykres zaznaczony na zielono to wykres funkcji opisanej wzorem n2+n+10. Zaczyna się on punkcie o współrzędnych (0;10) i jest wyżej położony od drugiego, czerwonego wykresu ilustrującego funkcję n2, którego początek znajduje się w punkcie (0;0) — Źródło: Contentplus.pl Sp. z o.o., licencja: CC BY-SA 3.0.

Aby przedstawić powyższy wniosek w sposób matematyczny, posłużymy się notacją duże Onotacja duże Onotacją duże O:

$f(n) = O(n^2)$

W taki właśnie sposób wyznaczyliśmy złożoność czasową przykładowego algorytmu; jest to złożoność kwadratowa.

Ważne!

Liczba operacji wykonywanych przez program może być zależna nie tylko od wielkości danych wejściowych, ale także od nich samych. W takiej sytuacji podczas wyznaczania złożoności obliczeniowej bierzemy pod uwagę najbardziej pesymistyczny przypadek (zakładamy, że realizacja algorytmu pochłonie największą ilość zasobów systemu komputerowego), co znaczy, że dla określania złożoności obliczeniowej będziemy używać złożoności pesymistycznejzłożoność pesymistycznazłożoności pesymistycznej.

Dla dokładniejszej analizy złożoności uwzględniana jest również złożoność oczekiwanazłożoność oczekiwanazłożoność oczekiwana – istnieje wiele przypadków, w których porównywane algorytmy mają tę samą złożoność pesymistyczną, jednak w przypadku średnim nie działają tak samo szybko. Wyróżniamy również złożoność optymistycznązłożoność optymistycznazłożoność optymistyczną, która określa złożoność dla najlepszego przypadku danych. W praktyce jednak często nie jest ona brana pod uwagę.

Operacje dominujące

Określając czasową złożoność obliczeniową, bierzemy pod uwagę tzw. operacje dominująceoperacje dominująceoperacje dominujące. Są to operacje charakterystyczne dla danego algorytmu, a więc mające największy wpływ na czas potrzebny do wykonania algorytmu. Przeanalizujmy przykładowy pseudokod prostego programu:

n ← wprowadź dodatnią liczbę całkowitą
suma ← 0
i ← 1
j ← 1

dopóki i <= n wykonuj:
	suma ← suma + i
	i ← i + 1

dopóki j <= n wykonuj:
	suma ← suma + j
	j ← j + 2

wypisz(suma)

Program ten wykonuje m.in. operacje odczytu i zapisu danych oraz dodawania. O czasie działania programu decyduje jednak tak naprawdę liczba wykonywanych dodawań. Jeżeli program wykona ich ponad milion, to czas potrzebny na zapis czy odczyt danych staje się mało istotny. Operacje dodawania są zatem operacjami dominującymi w przedstawionym algorytmie.

Zastanówmy się nad kolejnym przykładem:

a ← 5
b ← 10
c ← a + b

wypisz(c)

W powyższym algorytmie nie ma operacji dominujących, czyli takich, które zajmowałyby większość czasu potrzebnego do wykonania w zależności od danych wejściowych. Nasz program zawsze wykona niezmienną liczbę operacji.

Przeanalizujmy jeszcze jeden przykład:

n ← wprowadź dodatnią liczbę całkowitą

jeżeli n parzyste:
	wypisz(n / 2)

w przeciwnym razie:
	i ← 0
	suma ← 0

	dopóki i < n wykonuj: 
		suma ← suma + 2 * i
		i ← i + 1
		
	wypisz(suma)

Ten z kolei program może być wykonywany przez różny czas w zależności od tego, jaką wartość będzie miała zmienna n. W takiej sytuacji zawsze bierzemy pod uwagę najbardziej pesymistyczny przypadek. Operacjami dominującymi są więc:

suma ← suma + 2 * i oraz i ← i + 1.

Słownik

efektywność algorytmu

praktyczne zastosowanie algorytmu w programie; miara tego, jak bardzo korzystna jest wybrana metoda

notacja duże O

miara określająca, w jaki sposób rośnie wartość funkcji wraz ze zwiększaniem jej argumentów; służy do wyznaczania górnych granic asymptotycznych

operacje dominujące

operacje charakterystyczne dla danego algorytmu, na ogół zajmujące w nim najwięcej czasu

pamięciowa złożoność obliczeniowa

ilość pamięci potrzebnej do wykonania zadania, wyrażona jako funkcja ilości danych

rząd złożoności

właściwość służąca do opisywania czasu działania algorytmu

złożoność czasowa

ilość czasu potrzebnego do wykonania zadania, wyrażona jako funkcja ilości danych

złożoność obliczeniowa

ilość zasobów komputerowych potrzebnych do wykonania zadania

złożoność oczekiwana

inaczej złożoność średnia; ilość zasobów potrzebna do zrealizowania zadania dla statystycznie oczekiwanych danych; zapisywana za pomocą notacji theta – $Θ$

złożoność optymistyczna

ilość zasobów potrzebna programowi do zrealizowania zadania dla najkorzystniejszego przypadku danych; zapisywana za pomocą notacji „małe O” – $ο$

złożoność pesymistyczna

ilość zasobów potrzebna do zrealizowania zadania w przypadku najgorszych danych; zapisywana za pomocą notacji „duże O” – $O$

Wprowadzenie

Prezentacja multimedialna

Jak zdefiniować złożoność obliczeniową?

Operacje dominujące

Słownik