Какой алгоритм может выполнять стабильное двоичное разбиение на месте только с движением O (N)?

Я пытаюсь понять эту статью: Стабильное минимальное разбиение пространства в линейном времени.

Похоже, что критическая часть претензии заключается в том, что

Алгоритм B сортирует стабильно бит-массив размера n в O (nlog ₂ 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 ₂ 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?

О (кН)