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

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

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

предлагаю алгоритм короче, за O(n) — сложить все числа
доказательство очевидно