Как улучшить временную сложность этого алгоритма

Question

Вот простая проблема: у меня есть этот массив длины N, и функция, которая дает 2 границы (a, b), возвращает сумму всех элементов в массиве между a и b.

Теперьэто явно O (N) временная сложность ... но если бы я хотел сделать его более эффективным (например, log (N)), со второй структурой данных, которая хранит частичные суммы, как я мог бы это сделать?

Я думал о двоичном дереве, но не могу найти алгоритм.Конечно, я мог бы просто создать матрицу NxN, но это слишком много.Я хотел бы что-то, что не требует слишком много места и позволяет мне иметь сложность логарифмического времени;любая идея?

ОБНОВЛЕНИЕ: Я не указал это четко .. но:

1. границы указываются для индексов массива, а не для значений
2. массив динамический, значения могут меняться, и я не хочу иметь линейную сложность для изменения значения!Поэтому простой алгоритм частичных сумм не работает, я думаю ..
3. нет параллельного программирования (1 процессор)

Answer 1

Ну, у вас может быть другой массив того же размера, в котором вы храните частичные суммы. Затем, когда вам дают границы, вы можете просто вычесть частичные суммы, и вы получите сумму элементов в этом интервале. Например:

Elements:    1 2 3 4  5  6
Partial_Sum: 1 3 6 10 15 21

Скажем, массив начинается с индекса = 0, и вы хотите, чтобы сумма элементов в интервале [1, 3] включительно:

// subtract 1 from the index of the second sum, because we
// want the starting element of the interval to be included.
Partial_Sum[3] - Partial_Sum[1-1] = 10 - 1 = 9

Answer 2

Хорошо, может быть, я нашел решение, чтобы log (n) как для значения, так и для суммы, и с линейными пробелами.

Я попытаюсь объяснить: мы строим двоичное дерево, гделистья - это значения массива в том порядке, в котором они находятся в массиве (не отсортировано, не отсортировано дерево).

Затем мы создаем дерево снизу вверх, объединяя 2 листа за раз и помещая их сумму вродитель.Например, если массив имеет длину 4 и значения [1,5,3,2], у нас будет дерево с 3 уровнями, корень будет общей суммой (11), а остальные будут 1 + 5->6 и 3 + 2-> 5

Теперь, чтобы изменить значение, мы должны обновить это дерево (log n) и вычислить сумму, которую я разработал для этого алгоритма (log n):

acc = 0 // аккумулятор

начиная с нижней границы, мы идем вверх по дереву.Если мы идем вверх налево (текущий узел - правый дочерний элемент), то acc + = current_node - parent_node.Если мы идем вправо (текущий узел - левый потомок), мы ничего не делаем.

Затем мы делаем то же самое с верхней границы, конечно, в этом случае все наоборот (мы делаем сумму, еслимы идем направо)

мы делаем это поочередно, один раз на нижней границе, один раз на верхней границе.Если у нас есть 2 узла, которые мы достигаем, на самом деле являются одним и тем же узлом, мы затем суммируем значение этого узла с аккумулятором и возвращаем аккумулятор.

Я знаю, что не очень хорошо это объяснил ...У меня возникли трудности с объяснением .. Кто-нибудь понял?

Answer 3

Я, должно быть, что-то упускаю из вопроса. Учитывая массив частичных сумм, вы должны быть в состоянии получить постоянную сложность - сумма элементов от a до b равна partial_sums[b] - partial_sums[a] (или, если вы не можете принять a<b, partial_sums[max(a,b)] - partial_sums[min(a,b)]).

Возможно, вы говорите о a и b как о границах значений, а не местоположения? Если это так, то при условии, что ваш массив отсортирован, вы можете получить сложность O (log N), используя двоичный поиск для местоположений a и b, а затем вычитая, как указано выше. Если массив не (и не может быть) отсортирован, вы можете сделать то же самое, создав массив ссылок на исходные объекты, отсортировав ссылки и сгенерировав частичные суммы для этих ссылок. Это добавляет работу к предварительной обработке, но сохраняет O (log N) для запросов.

Редактировать: Создание динамических массивов не должно иметь никакого эффекта, по крайней мере, с точки зрения вычислительной сложности. Если вы когда-либо вставляете / удаляете только в конце основного массива, вы также можете вставлять / удалять в постоянное время в массиве частичных сумм. Для вставки вы делаете что-то вроде:

N = N + 1
main_array[N] = new_value
partial_sum[N] = partial_sum[N-1] + new_value

Чтобы удалить с конца, вы просто используете N = N - 1 и игнорируете значения, ранее находившиеся на концах обоих массивов.

Если вам нужно поддерживать вставку / удаление в середине основного массива, это занимает линейное время. Обновление массива частичных сумм также может быть выполнено за линейное время. Например, чтобы вставить new_value в индекс i, вы должны сделать что-то вроде:

N = N + 1
for location = N downto i + 1 
    main_array[location] = main_array[location-1]
    partial_sums[location] = partial_sums[location-1] + new_value

