Существуют ли известные алгоритмы сортировки сравнений, которые не сводятся к сеткам сортировки, чтобы каждый элемент сравнивался раз?O(logn)O(logn)O(\log n) Насколько я знаю, единственный способ сортировки по для каждого элемента состоит в том, чтобы построить сеть сортировки AKS для n входов и...
Справочная информация: Чао Сюй некоторое время назад опубликовал следующий вопрос: « Существуют ли какие-либо известные алгоритмы сортировки сравнения, которые не сводятся к сортировке сетей, так что каждый элемент сравнивается раз?O(logn)O(logn)O(\log n) ». Кажется, мы немного застряли в...
Принцип 0-1 говорит, что если сеть сортировки работает для всех последовательностей 0-1, то она работает для любого набора чисел. Существует ли такое, что если сеть сортирует каждую последовательность 0-1 из S, то она сортирует каждую последовательность 0-1, а размер S является полиномиальным по n...
Учитывая входов , мы строим сеть случайной сортировки с воротами, итеративно выбирая две переменные с и добавляя вентиль компаратора, который меняет их, если .x 0 , … , x n - 1 m x i , x j i < j x i > x jnnnx0,…,xn−1x0,…,xn−1x_0, \ldots, x_{n-1}mmmxi,xjxi,xjx_i, x_ji<ji<ji <...
Я заинтересован в следующей проблеме. В качестве входных данных нам дается «целевая перестановка» , а также упорядоченный список индексов i 1 , … , i m ∈ [ n - 1 ] . Затем, начиная со списка L = ( 1 , 2 , … , n ) (т. Е. Перестановки тождеств), на каждом временном шаге t ∈ [ m ] мы меняем элемент i...