Здравствуйте, Кодт, Вы писали:
К>Здравствуйте, Аноним, Вы писали:
А>>Здравствуйте, вот такой вопрос. Можно реализовать следующий алгоритм за время меньшее чем 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 и т.п.
К>
К>Да, кстати, если у кого возникает вопрос о перемене мест слагаемых. Для чисел с плавающей точкой и конечной разрядностью это несправедливо.
Спасибо, только не понимаю, почему мой алгоритм имеет сложность O(n*n), выбор минимума производится n раз за log(n) времени, используется выбор минимума методом дерева. Вроде O(n*log(n)). А насчёт деревьев, в интернете есть описание всех этих функций и алгоритмов? Я в Borland C++ 3.2 работаю, буду сам всё реализовывать.
А насчёт перестановки мест слагаемых, там результатом не будет сумма всех элементов, кто не верит — пусть подумает на досуге, почему. Если бы всё было так просто!
