У у 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 (n log n) в худшем случае по общему числу операций.

Некоторое различие между примером 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 ||) дает верхнюю границу для числа шагов цикла. ^г

Заметим попутно, что, исходя из установленной в примере 9.2 сложности бинарного поиска, мы сразу можем получить верхнюю оценку

T _B(n)^(n -l)riog₂ n l (9.14)

для сложности по числу сравнений сортировки бинарными вставка­ми; мы используем для обозначения этой сортировки букву B, от английского слова binary—бинарный. По числу перемещений слож­ность этой сортировки квадратична, здесь эта сортировка уступает сортировке фон Неймана. Пространственную сложность сортировки бинарными вставками можно считать равной нулю (все делается на том же месте), а для сортировки фон Неймана эта сложность есть n.

Пример 9.4. Число итераций численных алгоритмов тоже часто оценивают сравнением размеров данных, соответствующих текущим итерациям, с элементами последовательности, которая может иметь, например, вид qn или q ² n (q < 1), n = 0,1,..., и т.д. Этим способом

¹ Такую функцию можно назвать функцией Ляпунова цикла, подразумевая аналогию с функцией, убывающей вдоль решения обыкновенного дифференциального уравнения (аналогия принадлежит С.С.Лаврову, см. [24, разд. 3.1.3]). Это не единственная ана­логия между дифференциальными уравнениями и циклическими алгоритмами и про­граммами. Например, понятие первого интеграла, или закона сохранения, сопостави­мо с понятием инварианта цикла и т.д.

§ 10. Качество оценок

получаются оценки числа итераций для классических методов (ал­горитмов) приближенного решения уравнений. Вспомним две такие оценки.

Пусть корень уравнения /(х) = 0 разыскивается на отрезке [а,Ъ], на котором функция /(х) непрерывна, /(а)/(Ь) «SO. Ошибка не долж­на превышать данного е > 0. При е^О и фиксированных f(x),a,b число итераций метода делений пополам есть

log,- + 0(1). (9.15)

Метод же Ньютона (касательных) требует

О flog log -) (9.16)

s

итераций при соблюдении ограничений на функцию /(х), обеспечи­вающих сходимость метода.

Дата добавления: 2014-01-11