搜索未排序的数组

Question

在未排序的数组中,可能具有重复元素的最小和最大数量的比较是什么？

我知道在未排序的数组中找到任何东西都是O(n)问题.但是,如果数组包含重复元素,这是真的吗？

重复元素是指在给定数组中出现多次的元素.

Answer 1

作为一般经验法则，当我们谈论忽略像 O(n) 这样的常量的渐近复杂度时，无论您是否有两倍的工作量、三倍的工作量等都无关紧要。因此，问题是 O(n)在这种情况下保持 O(n) 。

在这个特定问题中，未排序数组中存在重复项并不会加快搜索元素的过程。当然，如果该元素在数组中出现了 10 次，您可能会发现它的速度快了 10 倍（平均而言），但只要这不依赖于 n，就不会改变复杂性。