Скажем, у меня есть массив A с n уникальными элементами на диапазоне [0, n). Другими словами, у меня есть перестановка целых чисел [0, n).
Возможно преобразование A в B с использованием O (1) дополнительного пространства (AKA на месте), так что B [A [i]] = i?
Например:
A B
[3, 1, 0, 2, 4] -> [2, 1, 3, 0, 4]
Да, возможно, с O (n ^ 2) алгоритмом времени:
Возьмите элемент с индексом 0, а затем напишите 0 в ячейку, проиндексированную этим элементом. Затем используйте только перезаписанный элемент, чтобы получить следующий индекс и записать там прежний индекс. Продолжайте, пока не вернетесь к индексу 0. Это алгоритм лидера цикла.
Затем сделайте то же самое, начиная с индекса 1, 2,... Но прежде чем делать какие-либо изменения, выполняйте алгоритм лидера цикла без каких-либо изменений, начиная с этого индекса. Если этот цикл содержит индекс ниже начального индекса, просто пропустите его.
Или этот O (n ^ 3) алгоритм времени:
Возьмите элемент с индексом 0, а затем напишите 0 в ячейку, проиндексированную этим элементом. Затем используйте только перезаписанный элемент, чтобы получить следующий индекс и записать там прежний индекс. Продолжайте, пока не вернетесь к индексу 0.
Затем сделайте то же самое, начиная с индекса 1, 2,... Но прежде чем делать какие-либо изменения, выполните алгоритм лидера цикла без каких-либо изменений, начиная со всех предыдущих индексов. Если текущий индекс присутствует в любом предыдущем цикле, просто пропустите его.
Я написал (немного оптимизирован) реализация алгоритма O (n ^ 2) в С++ 11, чтобы определить, сколько дополнительных запросов требуется для каждого элемента на если случайная перестановка инвертирована. Вот результаты:
size accesses
2^10 2.76172
2^12 4.77271
2^14 6.36212
2^16 7.10641
2^18 9.05811
2^20 10.3053
2^22 11.6851
2^24 12.6975
2^26 14.6125
2^28 16.0617
Пока размер растет экспоненциально, количество обращений к элементу растет почти линейно, поэтому ожидаемая временная сложность для случайных перестановок - это что-то вроде O (n log n).
Инвертирование массива A требует от нас найти перестановку B, которая удовлетворяет требованию A[B[i]] == i для всех i.
Чтобы построить обратное на месте, мы должны поменять элементы и индексы, установив A[A[i]] = i для каждого элемента A[i]. Очевидно, что если бы мы просто перешли через A и выполнили вышеупомянутую замену, мы могли бы переопределить предстоящие элементы в A, и наши вычисления потерпят неудачу.
Поэтому мы должны поменять элементы и индексы на циклы A, следуя c = A[c], пока не достигнем нашего начального индекса цикла c = i.
Каждый элемент из A принадлежит одному из таких циклов. Поскольку у нас нет места для хранения, если элемент A[i] уже обработан и должен быть пропущен, мы должны следовать его циклу: если мы достигнем индекса c < i, мы бы знали, что этот элемент является частью ранее обработанный цикл.
Этот алгоритм имеет худшую временную сложность O (n²), среднюю сложность во времени O (n log n) и лучшую Сложная временная сложность O (n).
function invert(array) {
main:
for (var i = 0, length = array.length; i < length; ++i) {
// check if this cycle has already been traversed before:
for (var c = array[i]; c != i; c = array[c]) {
if (c <= i) continue main;
}
// Replacing each cycle element with its predecessors index:
var c_index = i,
c = array[i];
do {
var tmp = array[c];
array[c] = c_index; // replace
c_index = c; // move forward
c = tmp;
} while (i != c_index)
}
return array;
}
console.log(invert([3, 1, 0, 2, 4])); // [2, 1, 3, 0, 4]