Я представляю проблему, которую показал мой профессор в классе, с моим решением 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
- наименьшие элементы в текущий список.