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

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

Выбор наименьшего можно сделать за O(log(n)) операций, кроме того эта функция запускается n-1 раз, n — длина массива. Всего O(log(n))*(n-1)=O(n*log(n)). Логика вроде верная, но скорости не хватает. Может я что то не так понял? Помогите мне разобраться.

Вот моя функция выбора минимума(метод дерева), если найдёте ошибку(вдруг она есть) — буду очень благодарен:

long min(long* m, long l, long r)
{
 long p;
 long i;
 long a1, a2;
 if(l == r) return l;
 else {
  p = int((l+r)/2);
  a1 = min(m, l, p);
  a2 = min(m, p+1, r);
 }
 if(m[a1]<m[a2]) return a1;
 else return a2;
}

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

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

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

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

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

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

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

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

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

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

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

Здравствуйте, 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
изменится ли конечная сумма, если слагаемые переставить?

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

Здравствуйте, 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-х массивов.

ой, извиняюсь, я неточно понял
озадачили меня

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

А>Здравствуйте, вот такой вопрос. Можно реализовать следующий алгоритм за время меньшее чем 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*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 работаю, буду сам всё реализовывать.

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

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

К>Суммирование по Хаффману? Тогда непонятно, зачем, ещё добавлять "эту сумму в переменную s".

---

Чтобы у не возникал вопрос, почему нельзя все числа просто сложить.

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

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

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

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

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

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

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

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

А что, в BC++3 нет STL ? Вот это новость.

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

К>А что, в BC++3 нет STL ? Вот это новость.

Родной нет. Только если исхитриться STLPort прикрутить, но не уверен, что получится. Насколько я помню, у BC3 с шаблонами как-то не очень.

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

К>Здравствуйте, 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) операций, используя метод дерева).

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

К>>А что, в BC++3 нет STL ? Вот это новость.

L>Родной нет. Только если исхитриться STLPort прикрутить, но не уверен, что получится. Насколько я помню, у BC3 с шаблонами как-то не очень.

Печально...
Ну что же, ничего страшного. Где компилятор не пройдёт и бронепоезд не промчится, там копипаст произойдёт и всё прекрасно получИтся
Берём алгоритмы std::push_heap, std::pop_heap, вручную подставляем туда типы, и — вуаля.

Или берём Седжвика и пишем собственные реализации.

double data[N];
double s = 0;

int n;

// фактически, это вызов make_heap
for(n=0; n<=N; ++n)
  push_heap(data,data+n); // последовательно запихнули в кучу все элементы

for(n=N; n>1; --n)
{
  pop_heap(data,data+n);         // выпихнули data[n-1]
  pop_heap(data,data+n-1);       // выпихнули data[n-2]
  s += (data[n-2] += data[n-1]); // нашли их сумму (и заодно прибавили к s), положили в data[n-2]
  push_heap(data,data+n-1);      // запихали сумму обратно в кучу
}

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

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

1. В принципе невозможно найти минимальное значение из N неупорядоченных элементов за время, меньшее чем O(N). Хотя бы по 1 разу нужно каждый элемент посетить. Хоть деревом, хоть тушкой, хоть чучелком.

2. Quicksort (сортировка Хоара) здесь не при чём. Если ты работаешь с упорядоченным массивом (единожды потратившись на его сортировку), то поиск минимума мгновенный; зато каждый раз, совершая вставку в массив, двигаешь в среднем N/2 элементов.

3. Для твоей задачи нужен контейнер "очередь с приоритетами".
Ведь, если отвлечься от способа хранения данных, алгоритм сводится к

priority_queue pq;
// первоначальное заполнение
for(i=0; i<N; ++i) push_pq(pq, data[i]);

// сложение
for(i=0; i<N-1; ++i) // повторять N-1 раз
{
  pair  = pop_minimum_from_pq(pq);
  pair += pop_minimum_from_pq(pq);
  s += pair;
  push_pq(pq, pair);
}
// полная сумма - последний элемент в очереди
total = pop_pq(pq);

