Перестановки. Трудоемкость выполнения перестановок с замещением.

Содержание этого раздела не скажется на понимании остального материала. Здесь описывается быстрые алгоритмы выполнения перестановок без использования дополнительной памяти. Пусть перестановка задана функцией (процедурой) , которая по номеру i вычисляет его образ , и требуется переставить элементы массива X в соответствии с указанной перестановкой. При использовании дополнительной памяти в размере массива переставляемых элементов, для выполнения перестановки потребуется n обращений к функции . Если по каким либо причинам размещение двух массивов в памяти не целесообразно (например, ее не хватает), то перестановку приходится проводить на месте расположения исходного массива. В этом случае говорят об алгоритме с замещением. Под трудоемкостью алгоритма, выполняющую перестановку будем понимать число обращений к функции .

Представим перестановку в виде произведения независимых циклов. Каждый цикл определяется последовательностью различных индексов . Приведем программу переставляющую в соответствии с элементы массива X, номера которых образуют один цикл.

i-{первый номер цикла}

j:= (i);

Repeat

a:=X[j];X[j]:=X[i];X[i]:=a;

j:= (j);

until j=i

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

Если такой возможности нет, то можно поступать следующим образом. Выполним сначала цикл, содержащий индекс 1. Затем перейдем к индексу 2 и, не выполняя перестановки, прокрутим цепочку индексов, входящих в цикл, содержащий 2. Если среди просматриваемых значений не встретилось значение 1, то выполним перестановки данного цикла. В противном случае переставлять элементы массива не следует, так как они уже переставлены. Теперь перейдем к индексу 3 и повторим аналогичную процедуру с той лишь разницей, что теперь, прокручивая цепочку индексов, будем проверять, не встретится ли значение меньше трех. Если начинаем с индекса k, то это означает, что все независимые циклы, содержащие индексы меньше k, уже выполнены. Поэтому при просмотре индексов цикла, содержащего индекс k, следует проверять, не встретится ли значение, меньшее k. Описанный алгоритм обозначим через I1.

Самый плохой случай (в смысле трудоемкости) для алгоритма I1 достигается на перестановке (1,2,…,n), на которой его трудоемкость . Тем не менее, во многих случаях поведение этого алгоритма приемлемое.

Теорема.Пусть максимальная длина независимого цикла перестановки равна l. Тогда трудоемкость алгоритма I1 не превосходит .

Доказательство. Пусть перестановка имеет k независимых циклов, длиной . Трудоемкость алгоритма I1 оценивается сверху величиной . При этом выполняются неравенства , и , где . Максимум выпуклой функции на политопе , и , где , достигается на его вершине. Легко проверить, что самое большое значение получается, когда и , , и равно (по определению s справедливо ). Тем самым теорема доказана.

Часто, кроме самой перестановки известна и обратная к ней перестановка . В этом случае порядок просмотра цикла (именно просмотра, а не выполнения) изменим на следующий: Как только будет получен индекс , меньший k, дальше просматривать этот цикл не имеет смысла, поскольку он был выполнен ранее. Возможно, такого индекса не найдется, то есть придется просмотреть весь цикл. В этом случае два последних элемента построенной последовательности будут равны. Обозначим модификацию алгоритма I1, в котором для просмотра циклов используется только что описанный способ, через I2.

Теорема.Пусть максимальная длина независимого цикла перестановки равна l. Тогда трудоемкость алгоритма I2 не превосходит .

Доказательство. Пусть k – наименьший индекс в рассматриваемом цикле. Возьмем произвольный индекс , принадлежащий данному циклу, и посмотрим, сколько имеется цепочек, начинающихся с различных индексов этого же цикла и таких, в которые он мог бы входить. Пусть эти цепочки с началом в при и цепочки с началом при . В цепочке с началом в индекс пред равен и обязательно содержится . Следовательно, выполняются неравенства , и значит , где и . Из неравенств выводим , откуда, учитывая , вытекает , или .

Рассмотрим цепочку с началом . В этой цепочке индекс перед равен . Следовательно, выполняются неравенства , и значит , где , и , где l – длина цикла. Из полученных неравенств выводим , откуда, учитывая , вытекает , или .

Теперь заметим, что принадлежит также цепочке порожденной им самим, и еще цепочке исходящей из k. Таким образом это число может принадлежать самое большее 2+m+r цепочкам, начинающимся в разных элементах данного цикла, и .

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