对于竞争性编程，有时我们需要从数组中找到最大值：我找到了一些算法，如下所示
Algorithms
让我知道你有任何参考。或任何解决方案在你的脑海
我尝试将时间复杂度降至最低，如下所示
array = [6, 8, 100, 4, 2]
l = len(array)
max = 0
for i in range(l//2):
if max<array[i]:
max = array[i]
if max<array[-1-i]:
max = array[-1-i]
if l%2!=0:
if max<array[i+1]:
max = array[i+1]
print(max)
3条答案
按热度按时间toiithl61#
不，没有比
O(n)更快的东西，也不可能有，证明时间复杂性往往意味着非常高深的数学，但在这种情况下，它非常容易理解：在读取数组中的所有数字之前，您无法知道哪个数字最大（否则，您尚未读取的数字可能比所有其他数字都大）。而这个运算本身，阅读所有的数字，就是O（n）。
所以不可能存在比O（n）更快的算法。
qojgxg4l2#
这段代码已经过优化，技术上需要O（n/2），所以仍然是线性时间。
Python中的max（）函数实际上非常快，可能比任何手动实现都要快。
但是如果你问的是一般情况，是否有任何算法可以在小于O（n）的时间内找到***未排序***数组中的最大元素，那么没有，据我所知，你能做的最好是线性时间。
rjzwgtxy3#
简短的回答是no，因为如果不首先检查所有元素，就无法知道一个元素是未排序数组中的最大值。
然而，可以使用一些技巧来使O（n）更快，例如使用多线程方法，减少搜索空间，或者使用某种奇特的方法 *。
如果这里的目标是赢得编程比赛，那么尝试类似这样的方法：
1.使用多个线程查找每个子数组的最大值，然后查找最大值中的最大值。根据数据集的大小和启动线程的时间，这可能会有所帮助。
1.确定数据是否具有一些可以利用的属性，例如知道边界、知道是否存在重复项、知道它是否以任何特定顺序进行结构化。
1.最后一种方法只是我个人的看法，但我认为值得一提的是，在某些情况下，还有一些更奇特的方法在理论上可以比O（n）做得更好，比如Sleep Sort。