Извлечение 2 чисел n раз и возврат обратно в O (n) вместо O (n * log (n))

Я представляю проблему, которую показал мой профессор в классе, с моим решением O (n * log (n)):

Учитывая список номеров n, мы хотели бы выполнить следующие n-1 раз:

  • Извлеките из списка два минимальных элемента x,y и представим их
  • Создайте новый номер z, где z = x+y
  • Поместите z обратно в список

Предложите структуру данных и алгоритм для O(n*log(n)) и O(n)

Решение:

Мы будем использовать минимальную кучу:

Создание кучи за один раз займет только O (n). После этого извлечение двух минимальных элементов займет O (log (n)). Размещение z в куче принимало бы O (log (n)).

Выполнение вышеуказанных n-1 раз займет O (n * log (n)), так как:

O(n)+O(n∙(logn+logn ))=O(n)+O(n∙logn )=O(n∙logn )

Но как я могу это сделать в O (n)?

EDIT:

Говоря: "извлеките из списка минимальные элементы x,y и их), я имею в виду printf("%d,%d" , x,y), где x и y - наименьшие элементы в текущий список.

Ответы

Ответ 1

Это не полный ответ. Но если список был отсортирован, тогда ваша проблема будет легкой в ​​ O(n). Чтобы сделать это, упорядочьте все числа в связанном списке. Ведите указатель на голову и где-то посередине. На каждом шаге выньте два верхних элемента из головы, распечатайте их, продвиньте средний указатель до тех пор, пока он не появится, и вставьте сумму.

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

В общем случае вы не можете сортировать во времени O(n), но есть ряд особых случаев, в которых вы можете. Поэтому в некоторых случаях это выполнимо.

Общий случай, разумеется, не разрешима во времени O(n). Почему нет? Потому что, учитывая ваш результат, со временем O(n) вы можете запускать выходные данные программы, составлять список попарных сумм по порядку и отфильтровывать их из вывода. Остается элемент исходного списка в отсортированном порядке. Это даст общий алгоритм сортировки O(n).

Обновление: меня попросили показать, как вы могли перейти от выхода (10, 11), (12, 13), (14, 15), (21, 25), (29, 46) к списку ввода? Фокус в том, что вы всегда держите все в порядке, тогда вы знаете, как выглядеть. При положительных целых числах следующая предстоящая сумма будет всегда находиться в начале этого списка.

Step 0: Start
  input_list: (empty)
  upcoming sums: (empty)

Step 1: Grab output (10, 11)
  input_list: 10, 11
  upcoming_sums: 21

Step 2: Grab output (12, 13)
  input_list: 10, 11, 12, 13
  upcoming_sums: 21, 25

Step 3: Grab output (14, 15)
  input_list: 10, 11, 12, 13, 14, 15
  upcoming_sums: 21, 25, 29

Step 4: Grab output (21, 25)
  input_list: 10, 11, 12, 13, 14, 15
  upcoming_sum: 29, 46

Step 5: Grab output (29, 46)
  input_list: 10, 11, 12, 13, 14, 15
  upcoming_sum: 75

Ответ 2

Это невозможно в общем случае.

В заявлении о проблеме говорится, что вы должны уменьшить свой массив до одного элемента, выполнив в общей сложности операции сокращения n-1. Поэтому число выполняемых восстановительных операций составляет порядка O (n). Для достижения общего времени работы O (n) каждая операция сокращения должна выполняться в O (1).

Вы четко определили свою операцию сокращения:

  • удалите 2 минимальных элемента в массиве и напечатайте их, затем
  • вставить сумму этих элементов в массив.

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

Здесь есть некоторые исключения. Если ваши числа являются целыми числами, вы можете использовать "вставку радикса" для достижения вставок O (1). Если ваш массив чисел достаточно разрежен в числовой строке, вы можете вывести точки вставки в O (1). Существует множество других исключений, но все они являются исключениями.

Этот ответ не отвечает на ваш вопрос сам по себе, но я считаю, что он достаточно уместен, чтобы гарантировать ответ.

Ответ 3

Если диапазон значений меньше n, то это можно решить в O (n).

1 > Создайте массив mk размера, равный диапазону значений, и инициализируйте его на все ноль

2 > пересечь массив и значение приращения mk в позиции элемента массива.  Если элемент массива является [i], то приращение mk [a [i]]

3) Для представления ответов после каждого из операций n-1 выполните следующие шаги:

Есть два случая:

Случай 1: все из [i] положительны

        traverse through mk array from 0 to its size
        cnt = 0
        do this till cnt doesn't equal 2
          grab a nonzero element decrease its value by 1 and increment cnt by 1
        you can get two minimum values in this way
        present them 
        now do mk[sum of two minimum]++

Случай 2: некоторые из [i] отрицательны

        <still to update>

Ответ 4

O (nlogn) легко - просто используйте кучу, treap или skiplist.

O (n) звучит жестко.

https://en.wikipedia.org/wiki/Heap_%28data_structure%29
https://en.wikipedia.org/wiki/Treap
https://en.wikipedia.org/wiki/Skip_list