Можно ли вычислить минимум набора чисел по модулю заданного числа в амортизированном сублинейном времени?

Существует ли структура данных, представляющая большой набор S (64-разрядных) целых чисел, который начинается пустым и поддерживает следующие две операции:

  • insert(s) вставляет число S в S;
  • minmod(m) возвращает число S в S так, что s mod m минимально.

Пример:

    insert(11)
    insert(15)
    minmod(7) -> the answer is 15 (which mod 7 = 1)
    insert(14)
    minmod(7) -> the answer is 14 (which mod 7 = 0)
    minmod(10) -> the answer is 11 (which mod 10 = 1)

Я заинтересован в минимизации максимального суммарного времени, затраченного на последовательность n таких операций. Очевидно, что можно просто сохранить список элементов для S и перебрать их для каждой операции minmod; то вставка O(1), а minmod - O(|S|), что займет O(n^2) время для операций n (например, n/2 insert, за которыми следуют операции n/2 minmod, будет примерно грубо n^2/4 операции).

Итак: возможно ли сделать лучше, чем O(n^2) для последовательности операций n? Может быть, O(n sqrt(n)) или O(n log(n))? Если это возможно, мне также будет интересно узнать, есть ли структуры данных, которые дополнительно допускают удаление отдельных элементов из S или удаление всех номеров в пределах интервала.

Ответы

Ответ 1

Другая идея основана на сбалансированном двоичном дереве поиска, как в Keith.

Предположим, что все вставленные элементы хранятся в сбалансированном BST, и нам нужно вычислить minmod(m). Рассмотрим наше множество S как объединение подмножеств чисел, лежащих в отрезках [ 0, m-1], [m, 2m-1], [2m, 3m-1].. и т.д.. Ответ, очевидно, будет среди минимальных чисел, которые мы имеем в каждом из этих интервалов. Таким образом, мы можем, следовательно, искать дерево, чтобы найти минимальные числа этих интервалов. Это легко сделать, например, если нам нужно найти минимальное число в [a, b], мы будем двигаться влево, если текущее значение больше, чем a, и В противном случае, отслеживая минимальное значение в [a, b], мы уже встречались.

Теперь, если мы предположим, что m является равномерно распределенным в [1, 2 ^ 64], вычислите математическое ожидание числа запросы, которые нам понадобятся.

Для всех m в [2 ^ 63, 2 ^ 64-1] нам понадобятся 2 запросы. Вероятность этого 1/2.
Для всех m в [2 ^ 62, 2 ^ 63-1] нам понадобятся 4 запросы. Вероятность этого 1/4.
...
Математическое ожидание будет sum [1/(2 ^ k) * 2 ^ k], для k в [1,64] который является 64.

Итак, чтобы суммировать, сложность запросов средняя minmod(m) будет O (64 * logn). В общем случае, если m имеет неизвестную верхнюю границу, это будет O (logmlogn). Обновление BST, как известно, O (logn), поэтому общая сложность в случае n запросов будет O (nlogm * logn).

Ответ 2

Частичный ответ слишком большой для комментария.

Предположим, что вы реализуете S как сбалансированное двоичное дерево поиска.

Когда вы ищете S.minmod(m), наивно вы идете по дереву, а стоимость - O (n ^ 2).

Однако в данный момент во время прогулки у вас есть лучший (самый низкий) результат. Вы можете использовать это, чтобы избежать проверки всех поддеревьев, когда:

bestSoFar < leftChild mod m

и

rightChild - leftChild < m - leftChild mod m

Это поможет только в том случае, если общий интервал b/w числа в наборе меньше общих значений m.

Обновить следующее утро...

Григор лучше и более четко сформулировал мою идею и показал, как она хорошо работает для "больших" m. Он также показывает, как "случайный" m обычно "большой", поэтому работает хорошо.

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

Но пусть m ~ 2^32? Тогда алгоритм поиска (конечно, как указано, но и в противном случае) должен проверять интервалы 2^32, что в любом случае может означать поиск всего набора.