c++ - C ++递归查找数组的最小值
问题描述
我有一个 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));
}
}
解决方案
担心效率有点傻,因为有一种明显的、非递归的方式可以在 O(n) 中完成,一次通过。甚至还有一个 STL 算法 std::min_element。但是,这是一个愚蠢的任务。首先确保您的解决方案是正确的。当 n==0 时,a[0] 是否有效?通常,这样的 ann
表示数组的长度,而不是最低索引。
要从 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);
}
推荐阅读
- python - EXPEDI - 远征 Spoj Python
- flutter - 验证冻结模型类
- php - JSON文件导入MySQL的不同标签
- java - 在 PHP 中,我们有 santize 以确保 String 是安全的。Java有什么相似之处
- javascript - 如何访问 Next.JS 自定义 404 页面上的当前路由?
- sql-server - 我们是否需要每个微服务都有 SQL Server 容器?3 个微服务需要 3 个 SQL Server 容器?
- android - 从 Facebook 图形 API 检索 Instagram 业务帐户数据
- html - 缩放时如何将按钮保留在 div 中?
- javascript - 用于视频游戏评论的架构 ld+json
- ruby - 微软弃用 EWS 的基本身份验证会影响视点 gem