用于查找数组最大值的O(log n)算法? [英] O(log n) algorithm for finding max of array?
本文介绍了用于查找数组最大值的O(log n)算法?的处理方法,对大家解决问题具有一定的参考价值,需要的朋友们下面随着小编来一起学习吧!
问题描述
是否存在一种算法,可以在O(log n)时间中找到未排序数组的最大值?
Does an algorithm exist that finds the maximum of an unsorted array in O(log n) time?
推荐答案
此问题经常被问到(这是一个很受欢迎的CS家庭作业问题吗?),答案始终是相同的:否。
This question is asked a lot (is this a popular CS homework question or something?) and the answer is always the same: no.
考虑一下数学上。除非对数组进行排序,否则没有任何东西可以减半以提供 log(n)
行为。
Think about it mathematically. Unless the array is sorted, there is nothing to "cut in half" to give you the log(n)
behavior.
阅读问题注释以进行更深入的讨论(无论如何,这可能超出了问题的范围)。
Read the question comments for a more in-depth discussion (which is probably way out of the question's scope anyhow).
这篇关于用于查找数组最大值的O(log n)算法?的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!
查看全文