algorithm - 我们能否找到元素是否存在于数组 {1,2,...,n} 中，其中元素 m 个不同的元素在 Θ(m) 中？

Question

假设我们有一个数组A[1...n]，这个数组有m个不同的键。
复杂性有可能n→∞变成Θ(m)?

这意味着 if m = constantthen Θ(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，上述情况显然也是正确的。