С.А. Абрамов - Вычислительная сложность алгоритмов, страница 2

Если для некоторого алгоритма ATA* (m) ≤ f (m) , то TA (n) ≤ f (log 2 n + 1) .Доказательство: 2 m−1 ≤ n < 2m ; ∃nˆ : 2m−1 ≤ nˆ < 2 m и такое, что TA (nˆ ) = TA* (m) .TA (n) ≤ TA (nˆ ) = TA* (m) ≤ f (m) = f (⎣log 2 n ⎦ + 1) ≤ f (log 2 n + 1) .Лемма 2. Пусть g (x) не убывает. Тогда( )2) если T (n) ≥ g (n) , то T (m) ≥ g (2 ).Доказательство: 2 ≤ n < 2 ; ∃nˆ ∈ [2 , 2 ) , такое, что на нём достигается максимум1) если TA (n) ≤ g (n) , то TA* (m) ≤ g 2 m ;m−1*AAm −1mm −1mTA (n) , т.е. TA (nˆ ) = mmaxTA (n) .−1m2≤ n< 21) TA* (m) = TA (nˆ ) ≤ g (nˆ ) ≤ g (2m ) ;2) TA* (m) = TA (nˆ ) ≥ g (nˆ ) ≥ g (2 m−1 ) .Указанные леммы можно обобщить на асимптотики, тогда получим:Лемма 1*. Если f (x) — неубывающая функция, TA* (m) = O( f (m) ) , то= O( f (log 2 n + 1) ) .

Если дополнительно f ( x + 1) = O( f ( x) ) , то TA (n) = O( f (log 2 n) ) .TA (n) =Лемма 2*. Пусть g (x) не убывает. Тогда1) если TA (n) = O( g (n) ) , то TA* (m) = O(g (2 m )) ;2) если TA (n) = Ω( g (n) ) , то TA* (m) = Ω(g (2m −1 )) .⎛x⎞Если дополнительно g ⎜ ⎟ = Ω( g ( x) ) , то TA* (m) = Ω(g (2 m )) .⎝2⎠Алгоритм возведения в степень: an.Рассмотрим алгоритм возведения в натуральную степень методом повторных квадратов (RS= repeating squaring). Для этого запишем n в двоичной системе счисления: n = β k β k −1...β1β 0 ,β i ∈ {0, 1}.

Приведём сам алгоритм на псевдокоде:q := a; u := 1;for i = 0 to k doif βi = 1 then u := u * q fi;if i < k then q := q2 fi;odЛегко видеть, что, взяв в качестве размера входа битовую длину n, получим сложность этогоалгоритма по числу умножений в следующем виде: TRS* (m) = 2m − 2 . Если в качестве входавзять значение n, то сложность перепишется в следующем виде: TRS (n) = ν (n) + ν * (n) − 2 , гдеν * (n) — количество единиц в двоичной записи n.8Сложность в среднемРассмотрим множество I s = {x : x = s} .

Введём на этом множестве классическуювероятность Ps ( x) =1, ∀x ∈ I s , где N s = card I s = I s (количество элементов множества).NsНе трудно видеть, что так введённая вероятность удовлетворяет условию:∑ P ( x) = 1 .x∈I ssОпределение. Величина TA ( s ) = ∑ C AT ( x) Ps ( x) называется временнόй сложностью в среднемx∈I sалгоритма A.Определение. Величина S A ( s ) = ∑ C AS ( x) Ps ( x) называется пространственной сложностью вx∈I sсреднем алгоритма A.Утверждение.

