搜索操作复杂性

Question

在

允许重复的未排序数组中搜索操作的复杂性是多少？我的猜测是 O（N），因为它允许重复，需要搜索整个数组。但是我对算法的复杂性很陌生，我不确定我的答案，你能确认我是否正确吗？

Answer 1

由于数组是未排序的，因此您必须平均查看数组的一半才能找到要搜索的元素。因此，复杂性是线性的 - O（N）。重复或没有重复，同样复杂。

Answer 2

在无序数组中搜索元素确实是 O（N），因为没有启发式方法可以加快搜索速度。

Answer 3

它是

O（n），因为在最坏的情况下，你仍然需要查看每个元素。