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

15

В некоторых случаях алгоритму сопоставляют несколько слож­ностей. Итоговые временные затраты сортировки массива с помо­щью сравнений складываются из затрат на сравнение и на пере­мещение элементов. Без учета типа элементов массива нельзя ска­зать, какая из операций является более дорогой. Поэтому для ал­горитмов сортировки используются две сложности: с одной сторо­ны—по числу сравнений, а с другой —по числу перемещений эле­ментов, т.е. присваиваний (:=) или обменов (<->). Если же рассмат­ривается некоторый арифметический алгоритм, то, исследовав его мультипликативную сложность, можно дополнительно интересовать­ся, в качестве уточнения, аддитивной сложностью (числом сложений и вычитаний в худшем случае) и т. д. В приложении D мы тщатель­но исследуем мультипликативную и аддитивную сложности алгорит­мов вычисления значения полинома при заданном значении аргу­мента.

Пусть некоторому алгоритму А сопоставлены две, скажем, времен­ные сложности Т'_А{п) и Т'_А\п). Например, Т'_А{п) и Т'_А\п) могут быть сложностями по разным операциям. Если операции первого и вто­рого вида предполагаются имеющими одинаковую затратность, то это еще не дает оснований считать, что сложность Т_А{п), которую мы определим, рассматривая совместно операции обоих видов, бу­дет равна Т'_А(п) + Т'_А{п), потому что максимумы этих двух видов за­трат могут достигаться на разных входах одного и того же размера. Можно только утверждать, что

Т_А{п)^Г_А{п) + Г_А\п).

Пример 1.4. Чтобы проиллюстрировать указанное обстоятельство, мы вновь обратимся к сортировке простыми вставками, которая мо­жет рассматриваться в двух вариантах \_г и 1₂: для вставки элемента x_i+1 в уже упорядоченную часть х_г,х₂, ...,x_t элементы этой упорядо­ченной части просматриваются либо в порядке x_h х_{-_ъ ..., либо в по­рядке х_г,х₂, ... В первом варианте максимум числа сравнений до­стигается тогда, когда входной массив имеет обратную к требуемой упорядоченность: х_г > х₂ > ... > х_п^ и на этом же входе достигается максимум числа обменов; имеем \(п) = Т^(п) + Т{[(п) = п{п- 1), где Т{^п),Т{^п) суть сложности по числу сравнений и обменов.

Во втором варианте максимум числа сравнений достигается, когда массив уже упорядочен так, как требуется: х_г <х₂ < ... <х_п, а макси­мум числа обменов—когда х_г > х₂ > ... > х_п. Если i > 1, то при вставке элемента x_i+1 в уже упорядоченную часть х_г, х₂,..., х_{ потребуется тем меньше обменов, чем больше потребуется сравнений. Если элемент

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

займет место с номером к, то это потребует i-k + 1 обменов. Число же сравнений равно к, если к s= i, и равно к - 1, если k = i + l. Сум­марное число сравнений и обменов равно i + 1, если к s= i, и равно i, если k = i + l. Поэтому максимум общего числа сравнений и обме­нов достигается, например, на входном массиве, имеющем обратную к требуемой упорядоченность: х_г > х₂ > ... > х_п. Легко устанавливает-

?. (п + 2)(п-1) ся, что 7]₂(п) = .

Рассматривая сложности 7] (п), 7] (п) первого и второго вариан­тов сортировки простыми вставками по общему числу сравнений и обменов, мы имеем

7\(n) = n(n-l), f_h = ⁽" ^{+ 2)}₂⁽" - ^1}, (1.3)

и, таким образом, Г] (п)/^ (п)—»2 при возрастании п.

Обладающий большей общей сложностью f_h первый вариант ал­горитма рассматривается в литературе значительно чаще второго, не в последнюю очередь из-за того, что его запись несколько проще: мы можем со всеми подробностями записать первый вариант с помощью псевдокода

for i = 2 to п do

k:=i;

while k > 0 and x_k >x_k+1 do x_k <->x_k+1; k:=k-l od od

(предполагается, что если k ^ 0, то булево выражение, имеющее вид конъюнкции

к > 0 and х_к > х_к+ъ

принимает значение 0, т. е. «ложь», даже если при этом, например, значение х_к не определено, и, следовательно, не определено значение второго члена конъюнкции).

Второй вариант будет иметь вид:

for i = 2 to n do

fc:=l;

while k<i and x_k<x_t do k:=k + l od;

f or j = i - 1 downto к do Xj^x_j+1 od od

В первом варианте используется на один оператор цикла меньше, но с точки зрения вычислительной сложности это не является пре-