Сложность в среднем не превосходит сложность в худшем случае:TA ( s ) ≤ TA ( s ) и S A ( s ) ≤ S A ( s ) .Доказательство проведём для временной сложности (для пространственной сложностидоказательство проводится аналогично): TA ( s ) = ∑ C AT ( x) Ps ( x) ≤ ∑ ⎛⎜ max C AT ( x) ⎞⎟ Ps ( x) =x∈I s⎠x∈I sx∈I s ⎝= ∑ TA ( s ) Ps ( x) = TA ( s )∑ Ps ( x) = TA ( s ) .x∈sx∈s14243=1Пример. Найдём сложность в среднем алгоритма возведения в степень (RS), описанногоранее. Рассмотрим множество I m = {n : 2m−1 ≤ n < 2m } . Вероятность каждого элемента этого111множества положим равной= m= m−1 . Тогдаm −1Im 2 − 22mm −1⎞⎛⎞1 ⎛1 2 −1 **⎟⎜TRS (m) = m−1 ∑ ν{(n) + ν (n) − 2 = (m − 2) + m−1 ∑ν (n) = m − 2 + m−1 ⎜ 2 m−1 + ∑ kCmk −1 ⎟ =⎟⎜2 ⎝2 n=2m−12 n=2m−1 ⎝ =mk =1⎠⎠12m −1= {kCmk −1 = (m − 1)Cmk −−12 } = m − 2 +m−1⎞1 ⎛ m−12(m1)Cmk −−12 ⎟ = {k = l + 1} =+−⎜∑m −12 ⎝k =1⎠⎛⎞⎜⎟m−2m −131= m − 2 + m−1 ⎜ 2 m−1 + (m − 1)∑ Cml −2 ⎟ = m − 1 + m−1 ⋅ 2 m−2 = (m − 1) < 2m − 2 = TRS* (m)⎜⎟222l =014243⎟⎜m−2=(1+1)⎝⎠⎛⎞⎜⎟m−21 ⎜ m−1m −13l= m − 2 + m−1 2 + (m − 1)∑ Cm−2 ⎟ = m − 1 + m−1 ⋅ 2 m−2 = (m − 1) < 2m − 2 = TRS* (m)⎟2 ⎜22l =014243⎟⎜=(1+1)m − 2 ⎠⎝Асимптотический закон распределения простых чисел.Рассмотрим функцию Эйлера π (n) , равную количеству простых чисел, меньших n.

Для этой9n. Рассмотрим ряд 1, 2, …, N. Вероятность того,ln n1что наперёд взятое число из этого ряда простое, согласно асимптотике π (n) , близка к.ln Nфункции известна асимптотика: π (n) ~Предпринимались многие попытки доказать асимптотический закон π (n) . Так, в 1850 г.nnЧебышёвым было доказано, что ∃c, C > 0 : c.

Позднее было получено, что< π ( n) < Cln nln nc = 0,92129 , C = 1,10555 . В 1896 г. асимптотический закон для π (n) был доказан Адамаром.⎛ m2 ⎞Вернёмся к алгоритму пробных делений. Известно, что T (m = ν (n) ) = Θ⎜⎜ 2 ⎟⎟ (см. задачу 6).⎝ ⎠*TDОпределение. Алгоритм называют алгоритмом с полиномиально ограниченной сложностью,если его сложность составляет O(m d ) .Определение. Алгоритм называют полиномиальным, если его сложность полиномиальноограничена.Не используя предыдущую оценку, покажем, что алгоритм пробных делений (TD) неявляется полиномиально ограниченным. Для этого рассмотрим функцию V (m) —( )количество простых чисел из полуинтервала 2 m−1 ≤ n < 2 m .

При m → ∞ , π 2 m ~2m.m ln 2m−2⋅ 2 m . Пусть D(n) — количество делений,2m(m − 1) ln 2необходимых алгоритму при работе с n, тогда если p ≥ 2 m −1 — простое число, тоТогда V (m) = π (2 m ) − π (2 m−1 ) ~D( p) =⎣⎦m2 m−1 − 1 ≥ 2 2TTD (m) =12m −1−1(для m ≥ 4 ). Используя эту оценку, для TTD (m) получаем:∑ D ( n) ≥2m−1 n=2m−11∑ D( p) ≥2 m−1 2m−1≤ p<2m12m−1⋅ 2 2 ⋅ V ( m) =m−1p - простоеm⎛1 m⎞m−2⋅ 2 2 = Ω⎜⎜ ⋅ 2 2 ⎟⎟ ,2m(m − 1) ln 2⎝m⎠откуда, в силу утверждения TA ≥ TA , получаем, что сложность алгоритма пробных деленийне является полиномиально ограниченной.Сложность в среднем алгоритмов сортировки.Пусть (a1 ,..., an ) — некоторая перестановка ( ai ∈ [1, n], ai ≠ a j при i ≠ j ). Рассмотримфункцию ψ n (t1 ,..., t n ) , которая для любого набора попарно различных чисел будетвозвращать перестановку (a1 ,..., an ) , отражающую порядок чисел t1 ,..., t n .⎛ 3⎞Пример.

ψ 3 ⎜ − , − 10, 17 ⎟ = (2, 1, 3) .⎝ 4⎠Не трудно видеть, что сложности сортировок исходного массива t1 , ... , t n и полученнойперестановки a1 , ... , an совпадают, поэтому можно ограничится рассмотрением сложностиалгоритмов сортировки, применяемых к перестановкам.10Рассмотрим множество всевозможных перестановок их n элементов Π n , оно же будет1(т.к.являться вероятностным пространством, с вероятностью каждого элементаn!количество всевозможных перестановок из n элементов равно n! ).Для дальнейшего нам понадобится факт из теории вероятностей, получивший названиеформула полного математического ожидания.Пусть пространство событий W может быть разложено на сумму попарно несовместныхсобытий Wi: W = W1 + ...

+ Wl , Wi ∩ W j = ∅ при i ≠ j . Пусть ξ — случайная величина,определённая на W. Тогда по определению Eξ =∑ ξ (ω ) P(ω ) .Пусть известны условныеω∈Wматематические ожидания E(ξ | Wk ) , k = 1, ... , l . Тогда формула полного математическогоожидания выглядит следующим образом:lEξ = ∑ E(ξ Wk )P(Wk ) .k =1Утверждение.(i) Пусть 1 ≤ u ≤ n , 1 ≤ v ≤ n и событие Fnu ,v заключается в том, что v-й элементперестановки a1 ,..., an равен u, т.е. av = u . Тогда вероятность такого события1Pn Fnu ,v = .n()(ii) Пусть 1 ≤ u ≤ n и p — некоторая перестановка чисел 1, ...

, u − 1 . Пусть событиеGnu , p заключается в том, что порядок элементов, меньших u, совпадает с p. Тогда1.вероятность такого события Pn Gnu , p =(u − 1)!()(iii) Пусть 0 < u < v ≤ n и событие H nu ,v заключается в том, что существует ровно uэлементов перестановки a1 , ... , an , для которых верно ai < av ∀1 ≤ i < v . Тогда1вероятность такого события Pn H nu ,v = .v()Доказательство:(i) очевидно: всего перестановок n! , перестановок, у которых один элемент(n − 1)! (n − 1)! 1== .фиксирован (n − 1)! ⇒ Pn Fnu ,v =n!n(n − 1)! n()(ii) всего перестановок n! , из них перестановок, в которых порядок элементовn!(n − u + 1)!n!=меньших u фиксирован, Cnu −1 (n − u + 1)!=, откуда(u − 1)!(n − u + 1)! (u − 1)!1Pn G nu , p =.(u − 1)!()(iii) если p — некоторая перестановка 1, ...

, v , то число перестановок (a1 , ... , an ) ∈ Π n ,n!для которых ψ n (a1 , ... , av ) = p , равно Cnv (n − v)!= . Число перестановок p, дляv!11которых последний элемент равен u − 1 , составляет (v − 1)! , откуда общее числоn!1⇒ Pn H nu ,v = .событий равноvv()Сортировка простыми вставками (I1).упорядочены678На i-й итерации алгоритма первые i элементов массива упорядочены: x1 ,..., xi , xi+1 ,... итребуется поставить на место xi+1 . Для этого xi+1 сравнивается подряд со всеми элементамислева, начиная с xi , до тех пор, пока не будет найден элемент, меньший xi+1 , или не будетдостигнута граница массива. После определения правильного места для элемента xi+1начинаются обмены элемента xi+1 с элементом, стоящим справа до тех пор, пока элемент xi+1не встанет на место.Найдём сложность в среднем этого алгоритма.

Для этого введём следующие случайныевеличины ξ n1 ,..., ξ nn−1 такие, что ∀a ∈ Π n ξ ni (a) показывает затраты на i-м шаге алгоритма.Тогда TI1 (n) = E(ξ n1 + ... + ξ nn−1 ) = Eξ n1 + ... + Eξ nn−1 . Рассмотрим события H nk ,i+1 , k = 0,1,..., i , тогдаΠ n = H n0,i+1 + H n1,i+1 + ... + H ni ,i+1 .По формуле полного математического ожидания получаем:Eξ ni =()1 iE ξ ni H nk ,i+1 .∑i + 1 k =0Допустим, что событие H nk ,i+1 выполнено, тогда⎧i − k + 1, k > 0k =0⎩i,ξ ni (a) = ⎨()ξ ni (a) = E ξ ni H nk ,i +1 ⇒ Eξ ni =i⎞ i1 ⎛1⎜ i + ∑ (i − k + 1)⎟ = + 1 −i + 1 ⎝ k =1i +1⎠ 2n −1n−11 ⎞1 ⎞⎛i⎛iОткуда получаем TI1 (n) = ∑ ⎜ + 1 −⎟ = n −1+ ∑ ⎜ −⎟ .

Из курса математическогоi +1⎠i +1⎠i =1 ⎝ 2i =1 ⎝ 2n1анализа известно, что ∑ = ln n + O(1) , тогда для TI1 (n) получаем:i =1 iTI1 (n) =n2(n + 4)(n − 1)− ln n + O(1) =+ O ( n) .44По числу перемещений (обменов) оценка останется верной, т.к. число перемещенийотличается от числа сравнений не более, чем на 1.Пусть ξ — затраты на сравнения, а η — затраты на перемещения. Тогда суммарнаясложность в среднем будет равна: E(ξ + η ) = Eξ + Eη .Сортировка «пузырьком».Имеется массив x1 , x2 ,..., xn , который требуется отсортировать. Сравниваем парами xi и xi+1 ,если xi > xi+1 , то меняем их местами и продолжаем с xi+1 . После первого прохода последний(наибольший) элемент окажется на своем месте.

Второй проход идёт до n − 1 , третий до12n − 2 и т.д. Заканчиваем, когда ни одной перестановки не было или остался массив из одногоэлемента.πnСложность в среднем такого алгоритма составит T (n) = n −2.Быстрая сортировка (QS = quick sort).Есть массив x1 , x2 ,..., xn , который нужно отсортировать. Для этого выбираем разбивающийэлемент (не важно какой, например, первый). Разбиваем элементы массива на 2 группы: теэлементы, которые меньше разбивающего, и те, которые больше. Далее применяем ту жепроцедуру рекурсивно к полученным после разбиения двум частям.В худшем случае заведомо TQS (n) = Ω(n 2 ) , т.к.