Удаление аналогично, за исключением того, что вы продвигаетесь вверх от точки удаления до конца и вычитаете удаляемое значение.

Я действительно сказал "должен" по причине - возможное предостережение. Если ваш массив очень динамический и , содержимое с плавающей запятой, вы можете / столкнетесь с проблемой: многократное добавление и вычитание значений при вставке / удалении элементов может (и в конечном итоге будет ) привести к ошибкам округления. В этих обстоятельствах у вас есть пара вариантов: один - полностью отказаться от идеи. Другой использует еще больше памяти - при добавлении / удалении элементов сохраняйте текущую сумму абсолютных значений элементов, которые были добавлены / вычтены. Когда / если это превышает выбранный процент от частичной суммы для этой точки, вы пересчитываете свои частичные суммы (и обнуляете текущую сумму).

Answer 4

Кажется, я помню, что суммы префиксов могут быть использованы для ответа на такие запросы в O(lg n) времени.

РЕДАКТИРОВАТЬ: Я был немного слишком быстр - это можно сделать дажеБыстрее.Если вы потратите O(n) времени (и O(n) дополнительной памяти) на предварительный расчет массива префиксных сумм (на одноядерном компьютере), ответ на каждый запрос можно найти за O(1) времени, вычтя соответствующие элементы этого массива.,Если у вас есть n доступных процессоров, предварительное вычисление может быть выполнено за O(lg n) время.

Answer 5

Создать сбалансированное двоичное дерево, сортирующее числа по их значению. Это можно сделать так, чтобы каждая операция занимала линейное время. В каждом узле хранится сумма всех значений ниже этого узла. Чтобы вычислить сумму значений в диапазоне [a, b], вам нужно пройти вниз по этому дереву как для a, так и для b и добавить соответствующие значения. O (ln n) каждый раз, когда вы вычисляете сумму или меняете значение.

Answer 6

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

Поскольку вы не разрешено выполнять ваше решение в многопроцессорной среде, вы «застряли» с O (N).

Если бы вашему решению было разрешено работать в многопроцессорной среде, оптимальной сложностью была бы O(N / p + p + 1), где p - количество доступных процессоров.Это связано с тем, что в этом случае вы могли бы разделить интервал на p подинтервалов (+1), суммировать параллельные интервалы (N / p), а затем суммировать результат каждого отдельногоподинтервал (+ p) для завершения расчета.

Answer 7

Есть два случая: статические данные или динамические (переменные) данные

1. Статические данные

Для статических данных это хорошо известная проблема. Сначала вычисляем «таблицу сумм» (массив из n + 1 элементов):

st[0] = 0;
for (int i=0,n=x.size(); x<n; x++)
    st[i] = st[i-1] + x[i];

затем, чтобы вычислить сумму элементов между a и b, вам просто нужно сделать

sum = st[b] - st[a];

Алгоритм также может использоваться в более высоких измерениях. Например, если вам нужно вычислить сумму всех значений между (x0, y0) и (x1, y1), вы можете просто сделать

sum = st[y0][x0] + st[y1][x1] - st[y0][x1] - st[y1][x0];

где st[y][x] - сумма всех элементов выше и слева от (x, y).

Для вычисления таблицы сумм используется операция O (n) (где n - количество элементов, например, rows*columns для двумерной матрицы), но для очень большие наборы данных (например, изображения) можно написать оптимальную параллельную версию , которая может работать в O (н / м) , где м - это число доступные процессоры. Это то, что я нашел довольно удивительным ...

Чтобы выполнить простое (однопоточное) вычисление таблицы сумм в 2d случае:

for (int y=0; y<h; y++)
  for (int x=0; x<w; x++)
    st[y+1][x+1] = st[y+1][x] + st[y][x+1] - st[y][x] + value[y][x];

2.Динамические данные

Вместо динамических данных вы можете использовать то, что можно назвать подходом "многократного разрешения":

void addDelta(std::vector< std::vector< int > >& data,
              int index, int delta)
{
    for (int level=0,n=data.size(); level<n; level++)
    {
        data[level][index] += delta;
        index >>= 1;
    }
}

int sumToIndex(std::vector< std::vector< int > >& data,
               int index)
{
    int result = 0;
    for (int level=0,n=data.size(); level<n; level++)
    {
        if (index & 1) result += data[level][index-1];
        index >>= 1;
    }
    return result;
}

int sumRange(std::vector< std::vector< int > >& data,
             int a, int b)
{
    return sumToIndex(data, b) - sumToIndex(data, a);
}

В основном на каждом «уровне» ячейка содержит суммы двух ячеек следующих более мелких уровней. Когда вы добавляете данные на самый низкий (с более высоким разрешением) уровень, вы также должны добавить их на более высокие уровни (это то, что делает addDelta). Чтобы вычислить сумму всех значений от 0 до x, вы можете использовать более высокие уровни для экономии вычислений ... см. Следующий рисунок:

Наконец, чтобы получить сумму от a до b, вы просто вычисляете разницу между этими двумя суммами, начиная с 0.