C++递归求数组的最小值 [英] C++ recursively find minimum value of array

问题描述

我有一个 C++ 编程类的赋值，用于编写一个不使用静态变量的递归函数，具有以下原型:int findmin(const int a[], int n);

I have an assignment for a c++ programming class to write a recursive function without the use of static variables, with the following prototype: int findmin(const int a[], int n);

我的解决方案有效(对于非常小的数组)，但是我认为 ~2^n 复杂度过高，可以改进.

My solution works (for very small arrays), however I think ~2^n complexity is excessive and could be improved.

在指定的标准内是否有任何改进可以提高效率?

Are there any improvements that could be made within the specified criteria that would make this more efficient?

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));
    }
}

推荐答案

担心效率有点愚蠢，因为有一种明显的、非递归的方法可以在 O(n) 中一次性完成.甚至还有一个 STL 算法 std::min_element.但是，这是一个愚蠢的任务.首先确保您的解决方案是正确的.当 n==0 时，a[0] 是否有效?一般这样的n表示数组的长度，而不是最低索引.

It's a little silly to worry about efficiency, given that there is an obvious, non-recursive way to do it in O(n), one pass. There is even an STL algorithm std::min_element. But then, it's a silly assignment. FIrst be sure your solution is correct. When n==0, will a[0] be valid? Generally, such an n indicates the length of the array, not the lowest index.

要从 O[n^2] 到 O[n]，请确保每个元素只比较一次.这意味着不是每次都从数组的开头开始.

To go from O[n^2] to O[n], be sure to compare each element only once. That implies not starting at the beginning of the array on every pass.

#include <algorithm>
#include <cassert>

int findmin(const int a[], int n)
{
    assert(n>0);
    if(n == 1)  // See heyah.
        return a[0];
    else
    {
        return std::min(a[0], findmin(a + 1, n - 1));
    }
}

在真正的 C++ 代码中，如果由于某种原因我们背负着老式的函数签名，我们会做这样的事情:

In for-real C++ code, if for some reason we were saddled with the old fashion function signature, we would do something like this:

int findmin(const int a[], int n) {
    if(n<=0) { throw std::length_error("findmin called on empty array");}
    return *std::min_element(a, a+n);
}

这篇关于C++递归求数组的最小值的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！