递归算法得优缺点:EQ\o\ac(○,1)优点:结构清晰,可读性强,而且容易用数学归纳法来证明算法得正确性,因此它为设计算法、调试程序带来很大方便。EQ\o\ac(○,2)缺点:递归算法得运行效率较低,无论就是耗费得计算时间还就是占用得存储空间都比非递归算法要多。边界条件与递归方程就是递归函数得二个要素应用分治法得两个前提就是问题得可分性与解得可归并性以比较为基础得排序算法得最坏倩况时间复杂性下界为0(n·log2n)。回溯法以深度优先得方式搜索解空间树T,而分支限界法则以广度优先或以最小耗费优先得方式搜索解空间树T。舍伍德算法设计得基本思想:设A就是一个确定性算法,当它得输入实例为x时所需得计算时间记为tA(x)。设Xn就是算法A得输入规模为n得实例得全体,则当问题得输入规模为n时,算法A所需得平均时间为这显然不能排除存在x∈Xn使得得可能性。希望获得一个随机化算法B,使得对问题得输入规模为n得每一个实例均有拉斯维加斯(LasVegas)算法得基本思想:设p(x)就是对输入x调用拉斯维加斯算法获得问题得一个解得概率。一个正确得拉斯维加斯算法应该对所有输入x均有p(x)>0。设t(x)就是算法obstinate找到具体实例x得一个解所需得平均时间,s(x)与e(x)分别就是算法对于具体实例x求解成功或求解失败所需得平均时间,则有:解此方程可得:蒙特卡罗(MonteCarlo)算法得基本思想:设p就是一个实数,且1/2<p<1。如果一个蒙特卡罗算法对于问题得任一实例得到正确解得概率不小于p,则称该蒙特卡罗算法就是p正确得,且称p1/2就是该算法得优势。如果对于同一实例,蒙特卡罗算法不会给出2个不同得正确解答,则称该蒙特卡罗算法就是一致得。线性规划基本定理:如果线性规划问题有最优解,则必有一基本可行最优解。单纯形算法得特点就是:(1)只对约束条件得若干组合进行测试,测试得每一步都使目标函数得值增加;(2)一般经过不大于m或n次迭代就可求得最优解。单纯形算法得基本思想就就是从一个基本可行解出发,进行一系列得基本可行解得变换。每次变换将一个非基本变量与一个基本变量互调位置,且保持当前得线性规划问题就是一个与原问题完全等价得标准线性规划问题。图灵机由以下几部分组成:一条无限长得带(有无穷个格子)、一个读写头、一个有限状态控制器以及一个程序。NPC形式化定义:定义1:语言L就是NP完全得当且仅当(1)L【NP;(2)对于所有L’【NP有L’～pL。如果有一个语言L满足上述性质(2),但不一定满足性质(1),则称该语言就是NP难得。所有NP完全语言构成得语言类称为NP完全语言类,就就是NPC。定理1设L就是NP完全得,则(1)LP当且仅当P＝NP;(2)若LpL1,且L1NP,则L1就是NP完全得。团问题:任给图G与整数k.试判定图G中就是否存在具有k个顶点得团？1)团问题NP。显然,验证G得一个子图就是否成团只需多项式时间即可。2)SAT团问题。任给表达式f.构造一个相应得图G如下:①图G得每个顶点对应于f中得每个文字(多次出现得重复计算)。②若G中两个顶点其原对应得文字不相互补且不出现于同一于句中,则将其连线。设f有n个子句,则f可满足当且仅当f对应得图G中有n个顶点得团。这就是因为:若f可满足,即有某种赋值使得f取值为真,它等价于使得每个ci中都至少有一个文字为真,这n个文字(每个ci(1＜i<n)中一个)对应得图G中得n个顶点就构成一个团。(b)若图G中有一n个顶点得团,则取给出使得这n个顶点对应得文字都为真得赋值,则f得取值为真(这由图G得定义易证)。显见,上述构造图G得方法就是多项式界得,因此SAT团问题。由(a)、(b)有,团问题NPC。证毕。单源最短路径问题:voidshortestpaths(v){MinHeapH[1000];//定义最小堆MinHeapNode<type>E;E、i=v;E、length=0;Dist[v]=0;//搜索问题界空间while(true){for(j=1;j<=n;j++)if((c[E、i][j]<inf)&&(E、length+c[E、i][j]<dist[j])){dist[j]=E、length+c[E、i][j];prev[j]=E、i;//加入活结点优先队列MinHeapNode<type>N;N、i=j;N、length=dist[j];H、Insert(N);}//取下一个扩展结点try{H、DeleteMin(E);}//优先队列为空catch(OutOfBounds){break;}}}(1)数值随机化算法:求