Вам дан массив из элементов
Задача состоит в том, чтобы чередовать массив, используя алгоритм на месте так, чтобы результирующий массив был похож на
Если бы требования на месте не было, мы могли бы легко создать новый массив и скопировать элементы, используя алгоритм времени .
При наличии требования на месте алгоритм «разделяй и властвуй» увеличивает алгоритм до .
Итак, вопрос:
Существует ли алгоритм времени , который также используется?
(Примечание: вы можете принять модель оперативной памяти WORD с одинаковой стоимостью, поэтому на месте это означает ограничение пространства ).
algorithms
arrays
permutations
in-place
Арьябхата
источник
источник
Ответы:
Вот ответ, который детализирует алгоритм из статьи, на которую ссылается Джо: http://arxiv.org/abs/0805.1598
Сначала рассмотримΘ ( п журналн ) алгоритм , который использует разделяй и властвуй.
1) Разделяй и властвуй
Нам дают
Теперь, чтобы использовать разделяй и властвуй, для некоторогоm = Θ ( n ) мы пытаемся получить массив
и рекурсировать.
Обратите внимание, что частьб1, б2, … Бм,м + 1, ...N является циклическим сдвигом
пом местам.
Это классика, и ее можно сделать на месте тремя разворотами и заO (n) раз.
Таким образом, «разделяй и властвуй» дает вам алгоритмΘ ( п журналн ) с рекурсией, аналогичной T( n ) = 2 Тл( n / 2 ) + Θ ( n ) .
2) Перестановочные циклы
Теперь другим подходом к проблеме является рассмотрение перестановки как множества непересекающихся циклов.
Перестановка дается (при условии, начиная с1 )
Если бы мы каким-то образом точно знали, что это за циклы, используя постоянное дополнительное пространство, мы могли бы реализовать перестановку, выбрав элемент , определить, куда идет этот элемент (используя приведенную выше формулу), поместить элемент в целевое местоположение во временное пространство, поместить элемент в это целевое местоположение и продолжить вдоль цикла. Как только мы закончим с одним циклом, мы переходим к элементу следующего цикла и следуем этому циклу и так далее.A A
Это дало бы нам алгоритм времени , но предполагает, что мы «каким-то образом знали, какими были точные циклы», и пытались вести этот бухгалтерский учет в пределах ограничения пространства это то, что делает эту проблему сложной.O (n) O (1)
Здесь статья использует теорию чисел.
Можно показать, что в случае, когда , элементы в позициях , находятся в разных циклах, и каждый цикл содержит элемент в позиции .2 n + 1 = 3К 1 3 , 32, … , 3к - 1 3м, м ≥ 0
При этом используется тот факт, что является генератором .2 ( Z / 3К)*
Таким образом, когда , подход, основанный на цикле, дает нам алгоритм времени, поскольку для каждого цикла мы точно знаем, с чего начать: степени (включая ) (те, может быть вычислено в пространстве ).2 n + 1 = 3k O (n) 3 1 O (1)
3) Конечный алгоритм
Теперь мы объединяем два вышеупомянутых: делить и завоевывать + циклы перестановок.
Делаем и разделяем, но выбираем так, чтобы была степенью и .м 2 м + 1 3 m = Θ ( n )
Таким образом, вместо рекурсии на обеих «половинках» мы рекурсируем только на одной и делаем дополнительную работу.Θ ( н )
Это дает нам рекуррентность (для некоторого ) и, таким образом, дает нам время, космический алгоритм!T( n ) = T( c n ) + Θ ( n ) 0 < с < 1 O (n) O (1)
источник
Я почти уверен, что нашел алгоритм, который не опирается на теорию чисел или теорию циклов. Обратите внимание, что есть некоторые детали, которые нужно проработать (возможно, завтра), но я вполне уверен, что они сработают. Я не сплю, потому что я пытаюсь скрыть проблемы :)
Позвольте
A
быть первый массив,B
второй,|A| = |B| = N
и предположимN=2^k
для некоторыхk
, для простоты. ПозвольтеA[i..j]
быть подмассиваA
с индексамиi
доj
, включительно. Массивы основаны на 0. ДавайтеRightmostBitPos(i)
вернем (основанную на 0) позицию самого правого бита, который равен '1'i
, считая справа. Алгоритм работает следующим образом.Давайте возьмем массив из 16 чисел, и давайте просто начнем чередовать их, используя свопы, и посмотрим, что произойдет:
Особый интерес представляет первая часть второго массива:
Шаблон должен быть четким: мы поочередно добавляем число в конец и заменяем наименьшее число большим. Обратите внимание, что мы всегда добавляем число, которое на единицу больше, чем наибольшее число, которое у нас уже есть. Если бы мы каким-то образом смогли точно определить, какое число является самым низким в любой момент времени, мы могли бы сделать это легко.
Теперь перейдем к более крупным примерам, чтобы увидеть, можем ли мы увидеть шаблон. Обратите внимание, что нам не нужно фиксировать размер массива для построения приведенного выше примера. В какой-то момент мы получаем эту конфигурацию (вторая строка вычитает 16 из каждого числа):
Теперь это ясно показывает схему: «1 3 5 7 9 11 13 15» - все 2, «2 6 10 14» - все 4, а «4 12» - 8. Поэтому мы можем разработать алгоритм, который говорит нам, каким будет следующее наименьшее число: механизм в значительной степени точно работает как двоичные числа. У вас есть бит для последней половины массива, бит для второй четверти и так далее.
Теперь вопрос: есть ли какой-то шаблон в той части, которую нам нужно отсортировать? Попытка 32 чисел дает нам «16 12 10 14 9 11 13 15» для исправления. Обратите внимание, что у нас точно такая же схема! «9 11 13 15», «10 14» и «12» сгруппированы таким же образом, как мы видели ранее.
Теперь дело в том, чтобы рекурсивно чередовать эти части. Мы чередуем «16» и «12» в «12 16». Мы чередуем «12 16» и «10 14» в «10 12 14 16». Мы чередуем «10 12 14 16» и «9 11 13 15» в «9 10 11 12 13 14 15 16». Это сортирует первую часть.
Пример:
источник
Вот нерекурсивный встроенный в линейное время алгоритм для чередования двух половин массива без дополнительной памяти.
Общая идея проста: пройтись по первой половине массива слева направо, поменяв правильные значения. По мере продвижения все еще используемые левые значения меняются местами, освобожденными правыми значениями. Единственный трюк - выяснить, как вытащить их снова.
Мы начнем с массива размера N, разделенного на 2 почти равные половины.
[ left_items | right_items ]
Поскольку мы обрабатываем это, это становится
[ placed_items | remaining_left_items| swapped_left_items | remaining_right_items]
Пространство подкачки увеличивается по следующей схеме: A) увеличивает пространство, удаляя соседний правый элемент и заменяя новый элемент слева; B) поменяйте местами самый старый элемент с новым элементом слева. Если левые элементы пронумерованы 1..N, этот шаблон выглядит
Последовательность изменения индекса в точности соответствует OEIS A025480 , который можно рассчитать с помощью простого процесса. Это позволяет найти место подкачки, учитывая только количество добавленных элементов, которое также является индексом текущего размещаемого элемента.
Это все, что нам нужно, чтобы заполнить первую половину последовательности за линейное время.
Когда мы доберемся до средней точки, массив будет состоять из трех частей:
[ placed_items | swapped_left_items | remaining_right_items]
если мы сможем расшифровать поменяемые местами, мы уменьшим проблему до половины размера и можем повторить.Чтобы расшифровать пространство подкачки, мы используем следующее свойство: Последовательность, построенная с помощью
N
чередующихся операций append и swap_oldest, будет содержатьN/2
элементы, которым дан их возрастA025480(N/2)..A025480(N-1)
. (Целочисленное деление, меньшие значения старше).Например, если левая половина изначально содержала значения 1..19, то пространство подкачки содержало бы
[16, 12, 10, 14, 18, 11, 13, 15, 17, 19]
. A025480 (9..18) -[2, 5, 1, 6, 3, 7, 0, 8, 4, 9]
это список индексов предметов от самого старого до самого нового.Таким образом , мы можем расшифровывать наше пространство подкачки, продвигая через него и обменивать
S[i]
сS[ A(N/2 + i)]
. Это также линейное время.Оставшееся осложнение заключается в том, что в конечном итоге вы достигнете позиции, где правильное значение должно быть с более низким индексом, но оно уже было заменено. Найти новое местоположение легко: просто выполните расчет индекса еще раз, чтобы определить, куда был заменен элемент. Может потребоваться пройти несколько шагов по цепочке, пока вы не найдете свободное место.
К этому моменту мы объединили половину массива и сохранили порядок неотделенных частей в другой половине с точными перестановками
N/2 + N/4
. Мы можем продолжить через остальную часть массива для общего количестваN + N/4 + N/8 + ....
перестановок, которое строго меньше3N/2
.Как рассчитать A025480:
Это определено в OEIS как
a(2n) = n, a(2n+1) = a(n).
альтернативная формулировкаa(n) = isEven(n)? n/2 : a((n-1)/2)
. Это приводит к простому алгоритму, использующему побитовые операции:Это операция амортизации O (1) по всем возможным значениям для N. (1/2 нужно за 1 смену, 1/4 нужно 2, 1/8 нужно 3, ...) . Существует еще более быстрый метод, который использует небольшую таблицу поиска, чтобы найти позицию младшего значащего нулевого бита.
Учитывая это, вот реализация в C:
Это должен быть довольно дружественный к кэшу алгоритм, поскольку к 2 из 3 местоположений данных обращаются последовательно, а объем обрабатываемых данных строго уменьшается. Этот метод можно превратить из перемешивания в перемешивание, отменив
is_even
тест в начале цикла.источник