Представление перестановок в виде таблицы инверсий.

{1} if f[j] > k then r[k] :=r[k]+1

end

end;

Временная сложность этого алгоритма фактически определяется числом выполнения {1}, которое равно n(n-1)/2, т. е. является О(n²).

Рассмотрим теперь алгоритм восстановления перестановки в естественной форме по его таблице инверсий. Здесь возможны два похода.

1. Будем последовательно, начиная с единицы и кончая n, расставлять элементы перестановки на свои места. Вначале всем вставляемым элементам перестановки соответствуют нулевые значения. Тогда для того чтобы определить место элемента i, достаточно перед ним оставить r_i нулей для элементов со значениями, большими i. Реализация этого подхода на языке Паскаль выглядит так:

type P = array [1..0] of 1..n;

end;

Заметим, что временная сложность этого алгоритма определяется числом выполнения оператора {1} и равна O(n²), т. е. алгоритм TABOUT2 несколько эффективней алгоритма TABOUT1, хотя его вычислителная сложность того же порядка.

Уражнение. Модернизируйте алгоритм TABOUT2 так, чтобы вспомогательный массив с совместить с массивам f.

Рассмотренные TABIN и TABOUT1, TABOUT2 имеют временную сложность O(n²). Возникает естественный вопрос, существует ли алгоритм, аналогичный по действию, например, алгоритму TABIN, но имеющий лучшую временную сложность. Для того чтобы прояснить возникающие здесь проблемы, рассмотрим близкие к исследуемым понятия, связанные с алгоритмами линейного упорядочивания значений элементов (сортировки).

Пусть задан некоторый массив X, например,

X : array [1..n] of real;

При этом для упрощения рассуждений будем считать, что все значения элементов Х различны между собой. Тогда задача упорядочивания (например в порядке возрастания значений) может быть интерпретирована как поиск перестановки f = <a₁ … a_n>, где a_k – порядковый номер элемента X[k] после упорядочивания, 1£k£n. Для любого элемента X[k] можно определить следующие числа:

b[k] (b`[k]) – число элементов Х, больших (меньших) X[k]

и расположенных перед ним;

c[k] (c`[k]) – число элементов Х, больших (меньших) X[k]

и расположенных после него;

Например, X = -2.5 1.3 1.0 -0.8 0.3 -5.0

f = <2 6 5 3 4 1>

b = 0 0 1 2 2 5

b`= 0 1 1 1 2 0

c = 4 0 0 1 0 0

c`= 1 4 3 1 1 0

Нетрудно показать, что для любого k, 1£k£n, определены следующие соотношения:

(1) b`{k} + c`[k] + 1 = f[k]

(2) b{k} + c[k] + 1 = n-f[k]

(3) b{k} + b`[k] + 1 = k

(4) c{k} + c`[k] + 1 = n-k

Из соотношений (3), (4) следует: если по массиву Х определены таблицы b, c, то легко вычислить таблицы b`, c`, и обратно. Из соотношений (1), (2) следует: если вычислены b` и c` (либо b и c), то легко построить таблицу f.

По характеру своего числа b, b`, c, c` весьма близки к числам r, r`, q, q`, определенным для перестановок. Рассмотрим вопрос, какова может быть временная сложность при вычислении по массиву Х таблиц, например, b`и c`?

Пусть A(b`,c`) – временная сложность наиболее эффективных алгоритмов вычисления b` и c`, а A(f) – временная сложность наиболее эффективных алгоритмов вычисления f; тогда, так как f линейно зависит от b` и c`, то A(b`,c`)/ A(f) =O(1).

Из теории сортировки известно, что если не задана дополнительная информация о структуре значений элементов массива, то наиболее эффективные алгоритмы сортировки имеют временную сложность O(n×log₂n). Это следует, например, из следующих рассуждений. В зависимости от исходных значений элементов Х ему может соответствовать любая из n! Возможных перестановок f. Фактически алгоритм сортировки может быть интерпретирован как поиск соответствующей ему перестановки f из множестваS_n, элементы которого упорядочены некоторым образом. Но наиболее эффективный алгоритм поиска индекса элемента в упорядоченном массиве размерностью k – это бинарный поиск, временная сложность которого O(log₂k). То есть поиск конкретной перестановки из n! упорядоченных перестановок оценивается минимальной временной сложностью O(log₂n!).

