§ 1. Затраты алгоритма для данного входа

17

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

Заметим попутно, что среди сортировок с квадратичной сложно­стью по числу сравнений чрезвычайно низкой сложностью по числу перемещений, а именно сложностью, равной п - 1, обладает сорти­ровка выбором.

В некоторых случаях к учитываемым операциям относят операции весьма разнородные, и время выполнения каждой из них считают равным 1 — пример 3.1, как и некоторые другие, даст соответству­ющую иллюстрацию. При нахождении каждой такой «смешанной» сложности затраты для каждого конкретного входа учитываются ра­зом все вместе.

Этот параграф завершим обсуждением тех предположений о вы­полнении рассматриваемых алгоритмов, которые неявно уже исполь­зовались нами. Мы исходили из того, что вычисления проводятся некоторой машиной, память которой состоит из ячеек. При этом как объем каждой ячейки, так и общее число ячеек считается бесконеч­ным, что, разумеется, является чистой абстракцией. Поместив в ячей­ку результат каких-то вычислений или считав содержимое некоторой ячейки, машина обращается еще к какой-то ячейке и т. д. Относитель­но этого процесса предполагается, что сам переход от ячейки к ячей­ке не связан с какими-либо затратами. Этот принцип лежит в основе модели вычислений, называемой РАМ («равнодоступная адресная ма­шина»—довольно неуклюжий, но принятый термин; имеется в виду машина с равнодоступными ячейками памяти)^г. Модель РАМ суще­ственно отличается в этом смысле от другой известной модели вы­числений—машины Тьюринга (МТ), где время перехода от одной ячейки ленты к другой зависит от расстояния между ячейками; при этом одна ячейка ленты МТ содержит один символ фиксированного конечного алфавита².

¹ В литературе на английском языке —RAM (random-access machine).

² Раньше в литературе по вычислительной математике и программированию сло­ во «машина» употреблялось как обозначение некоторого реального вычислительного устройства; устойчивым словосочетанием было, например, «электронная вычислитель­ ная машина» (ЭВМ). Сейчас в этом значении в основном употребляется слово «ком­ пьютер», а слово «машина» часто используется при обсуждении абстрактных вычисли­ тельных устройств: машин Тьюринга, равнодоступных адресных машин и т. д.

18 Глава 1. Сложности алгоритмов как функции числовых аргументов

Употребление слова «модель» в этом контексте подчеркивает то обстоятельство, что реальные вычислительные устройства (компью­теры) работают на тех или иных специфических принципах, но при исследовании вычислительной сложности алгоритмов этой специфи­кой можно до известного предела пренебрегать и исходить из упро­щающей системы допущений.

Далее мы будем еще неоднократно обращаться к понятию модели вычислений; всюду до главы 5 без оговорок подразумевается модель РАМ.