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

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

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

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

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

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

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

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

коллега, не мудри
давай по другому задачу поставлю:
m1+m2+...+mN
изменится ли конечная сумма, если слагаемые переставить?

ответ подсказать?
нет, т.к. все операции линейны!!!!
а в той задачи идет сложение, в качестве перестановки предлагаается порядок их выбора