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

Question

我有一个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));
    }
}

- Brian

---

将findmin(a,(n-1))的结果存储起来而不是再次调用它会有所帮助。 - John3136

通过递归跳转到数组的最后一个索引。将最后一个元素设为最小元素并返回它。在每次递归展开时，将当前索引元素与答案最小值进行比较，并在必要时更新。 - Brij Raj Kishore

@John3136 我很惊讶这带来了多大的差异，现在似乎以线性复杂度运行。 - Brian

如果 n 表示大小，那么你的算法是错误的（当 n == 0 时，a[0] 不应该有效，否则你没有检查 a[n]）。 - Jarod42

使用堆数据结构。findMin() 的时间复杂度为 O(1)。 - Joseph D.

Answer 1

考虑到存在一种显而易见的非递归方法，使用一次扫描即可以O(n)的效率完成，所以担心效率有些愚蠢。甚至，还有一个STL算法std::min_element。但是这只是一个愚蠢的任务。首先确保你的解决方案是正确的。当n==0时，a[0]是否有效？通常，这样的表示数组的长度而不是最低索引。

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

- Jive Dadson

---

@codekaizer. 它根本不创建任何副本。签名 const int a[] 是从C遗留下来的。我们不再这样做了。（C++新手甚至还不知道它，但这是另一个抱怨。）数组声明 a []“衰减”为指针 int *a。 - Jive Dadson

@codekaizer - "衰变"听起来比"类型腐烂"更好。 - Jive Dadson

@codekaizer - 任选其一，但最终请来这里：https://dev59.com/m3M_5IYBdhLWcg3wPAnU - Jive Dadson

@JiveDadson。我在想用Java实现这个解决方案。但是在C++中，n的含义会有很大的不同。在Java中，数组大小是隐式的，但在C++中则完全不同。非常令人印象深刻的细节捕捉。 - Brij Raj Kishore

在C++中，如果采用简单易行的方式做事情，情况比Java还要好。问题在于，教师们教授学生编写C代码，并使用C++编译器进行编译。由于考虑到向后兼容性的原因，C++保留了许多从C语言继承而来的特性。 - Jive Dadson

Answer 2

你可以使用条件运算符?:来代替一堆if else语句，使函数更加简洁。而且，你可以在语句内部将返回值赋给变量，这是这段代码相对于原始代码的主要优势，避免了两次调用findmin()。

int findmin(const int a[], int n) {
   if (n == 0) // base case
      return a[0];

   return a[n] < (int min = findmin(a, n - 1)) ? a[n] : min;
}

这个代码段 (a[n] < (int min = findmin(a, n - 1)) ? a[n] : min;) 也可以使用 if 语句来实现:

if (a[n] < (int min = findmin (a, n - 1))
     return a[n];
else
     return min;

编辑： 根据多个可靠来源，这是O(n)时间复杂度。如果我们将每个元素与所有其他元素进行比较，则为O(n^2)。

- user5550963

---

@GRG，这是一道作业问题或者任务。直接写答案并不是帮助的正确方式。请指导他正确的方法。 - Brij Raj Kishore

@BrijRajKishore - 在某些情况下，编写答案可能会教导学生不要相信来自互联网的代码。 :-) - Jive Dadson

@BrijRajKishore 有时候一个答案会被投票到+4，尽管它是错误的且时间复杂度为O[n^2]。 - Jive Dadson

@JiveDadson，您能向我解释一下这个算法为什么是O(n^2)吗？ - Brij Raj Kishore

O(n^2)并不意味着步骤数恰好为n^2。(n^2-n)/2是O(n^2)。自己算一下吧，逐步执行算法并计数。将该计数过程转化为数学级数。玩得开心，我完成了。 - Jive Dadson