Подразделы

Другие разделы

Дата и время

09/04/2025 21:48:44

Авторизация

Математические основы анализа алгоритмов

Асимптотические обозначения Основные классы эффективности Индукция и инвариант Нижние границы эффективности Тривиальная нижняя граница Информационно-теоретическая нижняя граница

Основные классы эффективности

Класс	Название
1	Константа
$log n$	Логарифмическая
$sqrt n$	-
$n$	Линейная
$n log n$	-
$n sqrt n$	-
$n^2$	Квадратичная
$n^3$	Кубическая
$2^n$	Экспоненциальная
$n!$	Факториальная
$n^n$	-

Обычно значения постоянных множителей никто не указывает. А это означает, что не исключена возможность, когда для входных данных реального размера, алгоритм, относящийся к худшему классу эффективности, будет работать быстрее, чем алгоритм, относящийся к лучшему классу эффективности. Например, если время выполнения одного алгоритма изменяется по закону $n^3$ , а другого – по закону $10^6 n^2$ , кубический алгоритм будет работать быстрее при условии, что $n$ не превышает $10^6$ .

Задания для практики

Расположите перечисленные ниже функции в соответствии с их порядком роста (от самого меньшего к самому большему).

$(n-2)!$ , $5 "lg" (n+100)^{10}$ , $2^{2n}$ , $0.001n^4+3n^3+1$ , $ln^2 n$ , $root^3 n$ , $3^n$