是否存在一种算法，可以在O(logn)时间内找到未排序数组的最大值？
这个问题被问了很多(这是一个流行的CS家庭作业问题还是什么？)答案总是一样的：no。
从数学角度考虑。除非对数组进行排序，否则没有什么可以"对半切开"来提供log(n)行为。
阅读问题评论进行更深入的讨论(无论如何，这可能远远超出了问题的范围)。
考虑一下：如果不访问每个元素，你怎么知道你没有访问过的某个元素不比你迄今为止发现的最大元素大？
在O(log(N))中无法执行此操作。在最佳/最差/平均情况下，它是O(N)，因为需要访问数组中的每个项来确定它是否是最大的项。数组未排序，这意味着您不能偷工减料。
即使在并行化的情况下，这也不能在O(N)中完成，因为Big-O表示法并不关心一个人有多少CPU或每个CPU的频率。它是从这一点上抽象出来的，专门用来给出问题的粗略估计。
并行化可以被忽略，因为划分作业所花费的时间可以被认为等于顺序执行的时间。这是由于忽略常量的原因。以下都是相同的：
O(N) = O(Const * N) = O(N / Const) = O(N + Const) = O(N - Const)
另一方面，在实践中，分治并行算法可以给您带来一些性能优势，因此它可能会运行得更快。幸运的是，Big-O没有处理这种细粒度的算法复杂性分析。
否。您必须至少对数组进行一次迭代。
否。它是O(n)。在最坏的情况下，必须访问和比较阵列的所有成员。
当然不是。假设仍然有一个元素，你还没有将它与任何其他元素进行比较。所以不能保证你没有比较的元素不是最大元素
假设比较图(元素的顶点和比较的边)有多个组件。在这种情况下，你必须放一个边(以最好的方式在最大两个分量之间)。我们可以看到，在n-1运算时必须进行
O(log n)意味着您甚至不必读取整个数组，因为这将是O(n)，对于未排序的数组来说，这是不可能的，因为如果您不能将元素与所有其他元素进行比较，则无法确保元素最大。O(n)是你所能得到的最好的绝对最大值，它只遍历一次数组，如果你只想要一个近似值，你可以随机挑选元素，并有最大值，这将挑选小于n的元素，然而，O(log n)对于未排序的数组是不可能的。
是的，我们可以这样做，但条件是，如果我们的数组是一个山数组。`
public int peakIndexInMountainArray(int[] arr) {
int s = 0;
int e = arr.length-1;
int mid = s+(e-s)/2;
while(s<e){``
if(arr[mid]<arr[mid+1]){
s = mid+1;
}
else{
e = mid;
}
mid = s+(e-s)/2;
}
return mid;
}`
这已经很老了，但我不同意给出的答案是，可以用并行硬件在对数时间内完成。
时间复杂度为：
O(log(n) * log(m))
n是要比较的数字的数量；m是每个数字的大小。
然而，硬件尺寸为：
O(n * m)
算法是：
成对比较数字。使用超前进位比较器，这样做的时间是
O(log(m))，大小是O(n * m)。使用1中的结果对1的两个输入进行多路复用。时间为
O(1)，大小为O(n * m)。现在您有一个初始大小的一半的数组；转到步骤1。此循环重复
log(n)次，因此总时间为O(log(n) * log(m))，总大小为O(n * m)。
如果需要，添加更多的MUX也可以跟踪最大数字的索引，而不会增加算法的复杂性。
如果使用N处理器，则可以在O(log N)时间内完成。但是工作复杂性仍然是O(N)。
如果使用N^2处理器，可以通过应用Usain Bolt算法将时间复杂性降低到O(1)。
我认为使用分段树可能会有所帮助，您可以实现log(N)成本。