Złożoność czasowa

Przyjętą miarą złożoności czasowej jest liczba operacji podstawowych w zależności od rozmiaru wejścia. Pomiar rzeczywistego czasu zegarowego jest mało użyteczny ze względu na silną zależność od sposobu realizacji algorytmu, użytego kompilatora oraz maszyny na której algorytm wykonujemy. Dlatego w charakterze czasu wykonania rozpatruje się zwykle liczbę operacji podstawowych (dominujących). Operacjami podstawowymi mogą być na przykład: podstawienie, porównanie lub prosta operacja arytmetyczna.

Złożoność pamięciowa

Złożoność pamięciowa jest miarą ilości wykorzystanej pamięci. Jako tę ilość najczęściej przyjmuje się użytą pamięć maszyny abstrakcyjnej (na przykład liczbę komórek pamięci maszyny RAM) w funkcji rozmiaru wejścia. Możliwe jest również obliczanie rozmiaru potrzebnej pamięci fizycznej wyrażonej w bitach lub bajtach.

Porównywanie złożoności algorytmów

Porównując złożoność algorytmów bierzemy pod uwagę asymptotyczne tempo wzrostu, czyli to jak zachowuje się funkcja określająca złożoność dla odpowiednio dużych, granicznych argumentów (rozmiarów danych wejściowych) ignorując zachowanie dla małych danych. Ponadto złożoności algorytmów różniące się o stałą uważamy za takie same, co eliminuje wpływ szybkości działania komputera, na którym dany algorytm ma być wykonany, oraz wybór operacji podstawowej, która na jednym komputerze może wykonywać się błyskawicznie, na innym zaś musi być zastąpiona szeregiem instrukcji.

Asymptotyczne tempo wzrostu jest miarą określającą zachowanie wartości funkcji wraz ze wzrostem jej argumentów. Asymptotyczne tempo wzrostu opisuje jak szybko dana funkcja rośnie lub maleje, abstrahując od konkretnej postaci tych zmian. Stosowane w celu opisu złożoności obliczeniowej, czyli zależności ilości potrzebnych zasobów (np. czasu lub pamięci) od rozmiaru danych wejściowych algorytmu.

n	f(n)	f(log10(n))	f(n*log10(n))	f(n^2)	f(n^3)	f(2^n)	f(3^n)	f(n!)
1	1,00	0,00	0,00	1,00	1,00	2,00	3,00	1,00
2	2,00	0,30	0,60	4,00	8,00	4,00	9,00	2,00
3	3,00	0,48	1,43	9,00	27,00	8,00	27,00	6,00
4	4,00	0,60	2,41	16,00	64,00	16,00	81,00	24,00
5	5,00	0,70	3,49	25,00	125,00	32,00	243,00	120,00
6	6,00	0,78	4,67	36,00	216,00	64,00	729,00	720,00
7	7,00	0,85	5,92	49,00	343,00	128,00	2 187,00	5 040,00
8	8,00	0,90	7,22	64,00	512,00	256,00	6 561,00	40 320,00
9	9,00	0,95	8,59	81,00	729,00	512,00	19 683,00	362 880,00
10	10,00	1,00	10,00	100,00	1 000,00	1 024,00	59 049,00	3 628 800,00
11	11,00	1,04	11,46	121,00	1 331,00	2 048,00	177 147,00	39 916 800,00

Notacja O

(Czytaj „notacja duże O” lub „ograniczenie górne”)

Zapisujemy jako: f(n) = O(g(n))

Taki zapis oznacza, że f jest co najwyżej rzędu g, czyli istnieje taka stała c, że:

|f(n)| ≤ c · |g(n)|

Czyli funkcja g(n) jest ograniczeniem górnym dla f (n).

• Jak sprawdzić, czy f(n) = O(g(n)) ?

Upewniamy się, że
a konkretniej

Przykładowy wykres:

Notacja Ω

(Czytaj „notacja duże omega” lub „ograniczenie dolne”)

Zapisujemy jako: f(n) = Ω(g(n))

Taki zapis oznacza, że f jest co najmniej rzędu g, czyli istnieje taka stała c, że:

|f(n)| ≥ c ·| g(n)|

Czyli funkcja g(n) jest ograniczeniem dolnym dla f (n).

• Jak sprawdzić, czy f(n) = Ω(g(n)) ?

Upewniamy się, że

Przykładowy wykres:

Notacja Θ

(Czytaj „notacja kanapkowa” lub „teta”)

Zapisujemy jako: f(n) = Θ(g(n))

Taki zapis oznacza, że f jest tego samego rzędu co g, czyli istnieją takie stałe c₁ i c₂ że:

c₁ · |g(n)| ≤ |f(n)| ≤ c₂ · |g(n)|

Czyli funkcja g(n) jest ograniczeniem górnym dla f (n).

• Jak sprawdzić, czy f(n) = Θ(g(n)) ?

Upewniamy się, że
lub konkretniej

Przykładowy wykres:

Porównanie klas złożoności obliczeniowych
Klasa złożoności obliczeniowej O()	Nazwa klasy złożoności obliczeniowej	Cechy algorytmu
O(1)	Stała	działa prawie natychmiast
O(log2n)	Logarytmiczna	niesamowicie szybki
O(n)	liniowa	szybki
O(nlog2n)	liniowo-logarytmiczna	dosyć szybki
O(n^2)	kwadratowa	wolny dla dużych n
O(n^3)	sześcienna	wolny dla większych n
O(2^n), O(n!)	wykładnicza	nierealizowalny dla większych n

Zadania

Zadanie 1.

Podaj możliwie najlepsze oszacowanie następującej funkcji stosując notację O:

Funkcja

Zadanie 2.

Podaj możliwie proste oszacowanie następującej funkcji stosując notację Θ:

Funkcja

Zadanie 3.

Dla K=3, L=6 Podaj ile wynosi X. Określ jego złożoność asymptotyczną przy użyciu notacji

Zadanie 4.

Dla podanego poniżej fragmentu kodu algorytmu określ jego złożoność asymptotyczną przy użyciu notacji
:

for ( i = sum = 0; i < n; i++)

sum += a[i];

Zadanie 5.

Dla podanego poniżej fragmentu kodu algorytmu określ jego złożoność asymptotyczną przy użyciu notacji
:

for (i = 0; i < n; i++){

for(j = 1, sum = a[0]; j<=i; j++)

sum += a[j];

cout<<"suma podtablicy od 0 do "<< i <<" to <<sum<<endl;

}

ODPOWIEDZI DO ZADAŃ

Zadanie 1.

Oszacowanie

Zadanie 2.

Oszacowanie

Zadanie 3.

X = 3⁶ = 729 , O(n)

Zadanie 4.

Pętla for wykonuje się n razy a podczas każdej iteracji 2 przypisania, jedno sum drugie i (2n) oraz 2 przypisania w deklaracji

2+2n = O(n)

Zadanie 5.

Inicjalizacja zmiennej i,

Pętla zewnętrzna wykonywana jest n razy,. Za każdym razem wykonywana jest iteracja pętli wewnętrznej, instrukcja drukowania oraz przypisania zmiennych i, j, sum. Pętla wewnętrzna wykonywana jest i razy dla każdego
przy czym w każdej iteracji wykonywane są dwa przypisania: jedno zmiennej sum , drugie zmiennej j.

Liczba przypisań w całym programie wynosi więc:

---