Złożoność obliczeniowa algorytmu

---

Pojęcie złożoności obliczeniowej

Złożoność obliczeniowa algorytmu określa, jak wydajny jest algorytm, ile musi on wykonać operacji w zależności ilości danych oraz ile potrzebuje do tego pamięci. Często zdarza się, że dany problem algorytmiczny można rozwiązać kilkoma metodami, czyli algorytmami o różnej złożoności obliczeniowej.

Złożoność obliczeniową dzielimy na złożoność pamięciową oraz złożoność czasową.

Złożoność pamięciowa algorytmu wyznaczana jest na podstawie ilości potrzebnej pamięci do rozwiązania problemu. Na przykład, jeśli dla danych wejściowych złożonych z n elementów nasz algorytm będzie zużywał dwa razy tyle pamięci, ile zużyłby na te n elementów, to mówimy, że złożoność pamięciowa wynosi 2n, natomiast, jeżeli do rozwiązania problemu potrzebuje stałą niewielką ilość komórek pamięci, to mówimy, że taka złożoność jest stała. Oczywiście, im mniejsza złożoność, tym lepiej.

Złożoność obliczeniowa określa, ile głównych operacji musi wykonać algorytm, aby rozwiązać problem dla n elementów będących danymi wejściowymi. Elementami tymi mogą być liczby, znaki itd. Główną operacją może być porównywanie elementów i ich przestawienie (np. w algorytmach sortujących), dodawanie, mnożenie itp. Załóżmy, że dla n liczb nasz algorytm będzie wykonywał 2n przestawień oraz 3n + 10 mnożeń co daje 5n + 10 operacji. Stwórzmy teraz funkcję, której argumentem będzie liczba danych wejściowych, a jej wartością liczba operacji:$$f(n)=5n+10.$$Odpowiedzmy sobie teraz na pytanie, co to jest za funkcja? Oczywiście liniowa, zatem mówimy, że ten algorytm ma złożoność liniową, a notacja, której używa się w zapisie złożoności algorytmów, wygląda następująco:$$O(klasa\ funkcji\ określającej\ złożoność).$$Powyższa notacja ma nazwę notacja O.

Klasa funkcji najprościej mówiąc, to rodzaj funkcji, jaką otrzymamy po wyznaczeniu liczby operacji wykonywanych przez analizowany algorytm w najgorszym przypadku (w pesymistycznej sytuacji).

Rodzaje złożoności obliczeniowych (rodzaje klas funkcji)

Złożoność stała O(1)

Złożoność stała algorytmu jest w sytuacji, gdy dany problem rozwiązywany jest w jednym lub kilku krokach bez względu na liczbę danych wejściowych np.:

• Dla zadanej liczby wierzchołków wielokąta wypukłego, określenie liczby przekątnych. W tej sytuacji liczbę n wystarczy podstawić do wzoru na liczbę przekątnych: $$L=\frac{n\cdot (n-3)}{2}$$
• Wyznaczenie wartości znajdującej się w komórce tablicy o indeksie i

Złożoność logarytmiczna O(log n)

Algorytmy realizujące takie podejście są bardzo wydajne. Na przykład dla miliarda elementów danych algorytm ten potrzebuje około 30 operacji, aby rozwiązać problem. Domyślną podstawą logarytmu jest liczba 2, więc $$log_21000000000 \approx 30.$$

Przykładowe algorytmy o złożoności obliczeniowej O(log n)

• Wyszukiwanie binarne

Złożoność liniowa O(n)

Złożoność liniowa algorytmu jest w momencie, gdy dla danych wejściowych o rozmiarze n liczba operacji w zależności od n elementów będzie wyrażona funkcją liniową:$$f(n)=an+b$$Złożoność taką najczęściej poznasz, gdy program analizujący dane będzie składał się z jednej pętli przechodzącej przez wszystkie elementy (lub prawie wszystkie) danych wejściowych tylko raz lub stalą ilość razy np.

