搜索未排序数组

Question

未排序数组中可能有重复元素的最小和最大比较次数是多少？

据我所知，在未排序数组中找到任何东西都是O（n）问题。但是，如果数组也包含重复元素，这是真的吗？

重复元素我的意思是，在给定数组中出现多次的元素。

Answer 1

作为一般的经验法则，当我们谈论忽略像O（n）这样的常数的渐近复杂性时，无论你有两倍的工作量还是三倍的工作量都不重要。因此，问题是O（n）在这种情况下保持O（n）。

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

Answer 2

所以这里的想法是，你必须从前到后走阵列，因为它是未排序的。这意味着你正在看O（n） - 元素的线性遍历。无论您正在搜索的位置是位置0，位置8还是位置n-1，您都必须走阵列才能找到它。

现在，如果数组中可能有重复，唯一的区别是您可能会发现该值的多个实例。如果你正在寻找所有这些或只是第一个，它仍然是一个O（n）的情况。重复项不会改变复杂性。

最好的情况 - 你找到它（假设你只需要找到一个）在第一次比较。

最坏的情况 - 没有重复的给定值，它是你检查的最后一个 - 第n比较。

如果您必须查找所有重复项，它总是会进行n次比较，因为您必须访问未排序数组中的每个元素。

Answer 3

即使存在重复元素，O(n)时间也是如此。你应该熟悉big-oh notation。

在最坏的情况下，考虑这个数组：1, 1, 1, 1, ..., 1, 1, 2。如果从第一个元素开始搜索2，那么将会完全进行n比较，因此重复项目根本没有任何帮助。如果你要搜索1，你会发现它在一个单一的比较，但有不同元素的输入，如果你幸运的话，你也可以在单个比较中找到一个元素，所以重复确实不会意味着很多，除了你更有可能幸运并且以更少的步骤找到你的目标元素。但它仍然是O(n)。

几乎总有最好的情况和最坏的情况。大多数算法的实际性能总是取决于给定的输入，大哦表示法只会让您对算法如何执行有一个模糊的概念。这并不是说渐近表示法是无用的，只是它并不总是完全准确，因为涉及的基础常量在实践中会产生差异。

如果对性能有疑问，请运行您自己的基准测试。

Answer 4

什么会在排序的数组 ，可能有重复的元素，以及最小和最大 数量比较？

如果您正在搜索一个指定的值，那么最小和最大比较数将分别为1和n。如果已知该值在数组中，并且您只查找它的位置，则可以通过n-1比较逃脱。

据我所知，发现任何在 未排序的数组是O（n）问题。但是，如果数组中还包含重复的 元素，那么是否为 ？

是的，它仍然是O（n）。

假设重复出现意味着平均搜索时间减半。那么，这是一个很大的减少，但它不会影响O（n）的时间。大O不是一般的情况，这是最坏的情况，最坏的情况不会改变。无论如何，由一个常数因子划分不会影响大O时间。

Answer 5

依我之见，应该是2N比较

for (int i=0; i<n; i++) 
    if (a[i]==ele) 
     break 
    else 
     continue; 

因此，有两个比较(i<n)和(a[i]==ele)做过N次在最坏的情况下。因此2n比较。如果有什么方法可以减少i<n，我不知道如何。

Answer 6

像其他人一样，我同意一个包含没有重复的未分类数组，穷举线性搜索将是O（n）。

如果允许重复，则该算法仅在任何元素重复的概率均匀分布的假设下保持为O（n）。

如果存在描述重复元素分布的不同概率密度函数，则根据概率密度函数，搜索算法可能会小于O（n）。