没有合适的资源?快使用搜索试试~ 我知道了~
递归算法的优缺点.doc
1.该资源内容由用户上传,如若侵权请联系客服进行举报
2.虚拟产品一经售出概不退款(资源遇到问题,请及时私信上传者)
2.虚拟产品一经售出概不退款(资源遇到问题,请及时私信上传者)
版权申诉
0 下载量 33 浏览量
2021-10-04
14:23:54
上传
评论
收藏 61KB DOC 举报
温馨提示
试读
9页
递归算法的优缺点.doc
资源推荐
资源详情
资源评论
- -
递归算法的优缺点:
优点:构造清晰,可读性强,而且容易用数学归纳法来证明算法的正确性,因此它为设计
算法、调试程序带来很大方便。
缺点:递归算法的运行效率较低,无论是消耗的计算时间还是占用的存储空间都比非递归
算法要多。
边界条件与递归方程是递归函数的二个要素
应用分治法的两个前提是问题的可分性和解的可归并性
以比拟为根底的排序算法的最坏倩况时间复杂性下界为 0(n·log2n)。
回溯法以深度优先的方式搜索解空间树 T,而分支限界法那么以广度优先或以最小消耗优
先的方式搜索解空间树 T。
舍伍德算法设计的根本思想:
设 A 是一个确定性算法,当它的输入实例为 x 时所需的计算时间记为 tA(x)。设 Xn 是
算法 A 的输入规模为 n 的实例的全体,那么当问题的输入规模为 n 时,算法 A 所需的平均
时间为
这显然不能排除存在 x∈Xn 使得 的可能性。希望获得一个随机化算法 B,使得
对问题的输入规模为 n 的每一个实例均有
拉斯维加斯( Las Vegas )算法的根本思想:
设 p(x)是对输入 x 调用拉斯维加斯算法获得问题的一个解的概率。一个正确的拉斯维加斯
算法应该对所有输入 x 均有 p(x)>0。
设 t(x)是算法 obstinate 找到具体实例 x 的一个解所需的平均时间 ,s(x)和 e(x)分别是算
法对于具体实例 x 求解成功或求解失败所需的平均时间,那么有:
解此方程可得:
蒙特卡罗(Monte Carlo)算法的根本思想:
设 p 是一个实数,且 1/2<p<1。如果一个蒙特卡罗算法对于问题的任一实例得到正确解
的概率不小于 p,那么称该蒙特卡罗算法是 p 正确的,且称 p-1/2 是该算法的优势。
如果对于同一实例,蒙特卡罗算法不会给出 2 个不同的正确解答,那么称该蒙特卡罗算法
是一致的。
线性规划根本定理:如果线性规划问题有最优解,那么必有一根本可行最优解。
单纯形算法的特点是:
〔1〕只对约束条件的假设干组合进展测试,测试的每一步都使目标函数的值增加;
〔2〕一般经过不大于 m 或 n 次迭代就可求得最优解。
单纯形算法的根本思想就是从一个根本可行解出发,进展一系列的根本可行解的变换。每
次变换将一个非根本变量与一个根本变量互调位置,且保持当前的线性规划问题是一个与
- word.zl-
资源评论
pyhm63
- 粉丝: 6
- 资源: 20万+
下载权益
C知道特权
VIP文章
课程特权
开通VIP
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功