Подразделы

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

Дата и время

16/03/2025 22:56:56

Авторизация

Основы анализа алгоритмов

Эффективность алгоритмов Оценка размера входных данных Единицы измерения времени выполнения алгоритма Порядок роста Эффективность алгоритма в разных случаях

Порядок роста

При малых размерах входных данных невозможно заметить разницу во времени выполнения между эффективным и неэффективным алгоритмом. И только тогда, когда $n$ становится велико, вопросы, связанные с разной эффективностью алгоритмов, выходят на первый план и становятся понятными.

$n$	$log_2 n$	$n log_2 n$	$n^2$	$n^3$	$2^n$	$n!$
$10$	3.3	33	$10^2$	$10^3$	$10^3$	$3.6*10^6$
$10^2$	6.6	660	$10^4$	$10^6$	$1.3*10^{30}$	$9.3*10^{157}$
$10^3$	10	$10^4$	$10^6$	$10^9$	$10^{301}$	$4*10^{2567}$
$10^4$	13	$1.3*10^5$	$10^8$	$10^{12}$	$2*10^{3010}$	много

Самый малый порядок роста имеет логарифмическая функция. Причем его значение настолько мало, что программы, реализующие алгоритмы с логарифмическим количеством основных операций, будут выполняться практически мгновенно для всех диапазонов входных данных реального размера. Хотя рост зависит от основания логарифма, можно заметить, что основание логарифма меняет только множитель:
$log_a n = log_a b log_b n$ .

Поэтому можно опускать основание логарифма и записывать просто: $log n$ .

С другой стороны, с помощью алгоритмов, в которых количество выполняемых операций растет по экспоненциальному закону, можно решить лишь задачи очень малых размеров.

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

Для каждой из приведенных ниже функций определите, во сколько раз изменится ее значение при увеличении значения аргумента в четыре раза.
а) $log_2 n$
б) $sqrt n$
в) $n$
г) $n^2$
д) $n^3$
е) $2^n$