Лекции о сложности алгоритмов. С. А. Абрамов (1121249), страница 48

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

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

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

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

Через 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.. При k > 1 уравнение (H.) имеет k различныхкорней.

При этом в точности один из них — мы будем называть егоглавным корнем уравнения (H.) и обозначать через αk — по модулюпревосходит единицу. Главный корень — вещественное число, удовле1творяющее условию  2 − ¶ αk < 2.kДоказательство. Поскольку предстоит использовать некоторуютехнику теории аналитических функций, мы перейдем к привычномуобозначению z для комплексной переменной и будем рассматриватьуравнение z k − z k−1 − ...

− z − 1 = 0, левую часть которого обозначимчерез vk (z). Положим Vk (z) = (z − 1)vk (z) = z k+1 − 2z k + 1.Уравнение Vk (z) = 0 в сравнении с vk (z) = 0 имеет дополнительныйкорень z = 1; мы докажем утверждение предложения для Vk (z) = 0,См. [, гл. , пп. —], [], [, разд. .., упр. ]. В [] доказано также, чтовсе корни, отличные от главного корня αk , по модулю не превосходят αk − 1 < 1.Об одном семействе алгебраических уравненийk > 1, откуда будет следовать требуемое.

Доказательство мы проведемв три этапа, установив справедливость следующих утверждений:(i) для любого k > 1 все корни уравнения Vk (x) = 0 простые (т. е.имеют кратность 1);1(ii) круг любого радиуса r, 1 < r < 2 − , с центром в z = 0 содерkжит ровно k корней уравнения Vk (z) = 0;(iii) уравнение Vk (z) = 0 имеетмере один вещественh по меньшей1ный корень на полуинтервале 2 − , 2 .kДля доказательства утверждения (i) заметим, прежде всего, чтоíîä(Vk (z), Vk′ (z)) = íîä(Vk (z), z k−1((k + 1)z − 2k)).2kНо Vk (z) не обращается в  при z = 0 и при z =.

Отсюда следует,k+1что íîä(Vk (z), Vk′ (z)) = 1. Это говорит о том, что корни Vk (z) простые.Для доказательства утверждения (ii) положим Wk (z) = z k+1 − 2z k .Если на некоторой окружности выполняется неравенство | Wk (z) | > 1,то внутри этой окружности полиномы Vk (z) и Wk (z) по теореме Руше имеют одинаковое число корней. Рассмотрим окружность Sσ радиуса1 + σ, 0 < σ < 1, с центром в z = 0.

Так как| Wk (z) | = | z k+1 − 2z k | ¾ | 2z k | − | z k+1 |,то на окружности Sσ выполняется | Wk (z) | ¾ (1 + σ)k (1 − σ). Далее,очевидно, (1 + σ)k ¾ 1 + k σ, и мы получаем, что если σ удовлетворяетнеравенству(1 + k σ)(1 − σ) > 1,(H.)то условия теоремы Руше выполнены, и полином Vk (z) имеет внутри Sσ столько же корней, сколько их имеет Wk (x), т. е. k.

Неравенство (H.) выполнено для всех значений σ, принадлежащих интервалу с концами, являющимися корнями квадратного уравнения1k σ2 − (k − 1)σ = 0, — эти корни суть 0 и 1 − . Это доказывает утверkждение (ii).Наконец, утверждение (iii) следует из того, что vk (1) < 0, vk (2) > 0иприэтомуравнение vk (z) = 0 не имеет корней на интервале11, 2 −.kСм., например, [, гл. , § ] или [, п. .]. Применительно к полиномиальномуслучаю эта теорема допускает следующую формулировку.

Пусть полином V (z) предeставлен в виде суммы W(z) + W(z)двух полиномов, и на контуре некоторой областиeзначение | W(z)| меньше значения | W(z) |. Тогда внутри этой области число корнейполиномов V (z) и W(z) одинаково.Приложение HРекуррентное уравнение (H.) имеет, таким образом, общее решение1y(n) = Ck αnk + Ck−1 αnk−1 + ... + C1 α1n −k−1(αk — главный корень характеристического уравнения (H.), всеостальные корни α1 , α2 , ..., αk−1 по модулю не превосходят единицу). Нас интересует частное решение, удовлетворяющее условиюy(0) = y(1) = ... = y(k − 1) = 0.

И без нахождения всех Ci ясно, чтоCk 6= 0, — иначе последовательность y(k), y(k + 1), ... была бы ограниченной.На рис.  показано расположение корней уравнений Vk (z) = 0,k = 2, 3, 4.Im zIm z11Re z−101Re z−120−112−1а) z2 − z − 1 = 0б) z3 − z2 − z − 1 = 0Im z1Re z−1012−1в) z4 − z3 − z2 − z − 1 = 0Рис.

.Итак, нам удалось обойтись без фактического нахождения корнейхарактеристического уравнения. Более того, речь шла не об одномконкретном уравнении, а о семействе, в которое входят уравнениясколь угодно высоких степеней.Мы получили доказательство предложения . из § .Литература[] С. А. Абрамов. Исследование алгоритмов одновременного нахождения наибольшего и наименьшего элементов массива // ЖВМи МФ.

. Т. , № . С.  — .[] С. А. Абрамов. Элементы анализа программ. Частичные функциина множестве состояний. М.: Наука, .[] С. А. Абрамов, Г. Г. Гнездилова. Алгоритм управления вопросником в автоматизированной обучающей системе // Вестн. Моск.ун-та. Сер. . Вычисл. мат. и киб. . № . С. — .[] В. Б.

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

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