<分区>
假设我们有一个数组 A[1...n] 并且这个数组有 m 个不同的键。
n→∞的复杂度是否有可能变为Θ(m)？
这意味着如果 m = constant 则 Θ(1)。
<分区>
假设我们有一个数组 A[1...n] 并且这个数组有 m 个不同的键。
n→∞的复杂度是否有可能变为Θ(m)？
这意味着如果 m = constant 则 Θ(1)。
最佳答案
不，你不能。
此外，即使 m=2 您无法在 O(1) 中找到，因为这意味着您可以在不受限制的情况下找到值 x数组(所有值都是可能的)也在 O(1) 中，通过创建一个函数:
f(i) = 1 arr[i] = x
0 otherwise
并搜索是否存在满足 f(i) = 1 的值 i。
由于您无法在 O(1) 的数组中找到一个元素，因此最多 m 个不同元素的知识在这里对您没有帮助。
以上显然对任何常量 m>2 也是正确的。
关于algorithm - 我们能否找到元素是否存在于数组 {1,2,...,n} 中，其中元素为 Θ(m) 中的 m 个不同元素？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/28795181/