Przykładowe programy ze złożonością obliczeniową O(n)

//algorytm.edu.pl
//program o złożoności liniowej
#include<iostream>
using namespace std;

int main()
{
	int n;
	cin>>n;
	
	int *tab = new int [n];
	
	//dane przechowywane są w tablicy o wielkości n, zatem złożoność pamięciowa wynosi O(n)
	for(int i=0;i<n;i++) //pętla odpowiedzialna za wczytanie liczb do tablicy
		cin>>tab[i]; 
	
	//jest tylko jedna pętla analizująca dane, która wykona n - 1 operacji
	//zatem f(n) = n - 1, czyli złożoność obliczeniowa wynosi O(n)
	for(int i=1;i<n;i++) 
	{
		//operacje na danych np. tab[i] = (tab[i-1]*tab[i])%100000;
	}
	
	return 0;
}

//algorytm.edu.pl
//program o złożoności liniowej
#include<iostream>
using namespace std;

int main()
{
	int n, cnt = 0;
	cin>>n;
	
	int *tab = new int [n];
	
	//dane przechowywane są w tablicy o wielkości n, zatem złożoność pamięciowa wynosi O(n)
	for(int i=0;i<n;i++) //pętla odpowiedzialna za wczytanie liczb do tablicy
		cin>>tab[i]; 
	
	//jest tylko jedna pętla analizująca dane, która wykona n/2 operacji
	//zatem f(n) = n/2, czyli złożoność obliczeniowa wynosi O(n)
	for(int i=1;i<n/2;i++) 
	{
		//operacje na danych np. if(tab[i] == tab[n-1-i]) ++cnt;
	}
	
	return 0;
}

Przykładowe algorytmy o złożoności obliczeniowej O(n)

• Dla n liczb podanych na wejściu wyznacz ile jest takich samych jak ostatnia wczytana. Wystarczy, że jeden raz przeanalizujemy wszystkie liczby, aby wyznaczyć wynik.
• Sprawdź, czy podany ciąg znaków jest palindromem.
• Wyznaczenie lidera w zbiorze.

Złożoność O(n log n)

Tego typu algorytmy są nieco wolniejsze od algorytmów o złożoności liniowej, ale nadal bardzo wydajne. Np. dla miliona elementów danych wejściowych, algorytm wykona około $$1000000\cdot log_21000000\approx 20 000 000$$operacji.

Przykładowe algorytmy o liniowo logarytmicznej złożoności obliczeniowej O(n log n)

• Sortowanie przez scalanie,
• w wielu algorytmach wykorzystujących metodę dziel i zwyciężaj

Złożoność kwadratowa O(n²)

Złożoność kwadratowa algorytmu jest w sytuacji, gdy dla danych wejściowych o rozmiarze n liczba operacji w zależności od liczby elementów będzie będzie wyrażona wzorem funkcji kwadratowej:$$f(n)=an^2+bn+c$$Złożoność taką najczęściej poznasz, gdy program analizujący dane będzie składał się z dwóch pętli zagnieżdżonych (pętla w pętli), a każda z nich będzie miała liniową złożoność.

Przykładowy program ze złożonością obliczeniową O(n²)

//algorytm.edu.pl
//program o złożoności kwadratowej
//Problem: wyznaczenie maksymalnej sumy dwóch liczb
#include<iostream>
using namespace std;

int main()
{
	int n, Max;
	cin>>n;
	
	int *tab = new int [n];
	
	//dane przechowywane są w tablicy o wielkości n, zatem złożoność pamięciowa wynosi O(n)
	for(int i=0;i<n;i++) //pętla odpowiedzialna za wczytanie liczb do tablicy
		cin>>tab[i]; 
	
	Max = tab[0]+tab[1];
	
	//zauważ, że pętla zewnętrzna wykona n operacji oraz tyle samo pętla wewnętrzna
	//zatem f(n) = n*n, czyli złożoność obliczeniowa wynosi O(n^2)
	for(int i=0;i<n;i++) 
	{
		for(int j=0;j<n;j++) 
		{
			if(i!=j)
				if(tab[i]+tab[j] > Max) Max = tab[i]+tab[j];
		}
	}
	cout<<Max;
	return 0;
}

