Глава 2. Сложность в среднем

n, m размера входа. Беря максимум этих сложностей по всем m та­ким, что l^m^n, определяем сложности T{n), T{n) по числу срав­нений в худшем случае и в среднем с использованием n в качестве размера входа. Показать, что T{n) = Q{n²) и T(n)<4n.

Указание. Возьмем U(n) = max T(k). Очевидно, что U(n) не убывает при

ЫЫn

возрастании n и что T(n) ^ U(n). Доказывается неравенство

U(n) г£ i(U(n - 1) + тах{U(1), U n - 2)} + ... n

... + max{U(n - 2), U(1)} + U(n - 1)) + n - 1, из которого, в силу неубывания U(n), следует

U(n)s£-(U(n-l) + U(n-2) + ... + U(|_nJ))+n. Отсюда с помощью индукции выводится, что U(n) <4n для всех n> 1.

36. В инверсионном векторе (b_ъ b₂,..., b_n) произвольной переста­ новки (a₁,a₂,...,a_n)бП_n каждая компонента b_i равна количеству це­ лых j таких, что 1 ^ j <i и a_j >a_i. Например, инверсионный вектор перестановки (2, 4, 3,1, 6, 5) —это (0, 0,1, 3, 0,1). Показать, что каж­ дому целочисленному вектору (b_ъ b₂, •••, b_n), для которого 0 ^ b_i < i, i = 1, 2,..., n, соответствует некоторая перестановка длины n, для ко­ торой этот вектор является инверсионным.

Указание. Очевидно, что если b_n = k, 1Цk<n, то a_n=n-k, и это со­ображение приводит к алгоритму построения (a₁,a₂,...,a_n), применимому к любому вектору b, удовлетворяющему оговоренным условиям: просматри­ваем компоненты вектора b, продвигаясь от последней к первой, находим значение соответствующей компоненты перестановки a и удаляем найден­ное значение из множества M, первоначально равного {1, 2,..., n}; при этом значение a_i , i = n,n — 1,..., 1, определяется как (b_i - 1)-й наибольший в мно­жестве M (самый большой элемент —это первый наибольший, следующий по величине элемент —это второй наибольший и т.д.).

37. Показать, что один этап пузырьковой сортировки понижает на единицу значение каждой неотрицательной компоненты инверсион­ ного вектора перестановки (см. предыдущую задачу) и не изменяет нулевые компоненты. Показать, что вероятность того, что значение максимума компонент инверсионного вектора выбранной наугад пе­ рестановки длины n равно k, 0^k<n, есть —j—¹.

Указание ко второй части задачи. Количество векторов (b_1; b₂,..., b_n), для каждого из которых b_i е N+, 0 г£ bi < i, i = 1,2,..., n, и max{b_1; b₂,..., b_n} г£ k,

Задачи

71

1 ^ к ^ п - 1, равно к\ к^{п к г}, так как Ь_; может принимать любое значение между 0 и £ - 1 при £ ^ к и любое значение между 0 и к - 1 для k<i^n.

38. Показать, что математическое ожидание числа этапов пузырь­ковой сортировки совпадает с (6.9).

Указание. Пользуясь решением предыдущей задачи, легко получить, что это математическое ожидание есть

J(fc(fcⁿ-^fc/c!-(/c-l)ⁿ-^fc+1(fc-l)!),

J_ n!

fc=l

что равно

— (>(fcⁿ-^fc+1fc! - № - l)ⁿ-^fc+2№ - 1)!) - V(fc - l)"-^k+1(k - 1)! V

' k=l k=l

В упрощении последнего выражения поможет дискретный аналог формулы Ньютона—Лейбница (см. задачу 27).

39. Используя идею решения задачи 35, предложить рандомизи­рованный алгоритм восстановления перестановки длины п по ее ин­версионному вектору (см. задачу 36), имеющий сложность в среднем по числу сравнений 0{п²).

39. Пусть {а_ъа₂,...,а_п)— произвольная перестановка длины п. Ее преобразование

for i = n downto 2 do j := 1 + random(i - 1); щ^а_} od

может дать любую перестановку длины п с вероятностью —. (Это дает алгоритм построения случайных перестановок с равномерным распределением вероятностей.)

41. Предположим, что у нас нет другого генератора случайных чи­ сел, кроме генератора, в результате обращения к которому появля­ ется 0 или 1 с одинаковой вероятностью | (аналог подбрасывания монеты), и пусть р, O^p^l, — заданное вещественное число. Ка­ ким образом с помощью этого генератора можно определить гене­ ратор randp, в результате обращения к которому появляется 0 или 1 с вероятностями соответственно р и 1 - р (незначительные отклоне­ ния допустимы)? Сложность в среднем алгоритма получения одного случайного числа с помощью randp должна быть меньше 2 (затраты определяются числом обращений к изначально имеющемуся генера­ тору).

Указание. Представить р (возможно, с небольшой погрешностью) в виде конечной суммы вида —- Н—| + ... + -|, где а_{ —это 0 или 1 для всех £, а к — некоторое целое положительное число.

72