У у V V ' ' ' V

Рис. 14. Три последовательных шага сортировки фон Неймана, удлиняющих упорядоченные участки (сегменты): а) переход от семи сегментов к четы­рем; б) переход от четырех сегментов к двум; в) переход от двух сегментов к одному (массив полностью упорядочен).

то при к > 1 на следующем шаге мы будем иметь дело с к' таким, что к' <2^т-¹. В случае же сортировки фон Неймана ситуация такова, что если на каком-то шаге имеем к > 1 уже построенных сегментов и 2^т-¹ < к ^ 2^т (это соответствует тому, что [log₂ к] = т), то на сле­дующем шаге сегментов будет к' <к и 2^т-² <к' ^ 2^т-¹ (это соответ­ствует тому, что [log₂ к']=т- 1). Поэтому функция L{k) = [log₂ к], где к — текущее число построенных сегментов, убывает с каждым шагом ровно на единицу. Таким образом, число этапов слияния, или число перебросок сортируемых элементов из массива в массив, равно [log₂n]. Это позволяет утверждать следующее:

Сложность сортировки фон Неймана по числу сравнений меньше, чем n\log₂ п]; сложность по числу присваиваний равна n\log₂ п].

В самом деле, каждый этап слияния, сопровождаемый переброс­кой элементов из массива в массив, требует п присваиваний. Число сравнений при каждом слиянии по крайней мере на единицу мень­ше, чем длина получаемого упорядоченного сегмента: известно, что число тех сравнений, которые априори могут потребоваться для слия­ния двух упорядоченных массивов, содержащих соответственно кит элементов, к^т, лежит в диапазоне от к до к + т - 1 (обе указанные границы достижимы).

Вновь обращаясь к примеру 3.1, мы видим, что, основываясь на сортировке фон Неймана, можно получить алгоритм построения вы­пуклой оболочки данных п точек координатной плоскости, имеющий сложность O(nlogn) в худшем случае по общему числу операций.

Некоторое различие между примером 9.1 и примерами 9.2, 9.3 со­стоит в том, что в примере 9.1 мы определяли L как функцию самого входа алгоритма и из полученной оценки для затрат выводили оцен­ку для сложности (переходили от входа как такового к его размеру), а в 9.2, 9.3 мы изначально рассматривали L как функцию размера.

82Глава 3. Оценивание числа шагов (итераций) алгоритма

В этих двух последних примерах значения функции L возникали из сравнений размера n с элементами некоторой последовательности s_k, k = 0,1, ... (в обоих случаях было s_k = 2^k). В примере 9.2 удобно бы­ло считать, что L{n) = k, если s_k-₁^n<s_k, а в примере 9.3 — если s_k-₁ <n^s_k.

Типичный итерационный алгоритм содержит цикл, в котором на­бор v начальных величин преобразуется в набор v', затем v преобра­зуется в v"и т. д. Функция L, которую мы подбираем, должна прини­мать неотрицательные значения и быть определенной либо на самих наборах величин, либо на их размерах; в обоих случаях функция долж­на убывать по ходу выполнения алгоритма:

L{v)>L{v')>L{v")> ...

в первом случае, или

L(||v||)>L(||v^/||)>L(||v^//||)>...

во втором. Значение L(v) или соответственно L(||v||) дает верхнюю границу для числа шагов цикла.^г