С.А. Абрамов - Лекции о сложности алгоритмов (pdf) (1123764), страница 46

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 46)

Поэтому доказательство теоремы D. сохраняет силу при рассмотрении сложения и вычитанияв качестве аддитивных операций.Известен алгоритм, который для вычисления значения произвольного полинома n-й степени требует n сложений и n умножений, этоалгоритм («схема») Горнера:an x n + an−1 x n−1 + ... + a1 x + a0 = (...(an x + an−1 )x + ... + a1 )x + a0 .Таким образом, мы получили следующий результат:Если рассматривать n в качестве размера входаx, a0 , a1 , ..., an ,то как по числу сложений, так и по числу умножений схема Горнераявляется оптимальным в худшем случае алгоритмом вычисления значения an x n + ...

+ a1 x + a0 с помощью операций сложения и умножения.Разумеется, полиномы какого-либо частного вида, как, например,x n , могут вычисляться с меньшими затратами.В  г. В. Я. Пан доказал утверждение теоремы D. в несколько более общей форме — см., например, [, разд. .., упр. ]. Главные идеи доказательства, приведенного выше в этом приложении, взяты из [].Приложение EОб одном свойстве сумм неотрицательныхслучайных величинЗдесь доказывается теорема . из § .Пусть ξ1 , ξ2 , ... — последовательность неотрицательных случайных величин на некотором вероятностном пространстве. Пусть числовая последовательность h1 , h2 , ... такова, что для каждого k ¾ 1выполнено E(ξk |ξ1 , ξ2 , ..., ξk−1 ) ¶ hk при всех значениях ξ1 , ξ2 , ..., ξk−1 .Зафиксируем неотрицательное число q и введем целочисленную случайную величину§nªXτ = min n:ξk ¾ q .k =1Пусть τ < ∞ всюду на рассматриваемом вероятностном пространP‹τстве.

Тогда Ehk ¾ q.k =1Рассмотрим случайные величины χk , k = 1, 2, ..., где χ1 = 1, а приk > 1 выполняется χk = 1, если ξ1 + ξ2 + ... + ξk−1 < q, и χk = 0 в противном случае. Заметим, что¨1, если τ ¾ k,χk =0, если τ < k,и 1 = χ1 ¾ χ2 ¾ ...Положим pk = P(τ = k) = P(χk = 1) − P(χk+1 = 1), k = 1, 2, ... Ясно,что P(χk = 1) = 1 − p1 − p2 − ... − pk−1 .

ИмеемEXτ‹ X∞ Xkhk =h j P(τ = k) =k =1 j =1k =1∞X=k =1(P(χk = 1) − P(χk+1 = 1))kXj =1hj =Приложение E∞X=P(χk = 1)j =1k =1∞X=P(χk = 1)∞XkXj =1k =1=kXP(χk = 1)kXk =1j =1∞XkX=P(χk = 1)j =1k =1= h1 P(χ1 = 1) +hj −hj −hj −hj −∞X∞XP(χk+1 = 1)P(χk = 1)P(χk = 1)hj =Xkj =1k =2∞Xk −1Xj =1k =2∞Xhj =j =1k =1∞XkXP(χk = 1)kXj =1k =2‹h j − hk =hj +∞XP(χk = 1)hk =k =2hk P(χk = 1) =k =2∞X=hk P(χk = 1).k =1Таким образом,EXτ‹hk =∞Xhk P(χk = 1).(E.)k =1k =1Введем случайные величины ηk = χk ξk , k = 1, 2, ...; из определенияслучайных величин χk следует, что∞Xηk ¾ q.(E.)k =1Докажем, что для k = 1, 2, ...Eηk ¶ hk P(χk = 1).(E.)Рассмотрим полную группу событий W1 , W2 : в W1 попадают те элементы вероятностного пространства, для которых ξ1 + ξ2 + ...

