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

Пример 6.2. Исследуем сложности в среднем по числу сравне­ний и перемещений сортировки простыми вставками, которую, как и прежде, мы будем рассматривать в двух вариантах \_г и 1₂ (см. при­мер 1.4). Вначале займемся первым вариантом \_г этой сортировки, полагая затраты равными числу сравнений. Входные массивы счита­ем перестановками чисел 1,2,..., п. Для исследования сложности по числу сравнений введем случайные величины Е}_п, С •••> Ъ^п-^г, опреде­ленные так, что значение Е,¹_п для

а=(а₁,а₂,...,а_п)∈П„

равно затратам на i-м шаге нашей сортировки, применяемой к а. Ясно, что интересующее нас математическое ожидание есть Е(^ + ^ + ... +CJJ-¹), и

7}_i(n) = E^ + E?2 + ... + Eq-¹. (6.4)

Найдем ?_п, l^i<n. Рассматривая события H*-^l+1, fc = 0, l,...,i, об­разующие разложение пространства П„, и применяя формулу (6.3) полного математического ожидания, мы имеем согласно предложе­нию 6.1(iii)

ЕГ=ДтУЕ(Г|Я^⁺¹). (6.5)

fc=0

Если перестановка а = {а_ъа₂,...,а_п) принадлежит событию Н^+, то в этой перестановке перед элементом a_i+1 имеется ровно к элементов, меньших его, и, очевидно,

._fi-fc + l, если/с>0, n~i, если/с = 0.

Мы видим, что при выполнении события H^^I+1 значение Е,¹_п опреде­лено однозначно (напомним, что значение E,^l_n, i = 1, 2,..., п - 1, равно числу сравнений на i-м шаге, а перед выполнением i-го шага элемен­ты a₁,a₂,...,a_i уже упорядочены по возрастанию). Поэтому

. _м+1 fi-fc + 1, если/с>0, " "' i, если fc = 0.

В соответствии с (6.5)

fc=i

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

Используя (6.4), получаем выражение

п-1 +

п-1

fi

1

2 i + l

i = l

для искомой сложности в среднем. С помощью известной из матема­тического анализа формулы (ее вывод имеется в приложении B)

п

Y, у = Inn+ 0(1)

i=l

сложность T^in) можно записать в виде

Т}₁(п)=⁽" ^{+ 4)(}"-¹⁾-1пп + 0(1) (6.6)

[К 4 и, проще, в виде

Г; (п) = ^+0(п). (6.7)

п_² 4

Таким образом, сложность в среднем по числу сравнений первого ва­рианта сортировки простыми вставками, как и сложность в худшем случае, есть величина порядка п², но при больших п первая слож­ность примерно вдвое меньше второй. Формула (6.6) показывает, что, вообще говоря, вопреки бытовым представлениям сложность в сред­нем не есть среднее арифметическое затрат в худшем и в лучшем слу­чае: такое среднее арифметическое для рассматриваемой сортировки является рациональной функцией от п и не может описываться этой формулой, содержащей логарифм.

Если рассмотреть вместо случайных величин Е}_п, £²,..., Е^^х слу­чайные величины г\\, г;²,..., rf_n^_1, соответствующим образом отража­ющие затраты исследуемой сортировки по числу перемещений, то, очевидно, будем иметь

^ *S r,j, *S ?j, + 1,

i = 1, 2,..., n - 1. Поэтому сложность в среднем по числу перемещений

п² тоже есть — +0(п). Нетрудно показать, что и сложности в среднем

по числу сравнений и числу перемещений второго варианта сорти­ровки простыми вставками равны — + 0{п). Сложность в среднем по суммарному числу сравнений и перемещений и для первого, и для второго варианта есть ^+0(п), поскольку для любых случайных величин Е,,г), определенных на каком-либо вероятностном простран­стве, выполняется

Е(? + т)) = Е? + Ет). (6.8)

52