Можем ли мы найти, существует ли элемент в массиве {1,2,...,n} с элементами m различных элементов в Θ(m)?

Question

Предположим, что у нас есть массив A[1...n] и этот массив имеет m разных ключей.
Это возможно для n→∞ сложность стать Θ(m)?

Что означает, что если m = constant затем Θ(1),

Answer 1

Нет, ты не можешь. Более того, даже если m=2 вы не можете найти в O(1), потому что это будет означать, что вы можете найти значение x в неограниченном массиве (все значения возможны) также в O(1), создав функцию:

f(i) = 1         arr[i] = x
       0         otherwise

и поиск, если есть значение i такой, что f(i) = 1,
Поскольку вы не можете найти в массиве элемент в O(1)знание не более m Отдельные элементы здесь вам не помогут.

Сказанное выше верно для любой константы m>2 также.