Здесь известная проблема.
Для массива натуральных чисел выведите наименьшее натуральное число, которого нет в массиве.
Проблема может быть решена в пространстве и времени: прочитать массив, отслеживать в пространстве, произошло ли , отсканировать наименьший элемент.
Я заметил, что вы можете обменять пространство на время. Если у вас есть только память, вы можете сделать это зараундов и получить время. В частном случае, очевидно, существует алгоритм квадратичного времени с постоянным пространством.
Мой вопрос:
Является ли это оптимальным компромиссом, то есть ли ? Как вообще можно доказать такой тип границ?
Предположим модель RAM с ограниченной арифметикой и произвольным доступом к массивам в O (1).
Вдохновение для этой проблемы: компромисс между временем и пространством для палиндромов в модели с одной лентой (см., Например, здесь ).
Ответы:
Это может быть сделано вO(nlogn) словарных операциях и O(1) словах памяти (соответственно O(nlog2n) времени иO(logn) памяти в модели RAM уровня битов). Действительно, решение будет основано на следующем наблюдении.
Скажем, в диапазоне [ 1 , n + 1 ] естьn0 четных и n1 нечетных чисел (поэтому n 0 ≈ n 1 и n 0 + n 1 = n + 1 ). Тогда существует b ∈ { 0 , 1 } такое, что на входе не более n b - 1 значений с четностью b . Действительно, в противном случае существует не менее n 0[1,n+1] n0≈n1 n0+n1=n+1 b∈{0,1} nb−1 b n0 четное и не менее n1 нечетных значений на входе, что означает, что есть не менее n0+n1=n+1 значений, противоречие (их толькоn ). Это означает, что мы можем продолжить поиск пропущенного числа только среди нечетных или четных чисел. Тот же алгоритм может быть применен и к старшим битам двоичной записи.
Итак, наш алгоритм будет выглядеть так:
Предположим, что мы уже сейчас знаем, что на входе есть только значенияx а остаток по модулю 2b равен r∈[0,2b) но в диапазоне [ 1 , n + 1 ] есть как минимум x+1 чисел, которые имеют остаток r по модулю 2 b (в начале мы знаем, что точно для b = 0 , r = 0 ).[1,n+1] r 2b b=0,r=0
Скажем, на входе есть значенияx0 с остатком r по модулю 2b+1 и значения x1 на входе с остатком r+2b по модулю 2b+1 (мы можем найти эти числа за один проход через вход). Ясно, что x0+x1=x . Более того, поскольку на входе имеется не менее x+1 чисел с остатком r по модулю 2b , по крайней мере одна из пар(r,b+1),(r+2b,b+1) удовлетворяет требованиям этапа1 .
Мы нашли пропущенное число, когда2b⩾n+1 : в диапазоне [1,n+1] есть только одно число, которое может иметь остаток r по модулю 2b ( сам r , если оно находится в диапазоне), поэтому большинство нулевых значений на входе, которые имеют такой остаток. Так что r действительно отсутствует.
Ясно, что алгоритм останавливается заO(logn) шагов, каждому из них требуется O(n) время (один проход по входному массиву). Кроме того, требуется только O(1) слов памяти.
источник
Если я понимаю ваши определения, это можно сделать за линейное время с постоянным пространством. Это, очевидно, самая низкая граница, потому что нам нужно, по крайней мере, прочитать весь ввод.
Ответ, данный в этом вопросе, удовлетворяет.
Невозможно выполнить это с меньшим временем или пространством, и добавление дополнительного времени или пространства бесполезно, поэтому здесь нет компромисса между пространством и временем. (Заметьте, что , поэтому компромисс, который вы наблюдали, не выполняется асимптотически, в любом случае.)n=O(n/k)
С точки зрения вашего общего вопроса, я не знаю ни одной хорошей теоремы, которая поможет вам доказать компромиссы пространства-времени. Этот вопрос, кажется, указывает на то, что нет (известного) простого ответа. В принципе:
неизвестно, и сильный ответ решит множество открытых проблем (особенно в отношении SC), подразумевая, что простого решения не существует.
РЕДАКТИРОВАТЬ: Хорошо, с повторением (но я все еще предполагаю, что с вводом размера максимально возможное числоn ).n+1
Заметьте, что наш алгоритм должен уметь различать хотя бы возможных ответов. Предположим, что при каждом прохождении данных мы можем получить не более k фрагментов данных. Тогда нам понадобится n / k пропусков, чтобы дифференцировать все ответы. Предполагая, что k = n / sn k n/k k=n/s тогда мы бежим в раз. Так что я думаю, это доказывает, что вы хотите.nn/sn=sn
Сложность состоит в том, чтобы показать, что каждый раз, когда мы получаем толькоk бит. Если вы предполагаете, что наша единственная законная операция - это =, тогда мы в порядке. Однако, если вы разрешите более сложные операции, вы сможете получить больше информации.
источник