我有一个C++编程课的作业,需要写一个递归函数,但不能使用静态变量,函数原型如下: int findmin(const int a[], int n);
我的解决方案能够工作(对于非常小的数组),但我认为2^n的复杂度过高,需要改进。
是否有任何可以在指定条件内提高效率的改进方法?
int findmin(const int a[], int n)
{
if(n == 0)
return a[0];
else
{
if(a[n-1] < findmin(a,(n-1)))
return a[n-1];
else
return findmin(a,(n-1));
}
}
findmin(a,(n-1))
的结果存储起来而不是再次调用它会有所帮助。 - John3136n
表示大小,那么你的算法是错误的(当n == 0
时,a[0]
不应该有效,否则你没有检查a[n]
)。 - Jarod42findMin()
的时间复杂度为O(1)
。 - Joseph D.