C++ 递归查找数组的最小值

标签 c++ recursion

我有一个 c++ 编程类的任务,用于编写一个不使用静态变量的递归函数,其原型(prototype)如下: 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));
    }
}

最佳答案

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

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

#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++ 代码中,如果由于某种原因我们背负着老式的函数签名,我们会这样做:

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++ 递归查找数组的最小值,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/50033943/

相关文章:

c++ - 调试器看到的输出线程 ID

c++ - 引用类型无法使用比较功能

c++ - 显式链接 DLL 和类方法

python - 为什么尾部递归不返回任何因果关系?

c++ - 如何通过函数指针调用不同签名的C++函数

c++ - 从中间 future 创造 future ?

algorithm - 树递归斐波那契算法需要线性空间吗?

java - 在递归函数中初始化变量

java - 如何找到公式的所有可能解,例如 100*7-8*3+7? (10 只猫中有 8 只做倒计时求解器)

java - 递归澄清