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

Question

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

Кажется, что важной частью претензии является то, что

Алгоритм 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); который стабильно сортирует использование Предиката в качестве ключа сортировки с меньшим, чем nlog ₂ n обращений к Предикату, и выполняет только O(N) записи в a?

Answer 1

Я испытываю желание сказать, что это невозможно. Каждый раз, когда вы вычисляете O(n log n) количество информации, но у вас нет (1) негде спрятать ее (постоянное пространство) и (2) негде немедленно ее использовать (O(n) перемещается), происходит нечто странное на, возможно, в связи с интенсивным использованием стека (который не может быть включен в анализ пространства, хотя это должно быть).

Это может быть возможно, если вы храните временную информацию во многих битах одного целого числа или чего-то подобного. (Таким образом, O(1) на практике, но O(log n) в теории.)

Radix-сортировка не вполне может это сделать, потому что вам нужно вызвать предикат для создания цифр, и если вы не запомните транзитивность сравнения, вы будете называть это O(n^2) раз. (Но для того, чтобы запоминать, я думаю, что O(log n) амортизированного пространства на элемент, я думаю.)

QED - доказательство отсутствия фантазии:)

Answer 2

Вот что у меня так далеко. Версия цикла сортировки, которая использует битовый массив для хранения результатов тестов раздела и вычисляет места назначения на лету. Он выполняет стабильный двоичный раздел с N сравнениями, битами выделенного хранилища.

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, используя битовый массив фиксированного размера из B битов. Есть ли способ повторно использовать те же биты при выполнении стабильного слияния?

Answer 3

Разве RadixSort не является?

O (кН)