Складність алгоритмів

03. 08. 2021

Obsah článku

Кожен алгоритм має свою складність, яку можна виразити в математичних позначеннях. Цей огляд показує типову складність алгоритмів відповідно до розміру вхідних даних (тобто кількості елементів, з якими вони працюють), а також те, які типи алгоритмів підходять для якого типу завдань.

Загалом, для кожного типу проблем існує найкращий спеціалізований алгоритм. Жоден алгоритм не є універсально найкращим, і завжди потрібно знати свій контекст.

Нотація Big O

Нотація Big O використовується для класифікації алгоритмів відповідно до того, як збільшуються вимоги до часу виконання або пам'яті при збільшенні розміру вхідних даних.

На наступній діаграмі показані найбільш поширені порядки зростання алгоритмів, заданих в нотації Big O.

Нижче наведено перелік деяких з найбільш часто використовуваних нотацій Big O та порівняння їх продуктивності щодо різних розмірів вхідних даних.

Нотація Big O	Складність на 10 елементів	Складність на 100 елементів	Складність на 1000 елементів
O(1)	1	1	1
O(log N)**	3	6	9
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(2^N) ¦ 1024 ¦ 1.26e+29 ¦ 1.07e+301 ¦ ¦ ¦O(2^N)
О(Н!) ¦ 3628800 ¦ 9.3e+157 ¦ 4.02e+2567 ¦ ¦ ¦О(Н!) ¦ 3628800 ¦ 9.3e+157 ¦ 4.02e+2567 ¦ ¦ ¦О(Н!)

Складність операцій зі структурами даних

Структура даних	Доступ	Пошук	Вставка	Видалення	Коментар
Масив 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1
Стопку!
Черга!
Пов'язаний список** n n n n n n n n 1 n n n n n n n n n n n n n n n n n n n n n n n n n n n n n n n n n n
Хеш-таблиця	-	n	n	n	n
Бінарне дерево пошуку**	n	n	n	n	n
В-дерево**	log(n)	log(n)	log(n)	log(n)	log(n)
Червоно-чорне дерево**	log(n)	log(n)	log(n)	log(n)	log(n)
Дерево AVL**	log(n)	log(n)	log(n)	log(n)	log(n)
Фільтр Блума** -	1	1	-	При пошуку "хибних спрацьовувань

Складність алгоритмів сортування

Назва алгоритму ¦ Найкращий ¦ Середній ¦ Найгірший ¦ Пам'ять ¦ Стабільна?
Сортування бульбашками**
Сортування вставкою**
Сортування за вибором
Сортування купою
Об'єднати сортування**
Швидке сортування**
Сортування оболонки** ¦ n log(n) ¦залежить від послідовності ¦ n (log(n))² ¦ 1
Сортування за рахунком**
Радіксне сортування

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: