Существует ли алгоритм O (n) для генерации массива без префиксов для массива натуральных чисел? - PullRequest
Новая
       2

Существует ли алгоритм O (n) для генерации массива без префиксов для массива натуральных чисел?

5 голосов
/ 28 марта 2012

Для массива [4,3,5,1,2] мы называем префикс 4 равен NULL, без префикса 4 - 0;префикс 3 равен [4], без префикса 3 - 0, потому что ни один из префиксов не меньше 3;префикс 5 - [4,3], без префикса 5 - 2, потому что 4 и 3 оба меньше 5;префикс 1 равен [4,3,5], без префикса 1 равен 0, поскольку ни один из префиксов не меньше 1;префикс 2 равен [4,3,5,1], без префикса 2 равен 1, потому что только 1 меньше 2

Так для массива [4, 3, 5, 1, 2],мы получаем без префикса арриту [0,0, 2,0,1]. Можем ли мы получить алгоритм O (n) для получения без префикса массива?

Ответы [ 3 ]

1 голос
/ 18 августа 2012

Это не может быть сделано в O(n) по тем же причинам, сортировка сравнения требует O(n log n) сравнения.Число возможных массивов без префиксов составляет n!, поэтому вам нужно как минимум log2(n!) бит информации, чтобы определить правильный массив без префиксов.log2(n!) равно O(n log n), по приближению Стирлинга .

1 голос
/ 18 августа 2012

Предполагая, что входные элементы всегда являются целыми числами фиксированной ширины, вы можете использовать метод, основанный на радикальной сортировке, для достижения линейного времени:

  • L - входной массив
  • X - список индексов L в фокусе для текущего прохода
  • n - это бит, над которым мы сейчас работаем
  • Количество - это число 0 битов в бите n слева от текущего местоположения
  • Y - список индексов подпоследовательности L для рекурсии
  • P - это инициализированный нулем массив, который является выходом (массив без префикса)

в псевдокоде ... 

Def PrefixLess(L, X, n)
    if (n == 0)
       return;

    // setup prefix less for bit n
    Count = 0

    For I in 1 to |X|
        P(I) += Count
        If (L(X(I))[n] == 0)
            Count++;

    // go through subsequence with bit n-1 with bit(n) = 1
    Y = []
    For I in 1 to |X|
        If (L(X(I))[n] == 1)
            Y.append(X(I))

    PrefixLess(L, Y, n-1)

    // go through subsequence on bit n-1 where bit(n) = 0
    Y = []
    For I in 1 to |X|
        If (L(X(I))[n] == 0)
            Y.append(X(I))

    PrefixLess(L, Y, n-1)

    return P

и затем выполнить: 

PrefixLess(L, 1..|L|, 32)
0 голосов
/ 15 августа 2012

Я думаю, что это должно работать, но дважды проверьте детали.Давайте назовем элемент в исходном массиве a [i] и один элемент в массиве префиксов как p [i], где i - i-й элемент соответствующих массивов.

Итак, скажем, мы находимся на [i], и мы уже вычислили значение p [i].Есть три возможных случая.Если a [i] == a [i + 1], то p [i] == p [i + 1].Если a [i] = p [i] + 1. Это оставляет нас в случае, когда a [i]> a [i + 1].В этой ситуации мы знаем, что p [i + 1]> = p [i].

В наивном случае мы возвращаемся через префикс и начинаем считать элементы меньше чем [i].Тем не менее, мы можем сделать лучше, чем это.Сначала узнайте, что минимальное значение для p [i] равно 0, а максимальное - i.Далее рассмотрим случай индекса j, где i> j.Если a [i]> = a [j], то p [i]> = p [j].Если a [i]

Выполняя анализ алгоритма огибающей, он имеет O (n) наилучшую производительность.Это тот случай, когда список уже отсортирован.Наихудший случай, когда он отсортирован.Тогда производительность O (n ^ 2).Средняя производительность будет O (k * n), где k - это количество, которое нужно откатить назад.Я предполагаю, что для случайно распределенных целых чисел k будет маленьким.

Я также уверен, что были бы способы оптимизировать этот алгоритм для случаев частично отсортированных данных.Я бы посмотрел на

Timsort , чтобы узнать, как это сделать.Он использует обнаружение прогона для обнаружения частично отсортированных данных.Таким образом, основная идея алгоритма заключается в том, чтобы один раз просмотреть список и найти прогоны данных.Для восходящих серий данных у вас будет случай, когда p [i + 1] = p [i] +1.Для нисходящих прогонов p [i] = p_run [0], где p_run - первый элемент в прогоне.

...