Сложность в среднем

Задачи

1.Для любого neZ выполнено n = I ⁿ ₂ I + Гⁿ ₂1, для любого aеЖ выполнено \a]=-[-a\.

2.Для любых k, n GN+, k > 1, выполнено Llog_k n\ + 1 = [log_k(n + 1)1.

Указание. Пусть mеN+ таково, что k^m-¹ Цn<k^m, тогда k^m-¹ <n + 1Цk^m. Прологарифмировать по основанию k обе системы неравенств.

3.Предположим, что в нашем распоряжении нет операции обмена
a <—>b и мы заменяем ее тремя присваиваниями:

c:=a; a:=b; b:=c;

чему в этом случае равны сложности первого и второго варианта сор­тировки простыми вставками по суммарному числу сравнений и при­сваиваний?

4.Пусть полином f(n) = a_mn^m + ... + a₁n + a₀ имеет ненулевой
старший коэффициент a_m. Тогда

а) f(n) = O(n^k)<=>k:?m,

б) f(n) = n(n^k)<=>k^m,

в) f(n) = 6(n^k)<=>k = m, при k = m также выполнено f(n)~a_mn^m.

Подробнее об аддитивных цепочках см. в [19, разд. 4.6.3].

Задачи

5.Пусть Р(п)—количество простых множителей целого числа п > 1 с учетом кратности. Имеет место точная оценка Р{п) = О (log п).

6.(Продолжение предыдущей задачи.) Пусть

Р*(т)= шах Р(п),

т = 2,3, ... Верно ли, что P*(m) = 6(m)?

7.Указать все вещественные значения 5, при которых справедлива
оценка

а) T_TD(n) = 0(.n⁵),

б) Г_тп(п) = П(п⁵),

в) r_TD(n) = 6(n⁵),

где T_TD(n)—сложность алгоритма пробных делений (пример 1.2).

8.Железнодорожный сортировочный узел устроен так, как пока­
зано на рис. 6. На правой стороне собрано некоторое число вагонов

МИМО

вСЗСТИ»

тупик

Рис. 6. Сортировочный узел.

двух типов (на рис. 6—черные и белые), по п штук каждого типа. Ту­пик может вместить все 2п вагонов. Требуется, пользуясь тремя сорти­ровочными операциями В, ИЗ, МИМО, собрать вагоны на левой сто­роне так, чтобы типы вагонов чередовались. Указать такой алгоритм решения этой задачи, сложность которого по числу сортировочных операций при рассмотрении п в качестве размера входа равнялась бы Зп-1.

9.Хорошо известно, что мультипликативная сложность метода Гаусса решения системы п линейных уравнений с п неизвестными допускает оценки

1) 0(п³), 2)|п³+0(п²), 3) в(п³).

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

а) Из какой оценки (указать номер) следуют две остальные?

б) Можно ли из приведенных оценок выбрать такую, которая яв­
ляется следствием любой из остальных?

в) Является ли оценка П(п³) следствием какой-либо из оценок 1,
2, 3?

10.Для сложности Tq_S (п) быстрой сортировки выполняется оценка
T_QS(n) = в(п²). (Обозначение QS происходит от английского названия
быстрой сортировки —quick sort.)

Указание. Оценка T_QS(n) = fi(n²) устанавливается предъявлением приме­ра. Неравенство T_QS(n)<n² можно доказать индукцией по п, используя то, что при фиксированном neN⁺ квадратичная функция (т- I)² + (п- т)² от т принимает на отрезке [1, п] свое максимальное значение в одном из концов этого отрезка.

11.Алгоритм, использующий только аддитивные операции и срав­
нения целых чисел для проверки того, является ли данное целое по­
ложительное пточным квадратом, может быть основан на вычисле­
нии последовательности значений 1,1 + 3,1 + 3 + 5, ... до появления
в ней первого большего или равного пэлемента. Сложность по числу
аддитивных операций и операций сравнения этого алгоритма (назо­
вем его sq_x) допускает оценку 6(л/п). Сохранится ли эта оценка, если
дополнительно использовать операцию нахождения целой части по­
ловины числа (считается, что затратность этой операции такая же,
как у аддитивных операций) для того, чтобы предварительно выяс­
нять, на какую максимальную степень двойки — четную или нечет­
ную—делится п (алгоритм sq₂)?

12.(Продолжение предыдущей задачи.) Пусть T_sqi(n), T_sq2(n) —
сложности, соответственно, первого и второго вариантов рассмотрен­
ного алгоритма и

Т*(т)= max T_sa(n), Г*(m) = max T_sa (n),

m = 2,3, ...

а) Как связаны значения функций T_s*_qi(m) и T_s*₂(m)?

б) Имеются ли среди оценок 6(m), O(logm), в(2^т/2), 0(2^т) такие,
которые верны для T_s*₂(m), и если да, то какие именно?

13.Изменим в алгоритме Грэхема (пример 3.1) этап удаления
вдавленных вершин: будем обходить — возможно, многократно —
против часовой стрелки вершины построенной несамопересекающей-
ся ломаной и удалять вдавленные вершины до тех пор, пока при
очередном обходе не окажется безуспешной попытка найти хотя бы

Задачи

одну вдавленную вершину. Сложность этого варианта рассматривае­мого этапа алгоритма Грэхема есть Г2(п²), где п— начальное число вершин ломаной (в то время как сложность этого этапа в алгоритме Грэхема есть 0(п)).

