Подразделы

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

Дата и время

27/05/2026 23:55:11

Авторизация

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

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

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

При малых размерах входных данных невозможно
заметить разницу во времени выполнения между эффективным и неэффективным
алгоритмом. И только тогда, когда `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`.

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

---

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

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

Назад

Подразделы

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

Дата и время

Авторизация

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

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