Каковы правила для «Ω (n log n) барьер» для алгоритмов сортировки?

Question

Я написал простую программу, которая сортирует по O (n). Это неэффективно с точки зрения памяти, но это не главное.

Для сортировки используется принцип HashMap:

public class NLogNBreak {
    public static class LinkedListBack {
        public LinkedListBack(int val){
            first = new Node();
            first.val = val;
        }
        public Node first = null;
        public void insert(int i){
            Node n = new Node();
            n.val = i;
            n.next = first;
            first = n;
        }
    }

    private static class Node {
        public Node next = null;
        public int val;
    }

    //max > in[i] > 0
    public static LinkedListBack[] sorted(int[] in, int max){
        LinkedListBack[] ar = new LinkedListBack[max + 1];
        for (int i = 0; i < in.length; i++) {
            int val = in[i];
            if(ar[val] == null){
                ar[val] = new LinkedListBack(val);
            } else {
                ar[val].insert(val);
            }
        }
        return ar;
    }
}

Значит ли это считать своего рода O (n), даже если он возвращает результат в неформальном формате?

Answer 1

Чтобы прямо ответить на ваш вопрос:

1. Ваш алгоритм сортировки технически не O (n), а скорее O (n + max), так как вам нужно создать массив размером max, который занимает O (max) время.
2. Это не проблема; фактически это частный случай хорошо известного алгоритма сортировки, который преодолевает барьер & Omega; (n log n).

Так что же это за барьер & omega; (n log n)? Откуда это взялось? И как ты это сломаешь?

& Omega; (n log n) Барьер

Барьер & Omega; (n log n) - это теоретически обоснованная нижняя граница для средней скорости любого алгоритма сортировки , основанного на сравнении . Если единственные операции, которые вам разрешено применять к элементам массива для их различения, - это выполнить какое-либо сравнение, тогда ваш алгоритм сортировки не может работать лучше, чем & Omega; (n log n) в среднем случае.

Чтобы понять, почему это так, давайте подумаем о состоянии алгоритма в любой точке его выполнения. Поскольку алгоритм работает, он может получить некоторое количество информации о порядке упорядочения входных элементов. Предположим, что если алгоритм имеет некоторый набор информации X об исходном упорядочении входных элементов, то алгоритм находится в состоянии X.

Суть аргумента & Omega; (n log n) (и нескольких связанных аргументов, о которых я расскажу позже) состоит в том, что алгоритм должен иметь возможность входить в большое количество различных состояний в зависимости от того, что вход есть. Давайте пока предположим, что вход в алгоритм сортировки представляет собой массив из n различных значений. Поскольку алгоритм не может ничего сказать об этих элементах, кроме того, как они упорядочены, не имеет значения, какие значения сортируются. Все, что имеет значение, - это относительное упорядочение этих n элементов относительно друг друга.

Теперь для ключевого шага - давайте предположим, что существует f (n) уникальных способов упорядочения n входных элементов и предположим, что наш алгоритм сортировки не может войти по крайней мере в f (n) различных состояний. Если это так, то должно быть два разных порядка элементов в массиве, которые алгоритм всегда группирует в одно и то же состояние. Если это произойдет, то алгоритм сортировки не сможет правильно отсортировать оба входных массива. Причина этого заключается в том, что, поскольку алгоритм обрабатывает два массива одинаково, любые шаги, которые он использует для переупорядочения элементов первого массива, будут такими же, как шаги, которые он использует для переупорядочения элементов второго массива. Поскольку эти два массива не совпадают, должен быть хотя бы один элемент, который будет неуместен в одном из двух случаев. Следовательно, мы знаем, что алгоритм сортировки должен входить в f (n) различных состояний.

Но как алгоритм может попасть в эти разные состояния? Что ж, давайте подумаем об этом. Первоначально алгоритм не имеет никакой информации о порядке элементов. Когда он делает свое первое сравнение (скажем, между элементами A [i] и A [j]), алгоритм может войти в одно из двух состояний - одно, где A [i] A [j]. В более общем смысле каждое сравнение, которое выполняет алгоритм, в лучшем случае может поместить алгоритм в одно из двух новых состояний, основанных на результате сравнения. Поэтому мы можем думать о большой двоичной древовидной структуре, описывающей состояния, в которых может находиться алгоритм - каждое состояние имеет до двух дочерних элементов, описывающих, в какое состояние входит алгоритм, основываясь на результате проведенного сравнения. Если мы возьмем какой-либо путь от корня дерева до листа, мы получим серию сравнений, которые в конечном итоге будут сделаны алгоритмом для конкретного входа. Чтобы сортировать как можно быстрее, мы хотим сделать как можно меньше сравнений, и поэтому мы хотим, чтобы эта древовидная структура имела наименьшую возможную высоту.

Теперь мы знаем две вещи.Во-первых, мы можем представить все состояния, в которые алгоритм может войти, как двоичное дерево.Во-вторых, это двоичное дерево должно иметь как минимум f (n) различных узлов в нем.Учитывая это, наименьшее возможное двоичное дерево, которое мы можем построить, должно иметь высоту не менее Ω (log f (n)).Это означает, что если существует f (n) различных возможных способов упорядочения элементов массива, мы должны сделать в среднем не менее Ω (log f (n)) сравнений , так как в противном случае мы не можем получитьв достаточно разных состояниях.

Чтобы завершить доказательство того, что вы не можете разбить Ω (n log n), обратите внимание, что если в массиве есть n различных элементов, то существует n!разные возможные способы упорядочения элементов.используя приближение Стирлинга , у нас есть этот лог n!= Ω (n log n), и поэтому для сортировки входной последовательности мы должны сделать не менее Ω (n log n) сравнений в среднем случае.