14.Рассмотрим в главных чертах алгоритм Шеймоса—Хоя¹ по­строения пересечения Р nQ двух выпуклых многоугольников Р и Q содержащих соответственно Zи т вершин. Считаем, что многоуголь­ники задаются массивами P₁,P₂,...,Pi и Qi,Q₂, •••jQm координат сво­их последовательных вершин.

Упорядочим множество всех абсцисс обоих многоугольников по возрастанию (для простоты считаем, что абсциссы попарно раз­личны, хотя это и несущественно), в результате получим абсциссы а_г < а₂ < ... < а_1+т (рис. 7). Теперь для каждого i = 1, 2,..., Z+ т - 1

a₁ a₂ a₃ ... a_i a_i+1 ... a_m+l

Рис. 7. Алгоритм Шеймоса—Хоя (1= 5, т = 4).

строим пересечение трапеций, вырезаемых прямыми x = a_t,x = a_i+1 в заданных многоугольниках. (В вырожденном случае такая трапе­ция превращается в треугольник.) Из получившихся пересечений трапеций можно собрать Р nQ, удаляя лишние вершины.

Привлекая дополнительно те или иные структуры данных (масси­вы, списки, ...) и уточняя по мере надобности какие-то этапы алго­ритма, добиться того, чтобы в итоге алгоритм (обозначим его бук­вами SH) имел следующие сложностные характеристики. Если раз­мер входа — это г = 1+ т, то T_SH(r) = 6(г); если размер входа — это s = max{Z, т}, то r_s'_H(s) = 6(s); если размер входа имеет два параметра

См. [30, гл. 7].

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

I и т, то Tg'_ti(l,m) = Q(l + m)—мы рассматриваем операции сравне­ния и перемещения элементов, арифметические операции, как муль­типликативные, так и аддитивные, все вместе. Для пространственной сложности—S_SH(г), S'_SH(s) или S'^a, т) в зависимости от выбора раз­мера входа — получаем те же оценки в(г), 6(s) или 6(Z + m).

Указание. Если исходные многоугольники представить, например, двуна­правленными списками координат последовательных вершин, то список абс­цисс (а₁,а₂, ...,а_!+т), а_г < а₂ < ... < а_1+т, можно получить с временными за­тратами, не превосходящими с₀(1 + т).

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

15. Расширить алгоритм построения вояжа в ориентированном графе G = (V, Е) с выделенной начальной вершиной v (пример 3.2) так, чтобы помимо вояжа алгоритм выдавал также информацию о том, охватил ли вояж все ребра графа. Размер входа имеет два параметра m=|V|, п = \Е\. Для графов, не содержащих изолирован­ных вершин, т. е. вершин, подобных вершине 7 на рис. 3, сложность расширенного алгоритма должна быть 0(,п).

16. Задача распознавания существования и фактического построе­ния эйлерова цикла в данном графе для ориентированного случая вы­глядит так: выяснить, имеется ли в данном ориентированном графе цикл, проходящий по всем ребрам графа по одному разу, и если су­ществует, то построить этот цикл. Воспользовавшись рассмотренным алгоритмом построения вояжа (пример 3.2), дать алгоритм решения этой задачи. Размер входа имеет два параметра m= \V\, п = \Е\. Для графов, не содержащих изолированных вершин, сложность предлага­емого алгоритма должна быть 0(,п).

17. Путник столкнулся со стеной, простирающейся бесконечно в обе стороны. Имеется дверь в этой стене, но путник не знает ни расстояния до двери, ни направления к ней. Предложить позволя­ющий добраться до двери алгоритм, сложность которого допускает оценку 0{п), где п — число шагов (неизвестное путнику), изначаль­но отделяющее путника от двери.

Указание. Сумма s_k = 1 + q + ... + q^k, q > 1, есть величина порядка q^k, т.е.s_k = e(q^k).

18.Будем считать затратностью любого построения на плоскости
с помощью циркуля и линейки количество линий (окружностей или

Задачи

прямых), проводимых в ходе построения. Рассмотрим задачу постро­ения отрезка, длина которого равна 1/п от длины исходного отрезка, считая п размером входа. Предложить для этой задачи такой алго­ритм решения, сложность которого допускает оценку O(logn).¹

19. При п = 15 возможно вычисление а^п с меньшим числом умно­жений, чем требуется бинарному алгоритму возведения в степень.

20.Пусть двоичная запись числа neN есть ft...ft/Зо. Алгоритм

и:=1;

for i = k downto 0 do

и:=и-и;

if Pi = l then u:=u-afi od

вычисляет aⁿ. Сравнить сложность этого алгоритма по числу умно­жений с аналогичной сложностью бинарного алгоритма возведе­ния в степень, рассмотренного в примере 4.2, при использовании п или соответственно т = А(п) в качестве размера входа. (Описанный в этой задаче алгоритм является еще одним вариантом бинарного алгоритма возведения в степень.)

21.Для функции Z(n), определенной в конце § 4, выполнено 1{аЪ) s= sSZ(a)+Z(b)-l для всехa,beN+.

22.(Продолжение предыдущей задачи.) Можно ли утверждать, что Z(ab) = Z(a)+Z(b)-l для всехa,beN+?

¹ Разбор задач на построение с точки зрения их сложности содержится, например, в [11, §15].

Глава 2