在比O(n)更快的未排序整数数组中找到最小元素？

Question

这可能比O(n)时间复杂度更快地找到未排序整数数组的最小元素.空间复杂性不是问题.

Answer 1

不,这是不可能的.给定一个任意数组的元素,您必须至少查看一次每个元素,以确定您已找到最小元素.这意味着必要的时间复杂度?(n) (请参阅此处了解有关Big Omega表示法的更多信息),这意味着*任何找到最小元素的算法都将至少采取c * n操作,其中c常量(在本例中为c >= 1).

换句话说,如果算法花费的时间少于n操作,则算法中至少必须有一个算法未传递的元素.由于我们没有关于这个元素的信息(数组是任意的),我们不能说这个元素不小于算法声明的最小元素.所以算法不正确.

_{*请注意,这不是Big-Omega符号的正式含义,但它得到了重点.你可以在这里阅读正式的定义.}