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

Question

Я представляю проблему, которую показал мой профессор в классе, с моим 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 (п)?

EDIT:

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

Answer 1

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

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

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

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

Update: меня попросили показать , как вы могли бы перейти от выхода (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 

Answer 2

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

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

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

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

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

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

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

Answer 3

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

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

2> траверса через массив и приращение значение ок в положении элемента массива. т.е. если элемент массива является [I], то приращение тк [а [I]]

3) Для представления ответов после каждой операции п-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: некоторые из а [я] отрицательна

 <still to update> 

Answer 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