+ ξk−1 < q,в W2 — для которых ξ1 + ξ2 + ... + ξk−1 ¾ q. С учетом определения случайной величины χk , равной 1 на множестве W1 и 0 на множестве W2 ,получаем по формуле полного математического ожидания:Eη k = E(χ k ξ k ) == E(χk ξk |W1 )P(W1 ) + E(χk ξk |W2 )P(W2 ) == E(ξk |W1 )P(W1 ) == E(ξk |W1 )P(χk = 1),Об одном свойстве сумм случайных величинт. е.Eηk = E(ξk |W1 )P(χk = 1).(E.)Так как по условию неравенство E(ξk |ξ1 , ξ2 , ..., ξk−1 ) ¶ hk выполняется при всех значениях ξ1 , ξ2 , ..., ξk−1 , то оно выполняется на W1 .С учетом (E.) имеем E(ξk |W1 )P(χk = 1) ¶ hk , откуда следует (E.).Из (E.), (E.), (E.) получаем‹ X∞X∞∞‹XτXq = Eq ¶ EEη k ¶ηk =hk P(χk = 1) = Ehk ,k =1k =1k =1k =1что и требовалось .Сходное, но менее подробное доказательство имеется в [, гл.

III, § , теорема ],но там в условии теоремы пропущено требование конечности τ (см. задачу ).Приложение FО сортировке, оптимальной по числусравнений в худшем случаеДолгое время считалось правдоподобным предположение, что сортировкой, оптимальной по числу сравнений в худшем случае, являетсясортировка бинарными вставками, о сложности TB (n) которой, вместе с этим, было известно, что TB (5) = 8, при том, что наибольшаяиз обоснованных нижних границ для числа сравнений, необходимыхдля сортировки пяти элементов, есть ⌈log2 5!⌉ = 7.

Это порождало гипотезу, что сложность Topt (n) оптимальной сортировки для некоторыхзначений n больше, чем ⌈log2 n!⌉, и первое такое значение n равнопяти. Но в  г. Г. Б. Демутом был найден алгоритм сортировки пятиэлементов, который требует всего семь сравнений.Этот алгоритм можно легко изобразить с помощью рисунков, накоторых те точки, которые соответствуют сравнивавшимся элементам, соединяются стрелкой, ведущей от большего элемента к меньшему. Сравниваем первый элемент со вторым и третий с четвертым,а потом сравниваем меньшие найденныеэлементы; на это уйдет три сравнения(рис. ).

Этим, в частности, для трех элементов из пяти мы устанавливаем их относительный порядок. Затем для пятого элемента, который еще не сравнивался, мы наРис. . Сортировка пятиходим место среди трех уже упорядоченэлементов: ситуацияных элементов бинарным поиском; на этопосле трех сравнений.уйдет два сравнения. Тем самым мы приходим к одному из двух случаев, изображенных на рис. .

И в том, и в другом случае для завершения сортировки с помощью бинарного поиска места элемента достаточнодвух сравнений: в случае, изображенном на рис. а, вставка производится в массив из двух элементов, в случае, изображенном нарис. б, — из трех элементов. В итоге семи сравнений оказываетсядостаточно.О сортировке, оптимальной по числу сравненийа)б)Рис.

. Сортировка пяти элементов, ситуация после нахождения места пятого элемента среди трех упорядоченных элементов: а) пятый элемент меньшевсех трех упорядоченных элементов; б) пятый элемент больше наименьшего из трех упорядоченных элементов. (В обоих случаях еще двух сравненийдостаточно для завершения сортировки.)Указанный алгоритм сортировки пяти элементов был позднееобобщен на произвольное число элементов, эта сортировка получила название сортировки слияниями и вставками. Через TF (n) обычно обозначается сложность этой сортировки по числу сравнений.Обнаружено, что TF (n) = ⌈log2 n!⌉ для n = 1, 2, ..., 11. Но при этомTF (12) = 30, хотя ⌈log2 12!⌉ = 29, и возникает вопрос, всегда ли возможна сортировка двенадцати элементов не более чем двадцатью девятью сравнениями? Аналогичные вопросы могут возникнуть и длябо́льших значений n.Как говорилось в § , имеется алгоритм, который, исходя из n > 0,строит оптимальный по числу сравнений алгоритм сортировки массивов из n элементов (алгоритм строит алгоритм).

