问题几乎是标题所说的，只是稍有变化。如果我没记错的话，在大小为'n'的数组中查找条目的平均情况为复杂度O（n）。
我认为如果向量中有固定数量的元素（我们要查找其中一个），情况也是如此。
但是，如果我们仍然只尝试找到一个条目的数量与向量的大小相关（即以某种方式增加），该怎么办？我手头有这种情况，但是我不知道数组大小和搜索到的条目数之间的确切关系。可能是线性的，也可能是对数的。平均情况是否仍为O（n）？
我将不胜感激。
编辑：一个例子
数组大小：100
数组内容：在每个位置，数量为1-10，完全随机是其中之一。
我们追求的是：第一次出现“ 1”
从幼稚的角度来看，我们平均应该在任何类型的线性搜索中查找10次查找后的条目（由于内容未排序，因此我们必须这样做）。
由于通常在big-O中省略因素，这是否意味着我们仍然需要及时O（n），即使它应该是O（n）
反正是O（n）。
考虑在1这里找到：
[9,9,9,9,9,1]
本文收集自互联网，转载请注明来源。
如有侵权，请联系[email protected] 删除。
我来说两句