Предположим, что у нас есть массив A[1...n], и этот массив имеет m различные ключи.
Возможно ли для n→∞ сложность стать Θ(m)?
Это означает, что если m = constant, то Θ(1).Можем ли мы найти элемент в массиве {1,2, ..., n} с элементами m различных элементов в Θ (m)?
Нет, вы не можете. Кроме того, даже если m=2 вы не можете найти в O(1), потому что это будет означать вы можете найти значение x в неограниченном массиве (все значения возможны) также в O(1), создав функцию:
f(i) = 1 arr[i] = x
0 otherwise
и поиск если есть значение i такое, что f(i) = 1.
Поскольку вам не удалось найти в массиве элемент в регионе O(1), знайте, что всего по-настоящему m отдельные элементы не выдерживают для вас.
Вышеизложенное верно для любой константы m>2.
@amit Массив не отсортирован. Но я не знаю, могу ли я использовать его в качестве гипотезы, – CharisAlex
Я думаю, вы можете получить больше ответов на этот вопрос на сайте теоретической информатики, так как он не занимается вопросами кодирования. –
Зависит от того, как хранится массив. Или, другими словами, если вопрос: «Существует ли структура данных, размер которой равен O (n + m), который может хранить упорядоченные значения« n »в диапазоне« 1..m »и которые могут отвечать в O (1) запросы «Каково значение объекта i?» И «Есть ли объект, значение которого j?», То ответ «да». – rici