§ 7. Пример медленного роста сложности в среднем

57

восходящую ⁿ длину, то в ходе применения сортировки к массиву x длины n > 1 число отложенных заданий, хранящихся в стеке, никогда не превосходит log₂ n.

Доказательство. Проведем индукцию по n. При n = 2 утвер­ждение, очевидно, справедливо. Пусть утверждение доказано для 2, 3,..., n - 1, и пусть массив x, содержащий n элементов, на первом этапе сортировки порождает два массива x', x", причем длина n' первого массива x' не превосходит -, длина n" второго массива x" не превосходит n - 1. Пусть n" ^ n' ^ 1. На протяжении сортировки массива x', помимо отложенных заданий, связанных с сортировкой x', в стеке будет храниться еще одно задание — сортировать x". Но в момент, когда сортировка массива x' завершена, в стеке не останется никаких ее следов; таким образом, по предположению индукции, число отложенных заданий в стеке никогда не превзой­дет max{log₂ n' + 1, log₂ n"}. В силу того, что n' ^ § и n" ^ n - 1, мы имеем

max{log₂ n' + 1, log₂ n"} ^ log₂ n, что и требовалось. □

Полученная оценка числа отложенных заданий, хранящихся в сте­ке, является оценкой для сложности в худшем случае и, тем самым, для сложности в среднем тоже.

Принимая во внимание теорему 7.1, мы приходим к варианту быст­рой сортировки, представляемому рекурсивной процедурой qsort{k, l), обращение к которой обеспечивает сортировку части x_k x_{k +ъ} ..., x_l ис­ходного массива x_г, x₂, ■ ■ ■, x_n; при k ^ l никаких действий не произ­водится. Сам массив x_ъx₂, ■■■,x_n является глобальным по отношению к процедуре:

if k<l then

x_k выбирается в качестве разбивающего элемента и выпол­няется разбиение x_k,x_k+ъ ...,x_l; пусть i — индекс, получае­мый разбивающим элементом после разбиения; if i-k<l-i then qsort(k,i - 1); qsort(i + 1,l) else qsort(i+ 1,l); qsort{k,i-l) fi

fi.

Быстрая сортировка всего массива является результатом выполнения qsort{l,n).

58

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

§ 8. Функция затрат рандомизированного алгоритма

Определение 8.1. Алгоритмы с элементами случайности, реали­зуемыми обращениями к генераторам случайных чисел, называются рандомизированными.

Рандомизированные алгоритмы можно разделить на вероятност­ные, или, что то же самое, алгоритмы типа Монте-Карло, и алгоритмы типа Лас-Вегас. Первый тип допускает, что ответ, который дает алго­ритм для поставленной задачи с некоторым конкретным входом, может быть неправильным, хотя бы и с малой вероятностью; второй тип — Лас-Вегас—гарантирует правильный ответ, но (как и для алгоритмов типа Монте-Карло) время получения ответа для конкретного входа не определяется, вообще говоря, однозначно этим входом^г. Исключая специально оговариваемые редкие случаи, мы будем рассматривать только алгоритмы типа Лас-Вегас, не упоминая этого каждый раз.

Анализ сложности рандомизированного алгоритма сводится к на­хождению математических ожиданий некоторых случайных величин. Но ситуация здесь отличается от той, когда множество входов фик­сированного размера рассматривается как вероятностное простран­ство и затраты алгоритма, однозначно определенные для каждого конкретного входа, становятся случайными величинами на этом про­странстве (мы шли этим путем в двух предыдущих параграфах). При исследовании рандомизированных алгоритмов вероятностное про­странство, на котором рассматриваются случайные величины, состо­ит из сценариев выполнения алгоритма для фиксированного входа, и каждый сценарий определяется тем, какие случайные числа бу­дут сгенерированы в соответствующие моменты выполнения алго­ритма; за каждым таким сценарием закрепляется некоторая вероят­ность. В нашем контексте генератор случайных чисел можно пред­ставлять себе как стандартную функцию random{N) целого положи­тельного аргумента N, результатом выполнения которой является эле­мент множества {0,1, ...,N - 1}, но невозможно предсказать точно, каким именно будет значение этой функции,—любой из элементов указанного множества может появиться с вероятностью 1/N.

Таким образом, затраты рандомизированного алгоритма при фик­сированном входе, вообще говоря, не определяются однозначно, но

¹ Эта классификация является достаточно распространенной в специальной литера­туре по рандомизированным алгоритмам — см., например, книгу [55], — но не един­ственной. Например, в [26, разд. 9.2] рандомизированные алгоритмы подразделяются иначе, а именно — на алгоритмы типа Монте-Карло, типа Лас-Вегас и шервудские. Мы не будем останавливаться на этом.