Упражнение. Докажите равенство O(log₂n!) = O(n×log₂n).Указание. Воспользуйтесь неравенством n×ln(n)-n+1 < ln(n!) < (n+1)×ln(n)-n+1, n>1, которое доказывается индукцией по n.

Таким образом, для произвольного массива Х наиболее эффективные алгоритмы вычисления таблиц b` и c` не могут иметь временную сложность лучшую, чем O(n×log₂n).

Возвратимся к алгоритмам построения таблицы инверсий для заданной перестановке f. Приведенные рассуждения наводят на мысль поиска подобного алгоритма сложностью O(n×log₂n). Действительно, такой алгоритм существует. Однако его построение требует привлечение новых идей, которые в данных методических указаниях не рассматривались. Можно показать, что алгоритмы с временной сложностью O(n×log₂n) являются наиболее эффективными алгоритмами построения таблицы инверсий. Такое доказательство строится на построении модели, в которой инверсиям соотвествуют некоторые операции, и эту модель характеризуют O(n!) состояний. Однако этот материал явно выходит за рамки данных методических указаний.

Перейдем к рассмотрению алгоритмов выполнения операций суперпозиции, вычисления обратной и четности для перестановок, заданных в виде таблицы инверсий. Наиболее простой из них – определение четности перестановки. В самом деле, непосредственно из определения таблицы инверсий следует, что перестановка четна, если сумма всех ее элементов таблицы инверсий четна, и нечетна в противном случае.

Упражнение. Напишите булевскую функцию с заголовком

end;

Комментарий. Для каждого столбца k матрицы инверсий алгоритм последовательно подсчитывает число единиц, расположенных в этом столбце. Перебор строк матрицы организован циклом {2}, а столбцов – с помощью вспомогательного массива next и ограничен числом инверсий в текущей строке. Для исключения столбцов, в которых ‘·’ расположена текущей строки, осуществляется корректировка значений массива next. В начальный момент всем значениям элементов массива next присваивается ссылка на следующий элемент {3}, а при достижении точки в данной строке ссылка на текущий столбец исключается из списка (оператор {4}). Переменные s и k хранят значения индексов предыдущего и текущего столбца соответственно.

Временная сложность алгоритма O3 оценивается числом выполнения оператора {1}, равного числу инверсий перестановки f. Ее порядок O(n²).

Упражнение. Протестируйте алгоритм O3 на перестановки, рассмотренной в предыдущем примере.

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

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

Подобная схема алгоритма имеет временную сложность O(n²). Улучшенные варианты этой схемы реализации (за счет более эффективных схем перевода из одной формы в другие) имеют временную сложность O(n×log₂n).

В качестве упражнения, являющегося скорее исследованием, предлагается ответить на следующие вопросы. Существует ли более эффективная реализация алгоритма суперпозиции для перестановок, представленных в виде таблиц инверсий? Можно ли, ‘непосредственно’ преобразуя исходные таблицы исходных данных, получить таблицу результата?

В этой теме были рассмотрены представления перестановок: в естественной форме, разложением на циклы (с разметкой начала циклов и каноническое) и таблицей инверсий. Над перестановками рассматривались операции суперпозиции, вычисления обратной и определения четности. В зависимости от внутреннего представления, выполнение этих операций существенно различно и имеет различные характеристики временной сложности. Однако с точки зрения пользователя (например, алгебраиста, решающего на ЭВМ свою конкретную задачу, описанную в терминах этих операций) совершенно безразлично, в каком представлении будут выполняться эти операции. Для него перестановки выступают как некоторый абстрактный тип данных, характеризующийся только тем, что отличает одну перестановку от другой, и возможностью выполнения указанных операций. Такое выделение понятия абстрактного типа данных методически весьма оправдано – оно позволяет пользователю описывать решение своей задачи в наиболее естественной и удобной форме, а проблему внутреннего представления этих типов данных либо оставить на более позднее время, либо передать другому специалисту, лучше знакомому с представлением данных на ЭВМ.

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

Не нашли, что искали? Воспользуйтесь поиском по сайту: