递归算法，用于检查数组中的最大值是否大于给定值

Question

我做了这样的事情：

compare(value, n)              //n is number of elements in array
if ( n == 0)               //no more elements to compare with
return false
if ( array[n-1] > value)
return true
else
return compare (value, n-1)

有更好的方法吗？我需要先递归地对数组进行排序，然后将最大值与给定值进行比较吗？

Answer 1

检查数组中最大值是否大于给定值的递归算法

您的算法是正确的，但您没有比较数组中最大的值，而是比较任何大于给定值的值。(比较最大的需要遍历整个阵列。(

所以你必须证明它，作为评论：

if (array[n-1] > value)
//     array[n-1] > value  /  largest_array_value >= array[n-1]  =>
// =>  largest_array_value > value 
// (No need to search the entire array for the largest array value.)

我会改为n == 0:

if (n <= 0)

Answer 2

您的算法工作正常，解决问题需要O(N(时间。但由于您使用的是递归，当n太大时，可能会出现stackOverflow问题。可以使用循环来避免这种情况。

int compare(value, n) {
for(int i=0;i<n;i++){
if (array[i] > value) {
return array[i]; //You can also return 1 here.
}
}
return 0;
}

关于是否对该数组进行排序的问题，实际上取决于您对compare(value，n(函数的使用情况。

排序需要O(N.logN(的时间复杂性。所以，如果你只使用这个函数1次或某个常数K次，那么你的算法本身就是好的。无需排序。它将在O(K.N(次上工作，本质上是O(N(。

但如果你要使用这个比较函数N次或更多次，那么时间复杂度就变成了O(N^2(。在这种情况下，明智的做法是先对数组进行排序，然后检查第一个元素是否大于值。排序需要O(N.logN(时间，检查第一个元素需要O(1(时间。所以总的时间复杂度是O(N.logN(。您可以使用合并排序或快速排序来获得O(N.logN(排序。

Answer 3

这是分而治之的版本。

compare_range(value, n, m):
if m <= n
return false
if n+1 == n
return array[n] == value
mid = (n+m)//2
return compare_range(value, n, mid) or compare_range(value, mid, m)

这仍然需要O(n)。但是调用堆栈从未超过大小O(log(n))。