9. Рассчёт максимальной сложности решения задачи

9 апреля 2026 г.

Рассчёт временной сложности решения

Современный компьютер может выполнять порядка ${600\ 000\ 000 = 6 \bullet 10^8}$ операций в секунду. Для простоты и учёта амортизации округлим до ${10^8}$ операций в секунду.

Для рассчёта максимальной допустимой временной сложности алгоритма необходимо, чтобы выполнялось условие: $O(g(N)) \le S \bullet 10^8$ , где $N$ – максимальный размер входных данных, $S$ – ограничение времени выполнения решения в секундах.

Максимальная допустимая временная сложность алгоритма в зависимости от N при S = 1 секунде:

N	g(n)	Тема часто встречаемых задач с данной сложностью
\le 10 - 11	n!,\ n^6	Перестановки
\le 15 - 18	2^n\ \bullet\ n^2	Задача Коммивояжера (ДП)
\le 18 - 22	2^n\ \bullet\ n	Перебор битовых масок
\le 100	n^4	Трёхмерная задача на ДП
\le 400	n^3	Алгоритм Флойда-Уоршела
\le 2K	n^2\ \bullet\ \log_2(n)	Вложенный цикл с глубиной 2 операции на дереве
\le 10K	n^2	Вложенный цикл в цикл
\le 100K	n\ \bullet\ \sqrt{n}	Вложенный цикл и поиск всех делителей числа
\le 1M	n\ \bullet\ \log_2(n)	Быстрая сортировка или сортировка слиянием, построение дерева
\le 100M	n	Итерация по массиву
\le 10^{16}\ *	\sqrt{n}	Поиск всех делителей числа
\le 10^{18}\ *	\log_2(n)	Дихотомия
Любое **	1	Хеширование, формула

${*\ - }$ важен выбор типа данных для хранения: ${int32 <= 10^9}$ , ${int64 <= 10^{18}}$ . ${**\ - }$ при вводе/выводе более ${50K}$ элементов нужно оптимизировать ввод/вывод.

Рассчёт сложности решения по памяти

Для рассчёта максимальной пространственной сложности решения задачи необходимо, чтобы выполнялось неравенство: $O(g(N)) \le M_{bytes}$ , где $N$ – максимальный размер входных данных, $M_{bytes}$ – ограничение решения по памяти в байтах.

Максимальная допустимая сложность алгоритма по памяти в зависимости от N:

g(n)	N
g(n)	32\ Mb	64\ Mb	128\ Mb	256\ Mb	512\ Mb
n!	10	10	10	11	11
n^6	14	16	17	20	22
2^n \bullet n^2	15	16	17	18	19
2^n \bullet n	18	19	20	21	22
n^4	53	64	76	90	107
n^3	203	256	322	406	512
n^2 \bullet \log_2 n	922	1\ 275	1\ 763	2\ 441	3\ 383
n^2	2\ 896	4\ 096	5\ 792	8\ 192	11\ 585
n \bullet \sqrt{n}	41\ 285	65\ 536	104\ 031	165\ 140	262\ 144
n \bullet \log_2 (n)	446\ 923	851\ 640	1\ 626\ 242	3\ 111\ 341	5\ 963\ 203
n	8\ 388\ 608	16\ 777\ 216	33\ 554\ 432	67\ 108\ 864	134\ 217\ 728
\sqrt{n}	7.0 \bullet 10^{13}	2.8 \bullet 10^{14}	1.0 \bullet 10^{15}	4.0 \bullet 10^{15}	18.0 \bullet 10^{15}
\log_2 (n)	\infty\ (2^{8\ 388\ 608})	\infty\ (2^{16\ 777\ 216})	\infty\ (2^{33\ 554\ 432})	\infty\ (2^{67\ 108\ 864})	\infty\ (2^{134\ 217\ 728})
1	\infty	\infty	\infty	\infty	\infty

9. Рассчёт максимальной сложности решения задачи

9 апреля 2026 г.

Рассчёт временной сложности решения

Максимальная допустимая временная сложность алгоритма в зависимости от N при S = 1 секунде:

N	g(n)	Тема часто встречаемых задач с данной сложностью
\le 10 - 11	n!,\ n^6	Перестановки
\le 15 - 18	2^n\ \bullet\ n^2	Задача Коммивояжера (ДП)
\le 18 - 22	2^n\ \bullet\ n	Перебор битовых масок
\le 100	n^4	Трёхмерная задача на ДП
\le 400	n^3	Алгоритм Флойда-Уоршела
\le 2K	n^2\ \bullet\ \log_2(n)	Вложенный цикл с глубиной 2 операции на дереве
\le 10K	n^2	Вложенный цикл в цикл
\le 100K	n\ \bullet\ \sqrt{n}	Вложенный цикл и поиск всех делителей числа
\le 1M	n\ \bullet\ \log_2(n)	Быстрая сортировка или сортировка слиянием, построение дерева
\le 100M	n	Итерация по массиву
\le 10^{16}\ *	\sqrt{n}	Поиск всех делителей числа
\le 10^{18}\ *	\log_2(n)	Дихотомия
Любое **	1	Хеширование, формула

Рассчёт сложности решения по памяти

Максимальная допустимая сложность алгоритма по памяти в зависимости от N:

g(n)	N
g(n)	32\ Mb	64\ Mb	128\ Mb	256\ Mb	512\ Mb
n!	10	10	10	11	11
n^6	14	16	17	20	22
2^n \bullet n^2	15	16	17	18	19
2^n \bullet n	18	19	20	21	22
n^4	53	64	76	90	107
n^3	203	256	322	406	512
n^2 \bullet \log_2 n	922	1\ 275	1\ 763	2\ 441	3\ 383
n^2	2\ 896	4\ 096	5\ 792	8\ 192	11\ 585
n \bullet \sqrt{n}	41\ 285	65\ 536	104\ 031	165\ 140	262\ 144
n \bullet \log_2 (n)	446\ 923	851\ 640	1\ 626\ 242	3\ 111\ 341	5\ 963\ 203
n	8\ 388\ 608	16\ 777\ 216	33\ 554\ 432	67\ 108\ 864	134\ 217\ 728
\sqrt{n}	7.0 \bullet 10^{13}	2.8 \bullet 10^{14}	1.0 \bullet 10^{15}	4.0 \bullet 10^{15}	18.0 \bullet 10^{15}
\log_2 (n)	\infty\ (2^{8\ 388\ 608})	\infty\ (2^{16\ 777\ 216})	\infty\ (2^{33\ 554\ 432})	\infty\ (2^{67\ 108\ 864})	\infty\ (2^{134\ 217\ 728})
1	\infty	\infty	\infty	\infty	\infty

OpenEd

9. Рассчёт максимальной сложности решения задачи

Рассчёт временной сложности решения

Рассчёт сложности решения по памяти

OpenEd

9. Рассчёт максимальной сложности решения задачи

Рассчёт временной сложности решения

Рассчёт сложности решения по памяти