Составители:
8
будем использовать только временную сложность. Пространственная
сложность оценивается аналогично.
Самый простой способ оценки – экспериментальный, т. е. запрограм-
мировать алгоритм и выполнить полученную программу на нескольких
задачах, оценивая время выполнения программы. Однако этот способ име-
ет ряд недостатков. Во-первых, экспериментальное программирование –
это, возможно, дорогостоящий процесс. Во-вторых, необходимо учитывать,
что на время выполнения программ влияют следующие факторы:
1) временная сложность алгоритма программы;
2) качество скомпилированного кода исполняемой программы;
3) машинные инструкции, используемые для выполнения программы.
Наличие второго и третьего факторов не позволяют применять ти-
повые единицы измерения временной сложности алгоритма (секунды,
миллисекунды и т.п.), так как можно получить самые различные оцен-
ки для одного и того же алгоритма, если использовать разных програм-
мистов (которые программируют алгоритм каждый по-своему), разные
компиляторы и разные вычислительные машины.
Существует метод, позволяющий теоретически оценить время вы-
полнения алгоритма, который и рассмотрим далее.
Часто, временная сложность алгоритма зависит от количества входных
данных. Обычно говорят, что временная сложность алгоритма имеет поря-
док T(n) от входных данных размера n. Точно определить величину T(n) на
практике представляется довольно трудно. Поэтому прибегают к асимпто-
тическим отношениям с использованием O-символики.
Например, если число тактов (действий), необходимое для работы
алгоритма, выражается как 11n
2
+ 19n·log n + 3n + 4, то это алгоритм,
для которого T(n) имеет порядок O(n
2
). Фактически, из всех слагаемых
оставляется только то, которое вносит наибольший вклад при больших
n (в этом случае остальными слагаемыми можно пренебречь), и игнори-
руется коэффициент перед ним.
Когда используют обозначение O(), имеют в виду не точное время
исполнения, а только его предел сверху, причем с точностью до посто-
янного множителя. Когда говорят, например, что алгоритму требуется
время порядка O(n
2
), имеют в виду, что время исполнения задачи рас-
тет не быстрее, чем квадрат количества элементов.
Для примера приведем числа, иллюстрирующие скорость роста для
нескольких функций, которые часто используются при оценке времен-
ной сложности алгоритмов (см. табл. 1).
Страницы
- « первая
- ‹ предыдущая
- …
- 6
- 7
- 8
- 9
- 10
- …
- следующая ›
- последняя »