Przykładowe algorytmy o złożoności obliczeniowej O(n²)

• Sortowanie bąbelkowe.
• Sortowanie przez wstawianie.
• Większość algorytmów z podejściem dynamicznym.

Złożoność wielomianowa np. O(n^k)

Złożoność wielomianowa algorytmu jest w sytuacji, gdy funkcja określająca liczbę operacji w zależności od liczby danych wejściowych jest stopnia k. Zauważ, że jeśli przykładowo algorytm jest złożoności obliczeniowej rzędu O(n³), to już dla 100 elementów wejściowych musi on wykonać około 100³ = 1000 000 operacji. Dla większej dawki danych może okazać się, że czas obliczeń będzie zbyt długi.

Przykładowy program ze złożonością obliczeniową O(n³)

//algorytm.edu.pl
//program o złożoności kwadratowej
//Problem: wyznaczenie maksymalnej sumy trzech liczb
#include<iostream>
using namespace std;

int main()
{
	int n, Max;
	cin>>n;
	
	int *tab = new int [n];
	
	//dane przechowywane są w tablicy o wielkości n, zatem złożoność pamięciowa wynosi O(n)
	for(int i=0;i<n;i++) //pętla odpowiedzialna za wczytanie liczb do tablicy
		cin>>tab[i]; 
	
	Max = tab[0]+tab[1];
	
	//zauważ, że każda z pętli wykona po n operacji
	//zatem f(n) = n*n*n, czyli złożoność obliczeniowa wynosi O(n^3)
	for(int i=0;i<n;i++) 
	{
		for(int j=0;j<n;j++) 
		{
			for(int k=0;k<n;k++)
			if(i!=j && j!=k && i!=k)
				if(tab[i]+tab[j]+tab[k] > Max) Max = tab[i]+tab[j];
		}
	}
	cout<<Max;
	return 0;
}

Złożoność n-silnia O(n!)

Algorytmy, które mają taką złożoność są bardzo wolne. Już dla niewielkiej ilości danych algorytm będzie wykonywał ogromną ilość operacji.

Przykładowe algorytmy o złożoności obliczeniowej O(n!)

• Wypisanie wszystkich permutacji danego zbioru.

Złożoność wykładnicza O(2ⁿ)

Algorytmy, które mają złożoność wykładniczą są bardzo nieefektywne i poradzą sobie z małą ilością danych wejściowych. Na przykład dla n = 30, algorytm musi wykonać około 2³⁰, co daje około miliarda operacji. Tego typu algorytmy czasami stosuje się do sprawdzenia poprawności właściwego algorytmu, ale tylko dla niewielkiej dawki danych.

Przykładowe algorytmy o złożoności obliczeniowej O(2ⁿ)

• Wypisanie wszystkich podzbiorów danego zbioru.

Podsumowanie

Im mniejsza złożoność algorytmu, tym jest on bardziej wydajny. Poniżej wypisane są złożoności od najwydajniejszej do najwolniejszej oraz szacowana liczba operacji, którą algorytm wykona dla 100 elementów:

1. O(1) - stała (od jednego do kilku operacji),
2. O(log n) - logarytmiczna (7 operacji),
3. O(n) - liniowa (100 operacji),
4. O(n log n) - n razy logarytm z n (700 operacji),
5. O(n²) - kwadratowa (10 000 operacji),
6. O(n³) - sześcienna (1000 000 operacji),
7. O(n!) - n silnia (1*2*3*4*...*100 operacji),
8. O(2ⁿ) - wykładnicza (2¹⁰⁰ operacji).