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

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

S>>Спасибо, только не понимаю, почему мой алгоритм имеет сложность O(n*n), выбор минимума производится n раз за log(n) времени, используется выбор минимума методом дерева. Вроде O(n*log(n)). А насчёт деревьев, в интернете есть описание всех этих функций и алгоритмов? Я в Borland C++ 3.2 работаю, буду сам всё реализовывать.

К>Где же там "метод дерева"?
К>У тебя неупорядоченный массив. Ты его разбиваешь примерно пополам, в каждой из половинок рекурсивно ищешь минимум, а затем берёшь минимум из двух результатов.
К>Теперь внимание, вопрос: сколько всего элементов массива ты читаешь? Ответ: все!!!
К>Да, глубина рекурсии — логарифм. Так ведь просто сканирование массива имеет глубину 1.

S>>А насчёт перестановки мест слагаемых, там результатом не будет сумма всех элементов, кто не верит — пусть подумает на досуге, почему. Если бы всё было так просто!

К>Ну я предположил, что это была ошибка в условии. Потому что есть очень похожая практическая задача — суммирование по Хаффману. А какой смысл у твоей задачи?

К>И тем не менее, решение с использованием пирамиды остаётся в силе.

Смысл тот,то здесь нужно сложить n чисел так, чтобы сумма всех промежуточных результатов была наименьшей. По индукции доказывается, что метод, описаный ранее даёт требуемый результат.

Если верить Вашей оценке, то алгоритм рекурсивной сортировки Хоара тоже работает за
O(n*n) операций, там также сканируется весь массив. Но он работает за O(n*log(n)) операций... Странно, или может я не так мыслю. Если мой алгоритм не верен, помогите мне реализовать поиск наименьшего элемента методом дерева за O(log(n)) операций. Метод дерева: весь массив разбиваем на пары, в кажой паре берём наименьший элемент, далее действуем так же, пока не останется один элемент(мой алгоритм делает то же самое, нашёл я его в книжке "Программирование — теоремы и задачи" А. Шеня, там задача — найти минимум за log(n) операций, используя метод дерева).