递归算法得优缺点:优点:结构清楚,可读性强,而且容易用数学归纳法来证明算法得正确性,因此它为设计算法、调试程序带来很大方便。缺点:递归算法得运行效率较低,无论就是耗费得计算时间还就是占用得存储空间都比非递归算法要多。边界条件与递归方程就是递归函数得二个要素应用分治法得两个前提就是问题得可分性与解得可归并性以比较为基础得排序算法得最坏倩况时间复杂性下界为 0(n·log2n)。回溯法以深度优先得方式搜索解空间树 T,而分支限界法则以广度优先或以最小耗费优先得方式搜索解空间树 T。舍伍德算法设计得基本思想:设 A 就是一个确定性算法,当它得输入实例为 x 时所需得计算时间记为 tA(x)。设 Xn 就是算法 A 得输入规模为 n 得实例得全体,则当问题得输入规模为 n 时,算法 A 所需得平均时间为这显然不能排除存在 xXn∈使得 得可能性。希望获得一个随机化算法 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