Этот алгоритмпостроения оптимального алгоритма сортировки требует огромнойработы, даже если применить все средства экономии перебора. Но,тем не менее, на этом пути с помощью компьютера показано, чтоTopt (12) = 30, что больше, чем ⌈log2 12!⌉. Но дальше продвинуться неудалось, и по сегодняшний день, видимо, неизвестно число Topt (13):n:⌈log2 n!⌉:TB (n):TF (n):Topt (n):?Исследования, не связанные с компьютерным вычислением Topt (n),показали, что имеется бесконечно много значений n, для которыхTF (n) > Topt (n). Значение 47 — наименьшее из известных  .См.

[, разд. ..].Приложение GМетод построения общего решениялинейного рекуррентного уравненияс постоянными коэффициентамиНапомним метод построения общего решения линейного рекуррентного уравнения с постоянными коэффициентами  . Начнем со случаяоднородного уравненияad y(n) + ad−1 y(n − 1) + ... + a0 y(n − d) = 0.(G.)Пусть λ1 , λ2 , ..., λs — все различные корни характеристического уравненияad λd + ad−1 λd−1 + ... + a0 = 0(G.)и m1 , m2 , ..., m s — кратности этих корней, m1 m2 + ... + m s = d. Общимрешением уравнения (G.) являетсяsXk =1(Ck,mk −1 nmk −1 + ... + Ck1 n + Ck0 )λnk ,(G.)где все Cij — произвольные постоянные.Общее решение неоднородного линейного рекуррентного уравнения с постоянными коэффициентамиad y(n) + ad−1 y(n − 1) + ...

+ a0 y(n − d) = f (n),(G.)где f (n) — известная функция, является суммой общего решения соответствующего однородного уравнения (G.) и какого-нибудь частного решения неоднородного уравнения (G.).Если правая часть f (n) уравнения (G.) представлена в видеf (n) = g(n) + ... + h(n) и если известны частные решения v(n), ......, w(n) для уравнений, левые части которых совпадают с левойчастью уравнения (G.), а правые части равны соответственноСм., например, [, гл. V, § ], [, гл.

].Построение общего решения рекуррентного уравненияg(n), ..., h(n), то v(n) + ... + w(n) будет частным решением уравнения (G.).Если правая часть f (n) неоднородного уравнения (G.) представляет собой квазиполином, т. е. равна p(n)µn , где p(n) — полиномнекоторой степени l ¾ 0, а µ — некоторое (комплексное) число, то(G.) имеет частное решение в виде квазиполинома q(n)µn , и приэтом полином q(n) имеет степень l + m, где m — кратность µ как корня характеристического уравнения (G.) (если µ не является корнемэтого уравнения, то считаем кратность нулевой: m = 0). Коэффициенты полинома q(n) находятся методом неопределенных коэффициентов.Частные решения с заданными начальными значениями находятсяподстановкой в общее решение начальных значений и определениемпостоянных из возникшей системы линейных алгебраических уравнений. (C помощью этого метода выводится и формула Бине (.).)Приложение HОб одном семействе алгебраическихуравненийВ примере . мы столкнулись с рекуррентным уравнениемy(n) − y(n − 1) − ...

− y(n − k) = 1,(H.)y(0) = y(1) = ... = y(k − 1) = 0. В качестве частного решения этого−1. Нам предстонеоднородного уравнения при k > 1 можно взятьk−1ит теперь заняться общим решением соответствующего однородногоуравнения, характеристическим уравнением которого служитλk − λk−1 − ... − λ − 1 = 0.(H.)Свойства корней уравнения (H.) описываются следующим предложением.Предложение H..

Характеристики

Список файлов лекций