Учитывая 1 миллиард чисел, мы должны найти самые большие 1 миллион чисел

Question

Я застрял в одном вопросе.

Учитывая 1 миллиард чисел, нам нужно найти самые большие 1 миллион чисел. Один из подходов состоит в том, чтобы отсортировать числа и затем взять первый миллион чисел из числа O (n log n). Предложите алгоритм с ожидаемой O (n) временной сложностью.

Является ли сортировка кучи, которая может сделать это при наличии O (n) сложности?

Answer 1

Общая версия проблемы, которую вы пытаетесь решить, выглядит следующим образом:

Учитывая n чисел, сообщите о наибольшем k из них за (возможно, ожидаемое) время O (n ).

Если вам просто нужно найти верхние k элементов, а порядок не имеет значения, есть умный O (n) -временный алгоритм для этой задачи, основанный на использовании быстрого выбора алгоритмы . В качестве обновления алгоритм выбора принимает в качестве входных данных массив A и число m, затем переупорядочивает массив A так, чтобы m самых маленьких элементов находились в первых m слотах, а оставшиеся элементы занимали большие слоты. Алгоритм быстрого выбора делает это за (ожидаемое) время O (м) и быстр на практике; алгоритм медиана медиан делает это в O (m) наихудшем случае, но на практике медленнее. Хотя эти алгоритмы обычно создаются с точки зрения нахождения наименьших k элементов, они работают так же хорошо, как нахождение наибольших k элементов.

Использование этого алгоритма в качестве подпрограммы Вот как мы можем найти верхние k элементов во времени и пространстве O (m):

Initialize a buffer of 2k elements.
Copy the first k elements of the array into the buffer.

While there are elements remaining in the array:
    Copy the next k of them into the buffer.
    Use a selection algorithm to place the k largest elements
      of the buffer in the first k slots of the buffer.
    Discard the remaining elements of the buffer.

Return the contents of the buffer.

Чтобы понять, почему это работает, обратите внимание, что после каждой итерации l oop мы сохраняем инвариант что в буфере хранится k самых больших элементов из тех, что были замечены до сих пор (хотя и не обязательно в отсортированном порядке). Следовательно, алгоритм идентифицирует верхние k элементов ввода и возвращает их в некотором порядке.

С точки зрения сложности времени - есть O (k) работа по созданию буфера и на всех итерациях l oop мы делаем O (n) копирование элементов в буфер. Каждый вызов алгоритма выбора занимает (ожидаемое) время O (k), и существует O (n / k) вызовов алгоритма для net времени выполнения O (n + k). При условии, что k

Answer 2

Вы можете обычно делать лучше, чем сортировку. Большинство людей решит эту проблему, используя кучу в качестве структуры. Временная сложность построения кучи будет O (n). Но тогда вам придется выполнить миллион операций «pop», временная сложность для каждого из которых составляет O (log n), но вы не делаете полный n pop (в этом случае только n / 1000 pop).

Я говорю, что вы "в общем" можете добиться большего успеха, чем сортировка, потому что большинство алгоритмов сортировки в библиотеках O (n log n). Но есть «сортировка распределения», которая на самом деле O (n + k), где k - количество возможных значений в диапазоне, который вы сортируете, и в зависимости от значения k вы могли бы сделать лучше сортировка.

Обновление

Чтобы включить предложение, сделанное @ p js, создайте «минимальную» кучу с первыми миллионами значений из миллиарда, где поп Операция удаляет минимальное значение из кучи. Затем для следующих 999 000 000 значений проверьте, не превышает ли каждое из них текущее минимальное значение в куче, и если да, извлеките текущее минимальное значение из кучи и введите pu sh новое значение. Когда вы закончите, у вас останутся 1 000 000 самых больших значений.

Answer 3

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

Однако, есть простое O (n ) алгоритм для этого:

1. инициализировать буфер возврата с 1 000 000 пустых ячеек
2. для каждого элемента в вашем списке 1 000 000 000, выполните следующие действия:
3. проверьте каждый из 1 000 000 ячеек в порядке
4. , если число на входе больше, чем число в вашем буфере, меняйте их местами и продолжайте идти
5. , если вы смотрите на пустую ячейку, поместите номер, который вы удерживаете
6. , если вы дойдете до конца списка и удерживаете номер, выбросьте его

Вот пример со списком из 10 вещей, и мы хотите самое большое 5:

Input:  [6, 2, 4, 4, 8, 2, 4, 1, 9, 2]
Buffer: [-, -, -, -, -]
        [6, -, -, -, -] … see a blank, drop the 6
        [6, 2, -, -, -] … 2 < 6, skip, then see a blank, drop the 2
        [6, 4, 2, -, -] … 4 < 6 but 4 > 2, swap out 2, see blank, drop 2
        [6, 4, 4, 2, -] … 4 <= 4,6 but 4 > 2, swap out 2, see blank, drop 2
        [8, 6, 4, 4, 2] … 8 > 6, swap, then swap 6 for 4, etc.
        [8, 6, 4, 4, 2] … 2 <= everything, drop it on the floor
        [8, 6, 4, 4, 4] … 4 <= everything but 2, swap, then drop 2 on floor
        [8, 6, 4, 4, 4] … 1 <= everything, drop it on the floor
        [9, 8, 6, 4, 4] … 9 > everything, swap with 8 then drop a 4 on the floor
        [9, 8, 6, 4, 4] … 2 <= everything, drop it on the floor

Вы делаете 1 000 000 сравнений и, возможно, до 1 000 000 свопов для каждого элемента на входе (рассмотрите вход в отсортированном порядке возрастания). Это означает, что вы выполняете работу, пропорциональную 1 000 000 * n, линейный объем работы в размере ввода n.