我想用除法在O(log N)
时间内找到数组中的最大元素。我在planet-source-code找到了一个工作代码。我把它翻译成Python,如下所示:
def largest(arr,i,j):
global max1
global max2
if i == j:
max1 = arr[i]
else:
if i == j-1:
max1 = arr[i] if arr[i] > arr[j] else arr[j]
else:
mid = (i+j)/2
largest(arr,i,mid)
max2 = max1
largest(arr,mid+1,j)
if max2 > max1:
max1 = max2
当我使用数组[98,5,4,3,2,76,78,92]
,并将代码调用为
我得到一个出界列表索引错误。但是C代码返回正确的结果98。有人能看出我犯了什么错误吗?在
最后会有一个函数调用
那你的密码呢
^{pr2}$将尝试索引arr[j]=arr[8] 这是越界的,因为Python从0-7而不是1-8枚举向量。在
顺便说一句,我不认为你有一个O(logn)算法,因为所有元素都必须至少扫描一次才能找到最大元素,从而得到O(N)。在
对于一般的未排序数组,您永远无法在小于O(n)的时间内找到
max
。一个非常简单的证明:如果在不到O(n)的时间内完成,那么对于一个足够大的数组,就没有足够的时间检查每个元素。因此,对手可以将最大值放在您不检查的元素中,从而使您的算法不正确。在原始代码的优点是使用少于2n的比较同时找到最大值和最小值(就像朴素的实现一样),它使用大约1.5n的比较,因为当有两个元素时它只执行一个比较。使用它只找到最大值不会带来任何好处:最好在Python中使用
max(arr)
(这也会更快,因为它没有函数调用开销)。在原始代码将值存储在
a[1]
到a[n]
中,这需要一个大小为n+1
的数组。因此,您应该在第一个位置放置一个虚拟元素。在但是,更麻烦的是,你的翻译是不正确的。原始版本使用全局变量来实现多值返回(这是一种非常老练的方法),并使用局部变量来保存旧的全局变量。由于您使
max1
和max2
都是全局的,所以该函数无论如何都不会产生正确的答案。在正确的Python转换将使用带有元组的直接多值返回:
相关问题 更多 >
编程相关推荐