Złożoność algorytmów

03. 08. 2021

Obsah článku

Każdy algorytm ma swoją własną złożoność, którą można wyrazić w notacji matematycznej. W tym zestawieniu pokazano typową złożoność algorytmów w zależności od wielkości danych wejściowych (tj. liczby elementów, z którymi pracują) oraz to, jakie typy algorytmów są odpowiednie do danego typu zadań.

Ogólnie rzecz biorąc, dla każdego typu problemu istnieje najlepszy wyspecjalizowany algorytm. Żaden algorytm nie jest uniwersalnie najlepszy i zawsze trzeba znać kontekst.

Notacja Big O

Notacja Big O służy do klasyfikowania algorytmów na podstawie tego, jak ich czas działania lub wymagania pamięciowe rosną wraz ze wzrostem rozmiaru danych wejściowych.

Na poniższym wykresie przedstawiono najczęściej spotykane rzędy wzrostu algorytmów określonych w notacji Big O.

Poniżej znajduje się lista kilku najczęściej używanych notacji Big O oraz porównanie ich wydajności w odniesieniu do różnych rozmiarów danych wejściowych.

Notacja Big O	Złożoność dla 10 elementów	Złożoność dla 100 elementów	Złożoność dla 1000 elementów
O(1)	1	1	1
O(log N)	3	6	9
O(N)	10	100	1000
O(N log N)	30	600	9000
O(N^2)	100	10000	1000000
O(2^N)	1024	1.26e+29	1.07e+301
O(N!)		3628800	9.3e+157

Złożoność operacji na strukturach danych

Struktura danych	Dostęp	Wyszukiwanie	Wstawianie	Usuwanie	Komentarz
1	n	n	n	n
Stack	n	n	n	1	1
Queue	n	n	n	1
n	n	1	n	1	n
	n	n	n	n	W przypadku doskonałej funkcji skrótu złożoność wynosi O(1).
Binarne drzewo poszukiwań	n	n	n	W przypadku zrównoważonego drzewa złożoność wyniesie O(log(n)).
B-Drzewo	log(n)	log(n)	log(n)	log(n)	log(n)
Drzewo czerwono-czarne	log(n)	log(n)	log(n)	log(n)	log(n)
AVL Tree	log(n)	log(n)	log(n)	log(n)	log(n)
	1	1	-	Przy wyszukiwaniu `fałszywych pozytywów`

Złożoność algorytmów sortowania

Nazwa algorytmu	Najlepszy	Średni	Najgorszy	Pamięć	Stabilny?	Komentarz
Sortowanie bąbelkowe	n	n²	n²	1	Tak
Insertion sort	n	n²	n²	1
	n²	n²	n²	1
Heap sort	n log(n)	n log(n)	n log(n)	1		Nie
Merge sort	n log(n)	n log(n)	n log(n)	n	Tak
Quick sort	n log(n)	n log(n)	n²	log(n)	Nie	Quicksort jest zwykle wykonywany z złożonością stosu O(log(n)).
n log(n)	zależy od sekwencji	n (log(n))²	1		Nie
n + r	n + r	n + r	n + r	n + r	Tak	r - największa liczba w tablicy
n * k	n * k	n * k	n + k	Tak	k - długość najdłuższego klucza

Jan Barášek Více o autorovi

Autor článku pracuje jako seniorní vývojář a software architekt v Praze. Navrhuje a spravuje velké webové aplikace, které znáte a používáte. Od roku 2009 nabral bohaté zkušenosti, které tímto webem předává dál.

Rád vám pomůžu: