logo
tsvpis

1.2. Справочный материал. Сравнение скорости роста основных функций

Формула Стирлинга:

.

Пример. Сравним скорости роста функций и

Решение. 1) Прологарифмируем обе функции по основанию 2, получим:

n! и .

2) Используя формулу Стирлинга: , получим:

и

Сократим на :

и

3) Так как значение некоторых частей выражений много меньше значения других, то их можно не рассматривать:

и log n.

т.к. nloge << nlogn.

Получаем: nlogn >> logn

n >> 1

Следовательно, 2n! >>

Функция 2n! растет быстрее, чем

Определение. Будем говорить, что задача решаема за полиномиальное время, если для неё существует некоторый алгоритм с трудоёмкостью T(n) ≤ p(n), где p – некоторый многочлен.

Примерами задач, решаемых за полиномиальное время, являются:

  1. сортировки;

  2. решение СЛАУ (метод Гаусса).

Чем же хороши задачи, решаемые за полиномиальное время?

Для ответа на этот вопрос рассмотрим две таблицы:

Таблица 1.1. – Время, необходимое для вычисления на машине

с быстродействием 106 опер/сек

n

T(n)

10

20

30

50

100

n

10-5 сек

2·10-5 сек

3·10-5 сек

5·10-5 сек

10-4 сек

n logn

3·10-5 сек

8·10-5 сек

15·10-5 сек

3·10-4 сек

7·10-4 сек

n2

10-4 сек

4·10-5 сек

9·10-5 сек

2·5·10-3 сек

10-2 сек

n5

10-1 сек

3·2 сек

10-5 сек

5.2 мин

≈ 3 часа

2n

10-3 сек

1 сек

18 мин

36 лет

3·1016 лет

Таблица 1.2. – Объем доступной решаемой задачи за одно

и то же время (таблица прогресса)

машины

T(n)

Современные

В 10 раз быстрее современных

30

n

k

10k

100k

n logn

k

n2

k

10k

n3

k

n5

k

Неполиномиальные алгоритмы

2n

k

3.3 + k

6.6 + k

n!

k

Комментарии к таблице прогресса. При повышении производительности машины в несколько раз для алгоритма с полиномиальной производительностью объем доступной решаемой задачи повышается в разы, а у неполиномиальных алгоритмов увеличивается «на сколько-то», то есть НЕ в разы.

Домашнее задание №1

Отсортировать по скорости роста, начиная с наименьшей: