Какой алгоритм может выполнять стабильное двоичное разбиение на месте только с движением O (N)?
Я пытаюсь понять эту статью: Стабильное минимальное разбиение пространства
в линейном времени.
Похоже, что критическая часть претензии заключается в том, что
Алгоритм B сортирует стабильно бит-массив размера n в O (nlog 2 n) время и постоянное дополнительное пространство, но делает только O (n).
Однако документ не описывает алгоритм, но только ссылается на другой документ, к которому у меня нет доступа. Я могу найти несколько способов сделать сортировку в пределах временных интервалов, но у меня возникли проблемы с поиском того, что гарантирует движение O (N), не требуя также больше, чем постоянное пространство.
Что это за алгоритм B? Другими словами, данный
boolean Predicate(Item* a); //returns result of testing *a for some condition
существует функция B(Item* a, size_t N);
, которая стабильно сортирует использование Predicate в качестве ключа сортировки с менее чем nlog 2 n вызовами Predicate и выполняет только O (N) запись в файл?
Ответы
Ответ 1
Я испытываю соблазн сказать, что это невозможно. Каждый раз, когда вы вычисляете O (n log n) количество информации, но имеете (1) нигде не записывать его (постоянное пространство) и (2) нигде не использовать его сразу (O (n) движется), есть что-то странное (возможно, это связано с интенсивным использованием стека (которое не может быть включено в анализ пространства, хотя оно должно быть).
Возможно, если вы храните временную информацию во многих битах только одного целого числа или что-то вроде этого. (So O (1) на практике, но O (log n) в теории.)
Сортировка Radix не будет делать это, потому что вам нужно будет вызвать предикат для создания цифр, и если вы не будете запоминать транзитивность сравнения, вы назовете его O (n ^ 2) раза. (Но для memoize, я думаю, это занимает O (log n) амортизированное пространство на элемент.)
QED - Доказательство из-за отсутствия воображения:)
Ответ 2
Вот что я до сих пор. Версия циклическая сортировка, в которой используется <бит href= "http://en.wikipedia.org/wiki/Bit_array" rel= "nofollow" > бит массива результат тестов разделов и вычисляет назначения "на лету". Он выполняет стабильное двоичное разбиение с N сравнениями, N свопов и ровно 2N бит выделенного хранилища.
int getDest(int i, BitArray p, int nz)
{ bool b=BitArrayGet(p,i);
int below = BitArrayCount1sBelow(p,i); //1s below
return (b)?(nz+below):i-below;
}
int BinaryCycleSort(Item* a, int n, BitArray p)
{
int i, numZeros = n-BitArrayCount1sBelow(p,n);
BitArray final = BitArrayNew(n);
for (i=0;i<numZeros;i++)
if (!BitArrayGet(final,i))
{ int dest= GetDest(i,p,numZeros);
while (dest!=i)
{ SwapItem(a+i,a+dest);
BitArraySet(final,dest);
dest = getDest(dest,p,numZeros);
}
BitArraySet(final,dest);
}
return numZeros;
}
int BinaryPartition(Item* a, int n, Predicate pPred)
{
int i;
BitArray p = BitArrayNew(n);
for (i=0;i<n;i++)
if (pPred(a+i)) BitArraySet(p,i);
return BinaryCycleSort(a,n,p);
}
с помощью этих помощников:
typedef uint32_t BitStore;
typedef BitStore* BitArray;
BitArray BitArrayNew(int N); //returns array of N bits, all cleared
void BitArraySet(BitArray ba, int i); //sets ba[i] to 1
bool BitArrayGet(BitArray ba, int i); //returns ba[i]
int BitArrayCount1sBelow(BitArray ba, int i) //counts 1s in ba[0..i)
Очевидно, это не постоянное пространство. Но я думаю, что это может быть использовано как строительный блок для достижения конечной цели. Весь массив можно разделить на блоки N/B, используя бит BitArray из бит B фиксированного размера. Есть ли способ повторно использовать те же самые биты при выполнении стабильного слияния?
Ответ 3
Не RadixSort?
О (кН)