Здравствуйте, ilnar, Вы писали:

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

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

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

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

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

Мне видится способ получить сложность O(n*log(n)) (а не O(n*n), как было изначально ).
Если сначала отсортировать массив O(n*log(n)). А потом, полученные суммы не вставлять в исходный массив, а дописывать в конец другого массива. При этом придется следить за тем, что два меньших числа нужно выбирать из начал 2-х массивов.