Лекции о сложности алгоритмов. С. А. Абрамов (1121249), страница 10
Текст из файла (страница 10)
Докажем, например, первое неравенство:XX¯T¯A (s) =C AT (x)Ps (x) ¶(max C AT (x))Ps (x) =x ∈ Xsx ∈ Xsx ∈ XsX=TA (s)Ps (x) = TA (s)x ∈ XsXPs (x) = TA (s).x ∈ XsВторое неравенство доказывается аналогично.Ниже в этом параграфе мы рассмотрим временную сложность всреднем ряда алгоритмов.Пример .. Как было уже установлено (пример .), бинарныйалгоритм возведения в степень n требует λ(n) + λ∗ (n) − 2 умножений; если в качестве размера взять m = λ(n), то сложность в худшемслучае будет равна 2m − 2.
Подсчитаем сложность в среднем, привлекая m как размер входа. Всего имеется 2m−1 неотрицательных целыхбитовой длины m; если считать все эти числа равновероятными, тоискомая сложность естьmm2X−12X−111∗(λ(n)+λ(n)−2)=m−2+λ∗ (n).m− 1m− 122n=2m−1n=2m−1Первая цифра каждого из чисел битовой длины m равна 1; количество чисел, имеющих кроме старшейцифрыеще k, 0 ¶ k ¶ m − 1,m−1ненулевых двоичных цифр, равно(т. е. числу сочетаний изkm − 1 по k). Поэтому искомую сложность можно переписать в видеm−1 m−1 XXm−11m−11k.m − 2 + m − 1 2 m −1 +k= m − 1 + m− 12k =1k2Легко проверяется, что при 1 ¶ k ¶ m − 1 выполненоm−1m−2k= (m − 1),kk−1k =1kГлава . Сложность в среднеми возможно дальнейшее упрощение выражения для сложности:m−1+m−12 m− 1m−1Xk =1m−2k−1=m−1+m−12 m− 1m−2Xl =0m−2l32= (m − 1).Если рассматривать m = λ(n) как размер входа бинарного алгоритма вычисления an , n ∈ N+ , то сложность в среднем по числу умно3жений для этого алгоритма есть (m − 1).2Таким образом, при больших m сложность в среднем бинарногоалгоритма возведения в степень приблизительно равна трем четвертым сложности в худшем случае.Анализ сложности в среднем для широкого ряда арифметическихалгоритмов опирается на асимптотический закон распределения простых чисел, который мы приведем без доказательства.Асимптотический закон распределения простых чисел.
Дляфункции π(n), значение которой равно количеству простых чисел,меньших данного натурального n, справедливо асимптотическое равенствоnπ(n) ∼.(.)ln nКак следствие, вероятность того, что при выборе «наугад» одногоиз целых чисел 1, 2, ..., n попадется простое число, асимптотически1 равна.ln nПример .. Вновь вернемся к алгоритму пробных делений, предназначенному для распознавания простоты данного n ¾ 2 (примеры ., .). Будем рассматривать в качестве размера входа битовуюПредположение о справедливости этого закона распределения простых чисел высказывалось, в частности, Гауссом и Лежандром.
Впоследствии в г. Чебышевымбыло доказано, что для некоторых констант c и Ccnln n< π(n) < Cnln nдля всех достаточно больших n, и, более того, им было установлено, что можно положить C = 1,10555, c = 0,92129. Асимптотическое равенство (.) было полностью доказано в г. независимо Ж. Адамаром и Ш. Валле Пуссеном. «После доказательстванеравенств Чебышева в г. речь шла, казалось бы, только о более точном нахождении и сближении постоянных c и C. Однако асимптотический закон распределенияпростых чисел был доказан лишь полвека спустя, в самом конце XIX века, на основании совершенно новых идей, предложенных Риманом...» [].
В [, гл. V] приводится1элементарное доказательство неравенств Чебышева для C = 6 и c = . Полное доказательство асимптотического закона имеется, например, в [].3§ . Понятие сложности в среднемдлину m данного числа. На первый взгляд сложность в среднем этогоалгоритма могла бы оказаться существенно меньшей, чем сложностьв худшем случае, так как для многих входов затраты совсем невелики.Например, для четных входов достаточно одного деления и т.
д. Длясложности в худшем случае по числу делений нами была установлена экспоненциальная оценка Θ(2m/2 ). Существует ли d ∈ N такое, чтосложность в среднем алгоритма пробных делений как функция от mдопускает оценку O(md )? Мы видим, что для довольно обширногомножества входов размера m алгоритм пробных делений работаетбыстро, и предположение, что для сложности в среднем существуеттакое число d, выглядит правдоподобным. На самом деле все обстоит не так, потому что среди всех натуральных чисел доля простых(для которых алгоритм пробных делений работает долго) достаточновелика. Оценка количества V (m) простых среди чисел2 m −1 ¶ n < 2 mможет быть получена из приведенной выше теоремы о распределениипростых чисел: воспользовавшись тем, чтоπ(2m ) ∼2m,(ln 2)mm → ∞,а также равенством V (m) = π(2m ) − π(2m−1 ), получимV (m) ∼11m−22m ∼2m .2 ln 2 m(m − 1)(2 ln 2)m(.)Теперь уже экспоненциальность роста сложности в среднем алгоритма пробных делений выводится легко.
Обозначим через D(n)количество делений, требующееся алгоритму пробных делений применительно к натуральному числу n. Для любого простого p ¾¾ 2m−1 , m ¾ 7, выполнено D(p) > 2m/2−1 (в самом деле, D(p) =p= ⌊ p ⌋ − 1 ¾ ⌊2(m−1)/2 ⌋ − 1 > 2(m−1)/2 − 2, и при m ¾ 7 выполнено2(m−1)/2 − 2 ¾ 2m/2−1 ). Интересующая нас сложность в среднем рав2m−1P1D(n). При m ¾ 7 мы имеемна m−12n=2m−112m− 1m2X−1n=2m−1D(n) ¾12m− 1Xm−1D(p) ¾ V(m)2−m/2 .(.)m2¶ p <2p — простоеУчитывая (.), находим, что последняя величина при m → ∞ асимптотически равна12m/2 .(2 ln 2)mГлава .
Сложность в среднемЭто говорит о том,чтоисследуемая сложность по числу делений1 m/2и как функция от m эта сложность не мо2в среднем есть Ωmжет быть оценена как O(md ) ни при каком d ∈ N.Определение .. Вещественная неотрицательная функция f (m),определенная для целых положительных значений аргумента, называется полиномиально ограниченной, если существует полином P(m)с вещественными коэффициентами такой, что f (m) ¶ P(m) для всехm ∈ N+ .
(Очевидно, что мы получим эквивалентное определение, еслидополнительно потребуем, чтобы все коэффициенты полинома P(m)были неотрицательными; другие эквивалентные варианты определения: f (m) = O(md ) для некоторого d ∈ N и f (m) = mO(1) .)Доказанное нами можно сформулировать так:Пусть в качестве размера входа алгоритма пробных делений, предназначенного для распознавания простоты натурального числа n,привлекается m = λ(n). Тогда временные сложности этого алгоритмакак в худшем случае, так и в среднем по числу делений не являютсяполиномиально ограниченными функциями от m.Краткое обсуждение идеи такого алгоритма распознавания простоты числа, который имеет полиномиально ограниченную сложность в худшем случае (тем самым, разумеется, и в среднем), будет проведено в примере ..
При этом речь пойдет не об алгебраической сложности по числу делений, мультипликативной сложности и т. д., а о битовой сложности, что приводит к существенно болеесильным утверждениям. До этого в гл. будет детально рассмотреносамо понятие битовой сложности.§ . Сортировка и конечные вероятностные пространства.Применение формулы полного математического ожиданияПри рассмотрении сложности в среднем мы, прежде всего, должныпревратить каждое из множеств входов, обладающих фиксированнымразмером, в вероятностное пространство.
Проще работать с конечными вероятностными пространствами, но как обходиться такимипространствами, имея дело, например, с алгоритмами сортировки,входом каждого из которых, при фиксированном размере n, можетбыть любой массив x1 , x2 , ..., xn с попарно различными элементами?Общий принцип заключается в том, что мы разбиваем все имеющиефиксированный размер n входы на некоторые классы, включая в один§ .
Сортировка и конечные вероятностные пространствакласс входы, неразличимые для данного алгоритма в том смысле, чтоалгоритм проделывает одну и ту же последовательность операций длялюбого входа, принадлежащего классу (этот принцип может применяться не только при рассмотрении той или иной сортировки). Числотаких классов может оказаться конечным, даже если само множествовходов размера n бесконечно. Если это не противоречит другим предположениям, то такие классы можно рассматривать как элементарные события, приписывая каждому из них некоторую вероятность.На выполнение любой сортировки с помощью сравнений самизначения элементов x1 , x2 , ..., xn не оказывают никакого влияния, важен лишь их относительный порядок.
Поэтому в один класс естественно объединять все массивы x1 , x2 , ..., xn , имеющие один и тотже порядок элементов по отношению друг к другу. Такой класс может быть представлен перестановкой чисел 1, 2, ..., n с соответствующим порядком элементов (перестановкой длины n). В дальнейшемдля любого n ∈ N∗ мы будем рассматривать функцию ψn , аргументами которой являются любые попарно различные числа x1 , x2 , ..., xn ,а значением — перестановка a = (a1 , a2 , ..., an ) чисел 1, 2, ..., n, отражающая относительный порядок чисел x1 , x2 , ..., xn .
Например,3(.)ψ3 − , −10, 17 = (2, 1, 3).4Множество всех перестановок чисел 1, 2, ..., n будет обозначаться через Πn , так же будет обозначаться и вероятностное пространство,1получаемое приписыванием вероятностикаждой из этих перестаn!новок.Рассмотрим некоторые события в вероятностном пространстве Πn ;Mвероятность каждого из них, очевидно, будет равна , где M — чисn!ло перестановок, составляющих событие. Эту вероятность мы будемобозначать через Pn (·).Пример .. Начнем с события Bvn , 1 ¶ v ¶ n, состоящего в том,что v-й элемент av перестановки (a1 , a2 , ..., an ) равен v.
Перестановку (a1 , a2 , ..., an ) ∈ Πn можно рассматривать как отображение множества {1, 2, ..., n} на себя, при котором 1 переходит в a1 , переходитв a2 и т. д., и событие Bvn состоит тогда в том, что v является неподвижной точкой перестановки. Множество, состоящее из перестановок (a1 , a2 , ..., an ) таких, что av = v, содержит (n − 1)! элементов, от(n − 1)!1= при всех рассматриваемых v.сюда Pn (Bvn ) =n!nВ зависимости от выбранной перестановки число неподвижныхточек может быть любым целым из диапазона от 0 до n.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
