Пространственно-временное решение проблемы пропущенного элемента

14

Здесь известная проблема.

Для массива A[1n] натуральных чисел выведите наименьшее натуральное число, которого нет в массиве.

Проблема может быть решена в O(n) пространстве и времени: прочитать массив, отслеживать в O(n) пространстве, произошло ли 1,2,,n+1 , отсканировать наименьший элемент.

Я заметил, что вы можете обменять пространство на время. Если у вас есть O(nk)только память, вы можете сделать это заkраундов и получить времяO(kn). В частном случае, очевидно, существует алгоритм квадратичного времени с постоянным пространством.

Мой вопрос:

Является ли это оптимальным компромиссом, то есть ли timespace=Ω(n2) ? Как вообще можно доказать такой тип границ?

Предположим модель RAM с ограниченной арифметикой и произвольным доступом к массивам в O (1).

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

sdcvvc
источник
2
Нет, вы можете отсортировать ваш массив в затем найти пропущенное число (первое число должно быть 1, второе должно быть 2, ... иначе вы найдете его) в O (n), эта сортировка может быть выполнена с INPLACE, слиянием средств O ( 1 ) дополнительное пространство, так что время пространство принадлежит O ( п войти п ) . Я не знаю, понял ли я вашу проблему точно или нет (из-за этого я не ответил на нее, также я не знаю, есть ли лучший предел). O(nlogn)O(1)O(nlogn)
Я предполагаю, что вход только для чтения. (Если это не так, проблема может быть оптимально решена в пространстве время / O ( 1 ) : умножьте ввод на 2 и используйте чётность для симуляции алгоритма O ( n ) / O ( n ) )O(n)O(1)O(n)/O(n)
sdcvvc
Что такое алгоритм постоянного пространства? Похоже, вам понадобится пробел для версии n 2, которая «очевидна» для меняlognn2
Xodarap
В этой модели целочисленные слова принимают ; если это более удобно, вы можете ответить на любой вариант вопроса со временем space = Ω ( n 2O(1)для некоторой постояннойk. timespace=Ω(n2logkn)k
sdcvvc
@sdcvvc, я не могу понять ваш алгоритм , вы бы описали его немного подробнее? (просто обратите внимание, что чтение в битах занимает O ( log n ) ). O(n)/O(1)O(logn)

Ответы:

2

Это может быть сделано в O(nlogn) словарных операциях и O(1) словах памяти (соответственно O(nlog2n) времени иO(logn) памяти в модели RAM уровня битов). Действительно, решение будет основано на следующем наблюдении.

Скажем, в диапазоне [ 1 , n + 1 ] есть n0 четных и n1 нечетных чисел (поэтому n 0n 1 и n 0 + n 1 = n + 1 ). Тогда существует b { 0 , 1 } такое, что на входе не более n b - 1 значений с четностью b . Действительно, в противном случае существует не менее n 0[1,n+1]n0n1n0+n1=n+1b{0,1}nb1bn0 четное и не менее n1 нечетных значений на входе, что означает, что есть не менее n0+n1=n+1 значений, противоречие (их толькоn ). Это означает, что мы можем продолжить поиск пропущенного числа только среди нечетных или четных чисел. Тот же алгоритм может быть применен и к старшим битам двоичной записи.

Итак, наш алгоритм будет выглядеть так:

  1. Предположим, что мы уже сейчас знаем, что на входе есть только значения x а остаток по модулю 2b равен r[0,2b) но в диапазоне [ 1 , n + 1 ] есть как минимум x+1 чисел, которые имеют остаток r по модулю 2 b (в начале мы знаем, что точно для b = 0 , r = 0 ).[1,n+1]r2bb=0,r=0

  2. Скажем, на входе есть значения x0 с остатком r по модулю 2b+1 и значения x1 на входе с остатком r+2b по модулю 2b+1 (мы можем найти эти числа за один проход через вход). Ясно, что x0+x1=x . Более того, поскольку на входе имеется не менее x+1 чисел с остатком r по модулю 2b , по крайней мере одна из пар(r,b+1),(r+2b,b+1) удовлетворяет требованиям этапа1 .

  3. Мы нашли пропущенное число, когда 2bn+1 : в диапазоне [1,n+1] есть только одно число, которое может иметь остаток r по модулю 2b ( сам r , если оно находится в диапазоне), поэтому большинство нулевых значений на входе, которые имеют такой остаток. Так что r действительно отсутствует.

Ясно, что алгоритм останавливается за O(logn) шагов, каждому из них требуется O(n) время (один проход по входному массиву). Кроме того, требуется только O(1) слов памяти.

Кабан-5
источник
Я рад видеть ответ на этот вопрос после того времени :)
sdcvvc
1

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

Ответ, данный в этом вопросе, удовлетворяет.

Невозможно выполнить это с меньшим временем или пространством, и добавление дополнительного времени или пространства бесполезно, поэтому здесь нет компромисса между пространством и временем. (Заметьте, что , поэтому компромисс, который вы наблюдали, не выполняется асимптотически, в любом случае.)n=O(n/k)

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

Предположим, что некоторый язык разрешим в времени (используя некоторое количество пространства) и в s пространстве (используя некоторое количество времени). Можем ли мы найти f , g такой, что L разрешима на M, который работает за время f ( t , s ) и g ( t)tsf,gLMf(t,s)пространстве , s ) ?g(t,s)

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


РЕДАКТИРОВАТЬ: Хорошо, с повторением (но я все еще предполагаю, что с вводом размера максимально возможное числоn ).n+1

Заметьте, что наш алгоритм должен уметь различать хотя бы возможных ответов. Предположим, что при каждом прохождении данных мы можем получить не более k фрагментов данных. Тогда нам понадобится n / k пропусков, чтобы дифференцировать все ответы. Предполагая, что k = n / snkn/kk=n/s тогда мы бежим в раз. Так что я думаю, это доказывает, что вы хотите.nn/sn=sn

Сложность состоит в том, чтобы показать, что каждый раз, когда мы получаем только k бит. Если вы предполагаете, что наша единственная законная операция - это =, тогда мы в порядке. Однако, если вы разрешите более сложные операции, вы сможете получить больше информации.

Xodarap
источник
3
В связанном вопросе предполагается, что каждое число встречается не более одного раза. Я не делаю этого предположения, поэтому решение не применяется. Спасибо за вторую ссылку.
sdcvvc
@sdcvvc: Моя ошибка, я предположил, что вы используете версию, с которой я знаком. У меня нет полного ответа, но это слишком долго для комментария - надеюсь, мое редактирование будет полезным.
Xodarap
5
k 2kn/2kn/k