Исключения из правила

Inто, что мы только что видели выше, мы увидели, что если у вас есть n элементов массива, которые все различны, вы не можете сортировать их с помощью сортировки сравнения быстрее, чем Ω (n log n).Однако это исходное предположение не обязательно верно.Многие массивы, которые мы хотим отсортировать, могут содержать дублирующиеся элементы.Например, предположим, что я хочу отсортировать массивы, состоящие исключительно из нулей и единиц, например, этот массив здесь:

 0 1 0 1 1 1 0 0 1 1 1

В этом случае не верно, чтоэто н!разные массивы нулей и единиц длины n.На самом деле их всего 2 ⁿ .Исходя из нашего результата выше, это означает, что мы должны иметь возможность сортировать за время Ω (log 2 ⁿ ) = Ω (n), используя алгоритм сортировки, основанный исключительно на сравнении.На самом деле, мы абсолютно можем это сделать;Вот пример того, как мы это сделаем:

1. Посмотрите на первый элемент.
2. Скопируйте все элементы, меньшие, чем первый элемент, в массив с именем 'less'
3. Скопировать все элементы, равные первому элементу, в массив с именем «равный»
4. Скопировать все элементы, превышающие первый элемент, в массив с именем «больше»
5. Объединить все три из нихМассивы вместе в следующем порядке: меньше, равно, больше.

Чтобы убедиться, что это работает, если 0 - наш первый элемент, то массив "меньше" будет пустым, массив "равно" будет иметьвсе нули, и в массиве «больший» будут все единицы.Затем их объединение ставит все нули перед всеми.В противном случае, если 1 - наш первый элемент, то массив less будет содержать нули, массив equal будет содержать единицы, а массив greater будет пустым.Таким образом, их конкатенация состоит из всех нулей, за которыми следуют все, что требуется.

На практике вы не будете использовать этот алгоритм (вы будете использовать сортировку отсчета, как описано ниже), но это показывает, что вы можетена самом деле превосходит Ω (n log n) с помощью алгоритма, основанного на сравнении, если число возможных входов в алгоритм невелико.

Известно, что некоторые алгоритмы сортировки, основанные на сравнении, работают очень быстро на входах с множественным дублированиемценности.Например, известно, что Быстрая сортировка со специальным шагом разбиения может использовать дублированные элементы во входном массиве.

Несопоставимые сортировки

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

Например, если вы знаете, что входные значения взяты из юниверса, который имеет только | U | элементы в нем, то вы можете отсортировать в O (N + | U |) времени, используя умный алгоритм. Начните с создания | U | разные сегменты , в которые мы можем поместить элементы из исходного массива. Затем выполните итерацию по всему массиву и распределите все элементы массива в соответствующее ведро. Наконец, посетите каждое из сегментов, начиная с сегмента, содержащего копии наименьшего элемента, и заканчивая блоком, содержащим копии самого большого элемента, а затем объедините все найденные значения. Например, давайте посмотрим, как сортировать массивы, состоящие из значений 1 - 5. Если у нас есть этот начальный массив:

1 3 4 5 2 3 2 1 4 3 5

Затем мы можем поместить эти элементы в ведра следующим образом:

Bucket     1  2  3  4  5
           -------------
           1  2  3  4  5
           1  2  3  4  5
                 3

Итерация по сегментам и объединение их значений дает следующее:

1 1 2 2 3 3 3 4 4 5 5

которая, конечно же, является отсортированной версией нашего исходного массива! Время выполнения здесь - это O (n) время, чтобы пойти и распределить исходные элементы массива в сегменты, затем O (n + | U |) время, чтобы перебрать все сегменты, собрав элементы вместе. Обратите внимание, что если | U | = O (n), это выполняется за O (n) время, преодолевая барьер сортировки & Omega; (n log n).

Если вы сортируете целые числа, вы можете сделать это намного лучше, используя radix sort , который работает в O (n lg | U |). Если вы имеете дело с примитивными int s, lg | U | обычно 32 или 64, так что это очень быстро. Если вы хотите реализовать особенно сложную структуру данных, вы можете использовать Van Emde Boas Tree для сортировки целых чисел от 0 до U - 1 за время O (n lg lg U), снова используя тот факт, что целые числа состоят из групп битов, которыми можно манипулировать в блоках.

Точно так же, если вы знаете, что ваши элементы являются строками, вы можете очень быстро отсортировать их, построив trie из строк, а затем повторив итерацию по всем три, чтобы восстановить все строки. В качестве альтернативы вы можете рассматривать строки как числа, записанные в большой базе (скажем, в базе 128 для текста ASCII), а затем использовать один из целочисленных алгоритмов сортировки сверху.

В каждом из этих случаев причина, по которой вы можете преодолеть теоретико-информационный барьер, заключается в том, что вы нарушаете исходное предположение барьера, а именно то, что вы можете применять только сравнения. Если вы можете рассматривать входные элементы как числа, или как строки, или как что-то еще, что раскрывает большую структуру, все ставки отключены, и вы можете сортировать чрезвычайно эффективно.

Надеюсь, это поможет!

Answer 2

Это называется Radix Sort, и да, оно преодолевает барьер nlog (n), который является только барьером на Comparison Model. На странице википедии, связанной с моделью сравнения, вы можете увидеть список видов, которые ее используют, и несколько, которые ее не используют.

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

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

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