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

Это говорит о том, что исследуемая сложность по числу делений

в среднем есть Г2( — 2^m/2) и как функция от m эта сложность не мо- m

жет быть оценена как O{m^d) ни при каком deN.

Определение 5.2. Вещественная неотрицательная функция f(m), определенная для целых положительных значений аргумента, назы­вается полиномиально ограниченной, если существует полином P{m) с вещественными коэффициентами такой, что f{m)^P{m) для всех meN⁺. (Очевидно, что мы получим эквивалентное определение, если дополнительно потребуем, чтобы все коэффициенты полинома P{m) были неотрицательными; другие эквивалентные варианты определе­ния: f{m) = O{m^d) для некоторого deN и f(m) = m^O(1).)

Доказанное нами можно сформулировать так:

Пусть в качестве размера входа алгоритма пробных делений, пред­назначенного для распознавания простоты натурального числа n, привлекается m = А(n). Тогда временные сложности этого алгоритма как в худшем случае, так и в среднем по числу делений не являются полиномиально ограниченными функциями от m.

Краткое обсуждение идеи такого алгоритма распознавания про­стоты числа, который имеет полиномиально ограниченную слож­ность в худшем случае (тем самым, разумеется, и в среднем), бу­дет проведено в примере 22.2. При этом речь пойдет не об алгеб­раической сложности по числу делений, мультипликативной сложно­сти и т. д., а о битовой сложности, что приводит к существенно более сильным утверждениям. До этого в гл. 5 будет детально рассмотрено само понятие битовой сложности.

§ 6. Сортировка и конечные вероятностные пространства.

Применение формулы полного математического ожидания

При рассмотрении сложности в среднем мы, прежде всего, должны превратить каждое из множеств входов, обладающих фиксированным размером, в вероятностное пространство. Проще работать с конеч­ными вероятностными пространствами, но как обходиться такими пространствами, имея дело, например, с алгоритмами сортировки, входом каждого из которых, при фиксированном размере n, может быть любой массив x_г,x₂, ■■■,x_n с попарно различными элементами? Общий принцип заключается в том, что мы разбиваем все имеющие фиксированный размер n входы на некоторые классы, включая в один

§ 6. Сортировка и конечные вероятностные пространства 47

класс входы, неразличимые для данного алгоритма в том смысле, что алгоритм проделывает одну и ту же последовательность операций для любого входа, принадлежащего классу (этот принцип может приме­няться не только при рассмотрении той или иной сортировки). Число таких классов может оказаться конечным, даже если само множество входов размера п бесконечно. Если это не противоречит другим пред­положениям, то такие классы можно рассматривать как элементар­ные события, приписывая каждому из них некоторую вероятность.

На выполнение любой сортировки с помощью сравнений сами значения элементов х₁,х₂, ...,х_п не оказывают никакого влияния, ва­жен лишь их относительный порядок. Поэтому в один класс есте­ственно объединять все массивы х₁,х₂,...,х_п, имеющие один и тот же порядок элементов по отношению друг к другу. Такой класс мо­жет быть представлен перестановкой чисел 1, 2, ...,п с соответству­ющим порядком элементов (перестановкой длины п). В дальнейшем для любого neN* мы будем рассматривать функцию i/>„, аргумента­ми которой являются любые попарно различные числа х₁,х₂,...,х_п, а значением — перестановка а = (а₁,а₂, . .., а_п) чисел 1, 2, ...,п, отра­жающая относительный порядок чисел х₁,х₂, ...,х_п. Например,

1/>3 (-³₄, -10,17) = (2,1, 3). (6.1)

Множество всех перестановок чисел 1,2,..., п будет обозначаться че­рез П„, так же будет обозначаться и вероятностное пространство,

получаемое приписыванием вероятности — каждой из этих переста­новок.

Рассмотрим некоторые события в вероятностном пространстве П_п;

вероятность каждого из них, очевидно, будет равна —, где М—чис­ло перестановок, составляющих событие. Эту вероятность мы будем обозначать через P_п(-).

Пример 6.1. Начнем с события B^v_n, 1^v^n, состоящего в том, что v-й элемент a_v перестановки (а₁,а₂, ...,а_п) равен v. Перестанов­ку (а₁,а₂,...,а_п)&и_п можно рассматривать как отображение множе­ства {1,2, ...,п} на себя, при котором 1 переходит в а₁, 2 переходит в а₂ и т.д., и событие B^v_n состоит тогда в том, что v является непо­движной точкой перестановки. Множество, состоящее из перестано­вок (а₁,а₂,..., а_п) таких, что a_v=v, содержит (п-1)! элементов, от-

_nv (п^-1)! 1 сюда P (В„) = :— = - при всех рассматриваемых v.

В зависимости от выбранной перестановки число неподвижных точек может быть любым целым из диапазона от 0 до п. Рассмотрим

48