问题与标题所说的差不多，只是略有不同。如果我没记错的话，在大小为“n”的数组中查找条目的平均情况复杂度为 O(n)。
我假设如果向量中有固定数量的元素，我们想从中找到一个元素，情况也是如此。
但是如果条目的数量(我们仍然只尝试找到一个条目)以某种方式与向量的大小相关，即以某种方式随着它增长，那又如何呢？ 我手头有这样一个案例，但我不知道数组大小和搜索条目数之间的确切关系。可能是线性的，可能是对数的..平均情况仍然是 O(n) 吗？
如有任何见解，我将不胜感激。
编辑:一个例子
数组大小:100
数组内容:在每个位置，1-10个数字，完全随机选择哪个。
我们要找的:“1”的第一次出现
从天真的角度来看，我们应该平均在任何一种线性搜索中查找 10 次后找到一个条目(我们必须这样做，因为内容没有排序。)
由于大 O 中通常会省略因子，这是否意味着我们仍然需要时间 O(n)，即使它应该是 O(n)
最佳答案
反正是O(n)。
考虑在这里找到 1:
[9,9,9,9,9,1]
关于arrays - 查找数组中众多元素之一的复杂性，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/25221507/