Очевидно, очередь можно сделать на
— несортированном массиве: вытаскивание минимума сводится к его линейному поиску (и линейному сдвигу всех остальных), вставка — дописывание в конец
— массиве, сортированном по убыванию: вытаскивание — вытаскивание из конца, вставка — логарифмический поиск позиции и линейный сдвиг
— пирамиде: и вытаскивание, и вставка логарифмические

Кстати, пирамидальная сортировка (запихать всё в пирамиду, а затем всё оттуда повытаскивать) в среднем вдвое медленнее быстрой, но зато — заведомо линейно-логарифмическая (в то время как быстрая в худшем случае — квадратичная).

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

Чтобы с этим побороться, нужно (в STL) передавать туда предикат — std::greater<double>().
Ну или, если пишем руками, то вместо < использовать >

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

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

Кстати, у сложения по Хаффману — ровнёхонько тот же смысл (там, правда, упорядочиваются по абсолютному значению).
Чем меньше абсолютные значения слагаемых, тем меньше ошибка округления у суммы.

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

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

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

К>Кстати, у сложения по Хаффману — ровнёхонько тот же смысл (там, правда, упорядочиваются по абсолютному значению).
К>Чем меньше абсолютные значения слагаемых, тем меньше ошибка округления у суммы.

В моей задаче все числа положительные, так что смысл абсолютно тот же.

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


S>Если верить Вашей оценке, то алгоритм рекурсивной сортировки Хоара тоже работает за
S>O(n*n)
Именно так. Другой вопрос, что, строго говоря,использование O-нотации здесь не совсем уместно, потому что во-первых, O-большое задает только 1 границу роста и если алгоритм имеет эффективность O(n*log n), то он же имеет эффективность O(n^2).
Во-вторых, когда говорят, что сложность быстрой сортировки составляет n*log n, имеют ввиду средний случай, в случае же поиска минимума, любой случай худший, поскольку каждый элемент может оказаться минимумом и соответственно пока ты не просмотришь все элементы, ты не узнаешь какой из них минимальный.

S>Спасибо, только не понимаю, почему мой алгоритм имеет сложность O(n*n), выбор минимума производится n раз за log(n) времени,
Как можно выбрать наименьшее из N чисел не просмотрев их все? (т.е. меньше чем за N операций)?

Случаем не с olympiads.ru задача, ? Торопись — времени почти не осталось. Для решения задачи, как тебе уже правильно подсказали, надо использовать кучу (heap). Только забей на STL, она поработила разум многих! Делов-то тут несколько строчек:

int N;
int a[N]; // массив из N элементов

// функция номер раз - проталкивание вниз

void push_down(int idx)
{
    while(true)
    {
        int lc = 2 * idx + 1;
        int rc = lc + 1;

        int least = idx;
        if(lc < N && a[lc] < a[least])
            least = lc;
        if(rc < N && a[rc] < a[least])
            least = rc;

        if(least == idx)
            break;

        int t    = a[least];
        a[least] = a[idx];
        a[idx]   = t;

        idx = least;
    }
}

// функция номер двас - проталкивание вверх

void push_up(int idx)
{
    while(true)
    {
        int p = (idx - 1) / 2;

        if(idx == 0 || a[p] <= a[idx])
            break;

        int t  = a[p];
        a[p]   = a[idx];
        a[idx] = t;

        idx = p;
    }
}

// функция номер трис - делает из массива хип

void make_heap()
{
    for(int i = N / 2 - 1; i >= 0; i--)
        push_down(i);
}

// вынимает наименьший элемент и восстанавливает хип

int pop_min()
{
    int val = a[0];
    a[0]    = a[--N];
    push_down(0);

    return val;
}

// вставляет элемент и восстанавливает хип

void insert(int val)
{
    a[N] = val;
    push_up(N);
    N++;
}

int main()
{
    // .................

    make_heap();

    while(N > 1)
    {
        int sum = pop_min() + pop_min();
        // .......................
        insert(sum);
    }

    return 0;
}