Здравствуйте, Аноним, Вы писали:

А>Здравствуйте, вот такой вопрос. Можно реализовать следующий алгоритм за время меньшее чем O(n*log(n)):

А>В массиве целые числа, они неупорядочены. Из него выбираются два наименьших числа, они удаляются из массива. Затем в него добаляется сумма этих двух чисел. Добавляем эту сумму в переменную s. Далее запускаем этот же алгоритм для нового массива. Когда осталось одно число — пишем на экран значение s.

Суммирование по Хаффману? Тогда непонятно, зачем, ещё добавлять "эту сумму в переменную s".

Твой алгоритм имеет сложность не O(N*logN), а O(N^2). Да, если мы единожды отсортируем массив (за O(N*logN)), то выбор минимальных значений — O(1), а поиск точки вставки — O(logN). Но сама вставка требует O(N) времени — сдвиг хвостовой части массива.

Более правильное решение — использовать пирамиду (двоичную кучу, heap) поверх массива, упорядоченную по убыванию.
За O(N*logN) мы превращаем неупорядоченный массив в пирамиду, затем N раз за O(logN) выдёргиваем-выдёргиваем-складываем-запихиваем.

Более подробно о пирамидах — см. Седжвика, Кормена или Кнута.
Если пишешь на C++, то используй STL-ные функции работы с пирамидами — make_heap и т.п.

---

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