ВУЗ:
Основным отличием между графиками, представленными на рис. 4.18 и 4.19, безусловно, является их общая форма. Именно
форма графика, а не его индивидуальные особенности, демонстрирует, насколько хорошо данный алгоритм будет справлять-
ся с все возрастающими объемами данных. Заметим, что общая форма графика определяется типом отображаемого выраже-
ния, а не его конкретными особенностями: все линейные выражения изображаются прямой линией, все квадратичные выраже-
ния – параболической кривой, а все логарифмические выражения порождают логарифмическую кривую, подобную пред-
ставленной на рис. 4.19. Общую форму кривой принято определять простейшим выражением, порождающим кривую данной
формы. В частности, параболическая форма обычно определяется выражением n
2
, а логарифмическая – выражением lgn.
Рис. 4.19. График зависимости времени поиска от длины списка
для алгоритма двоичного поиска
Выше было показано, что форма графика, представляющего зависимость времени выполнения алгоритма от объема
входных данных, отражает общие характеристики эффективности алгоритма. Поэтому принято классифицировать алгорит-
мы согласно форме их графиков, построенных для самого неблагоприятного случая. Способ обозначения, используемый для
определения этих классов, иногда называют тета-классами. Алгоритмы, графики которых имеют параболическую форму
(например, сортировка методом вставки), относятся к классу Θ(n
2
), алгоритмы, графики которых имеют логарифмическую
форму (например, двоичный поиск), – к классу Θ(lgn). Любой алгоритм из тета-класса Θ(lgn) по самой свой сути всегда бо-
лее эффективен, чем алгоритм из тета-класса Θ(n
2
).
Верификация программ. Вспомним, что четвертая фаза процедуры решения задачи, согласно схеме, предложенной
математиком Полиа (см. раздел 4.3), заключается в оценке точности работы программы или верификации (verification) и
определении его потенциала как инструмента для решения других задач. Важность первой части этой фазы мы проиллюст-
рируем следующим примером.
Путешественник, у которого есть золотая цепочка из семи звеньев, должен остановиться в уединенном отеле на семь
ночей. Плата за каждую проведенную в отеле ночь составляет одно звено его цепочки. Какое наименьшее число звеньев не-
обходимо разрезать, чтобы путешественник мог платить владельцу отеля одно звено каждое утро, не внося плату заранее?
Первым делом уясним себе, что нет необходимости разрезать все звенья. Если мы разрежем только второе звено, то и
первое, и второе будут отделены от остальных пяти звеньев. Следуя этому, можно прийти к решению разрезать только вто-
рое, четвертое и шестое звенья цепочки. В результате все звенья окажутся свободными, причем только три из них будут раз-
резанными (рис. 4.20). Более того, любое меньшее число разрезов оставит два звена соединенными, поэтому мы заключаем,
что правильный ответ для этой задачи – три звена.
Однако, рассмотрев задачу более внимательно, можно заметить, что если разрезать только третье звено, то получится
три фрагмента цепочки, состоящие из одного, двух и четырех звеньев (рис. 4.21). С этими фрагментами мы можем поступить
следующим образом.
Первое утро. Отдать владельцу отеля одно звено.
Второе утро. Забрать у владельца отеля одно звено и отдать ему фрагмент цепочки из двух звеньев.
Рис. 4.20. Разделение всех звеньев цепочки с помощью лишь трех разрезов
Страницы
- « первая
- ‹ предыдущая
- …
- 98
- 99
- 100
- 101
- 102
- …
- следующая ›
- последняя »
