《算法导论》由会员分享，可在线阅读，更多相关《算法导论（10页珍藏版）》请在金锄头文库上搜索。
1、【分治策略的基本思想】将原问题划分成m个规模较小，而结构与原问题相似的子问题，递归的解决这些子问题，然后再合并其结果，就得到原问题的解【分治策略的基本步骤】分解：将原问题分解为规模更小的子问题解决：如果问题足够小，可以直接解决；否则调用相同的方法求解合并：将子问题的结果合并为原问题的解【两种大整数存储方法】顺序存储、链式存储顺序存储：可以分为静态存储方式和动态存储方式 静态存储方式：数组的大小是事先已经知道的，适合知道大小的整数运算。而因其数组长度是固定不变的，因此在运算时候容易造成溢出，所以不适合不定长度的整数运算 动态存储方式：可以根据大整数位数变化调整大小，而且是连续分配，可随机访问，又
2、没有指针等其他存储开销，空间利用高，是最常用的顺序存储方式 链式存储：可以适应不定长度的大数，这种方式的存储空间包括大整数的表示部分和指针部分，其空间利用率不高，而且存储空间是离散的，所以随机访问效率低直接对两个整数数组对应位元素相加，并考虑进位问题。对数位较大的整数一分为二，第一部分和另一大整数长度相等，先把相同长度部分先计算，然后再对多出的长度部分直接赋值【加法】将字符串转换成字符数组 将字符串数组反转 调用数组加法 将结果转化成字符串型逐位相乘处理进位法：乘积是逐位相乘，也就是aibj，结果加入到积c的第i+j位，最后处理进位 【乘法】转换并反转，字符串转换为数字并将字序反转 逐位相乘，
3、结果存放在result_numi+j中 处理进位，消除多余的0 转换并反转，将计算结果转换为字符串并反转【时间复杂度】概念：算法的基本操作重复执行的次数是模块n的某个函数f(n)，算法的时间复杂度记为T(n)=O(f(n)表示随着模块n的增大，算法执行时间的增长率和f(n)的增长率成正比含义：反应随着问题规模的增长，计算量增长的速度的快慢【证明】对于渐近非负的任意二次函数f(n)=an2+bn+c(a0且a,b,c均为常数)，有f(n)=(n2)渐近正函数渐近确界的确定只与最高阶项的幂数有关，与最高阶项的系数、低阶项、常量无关【渐进符号】【符号】对于给定的函数g(n),记(g(n)=f(n):
4、存在三个正常数c1,c2,n0，对于任给nn0，满足0c1g(n)f(n)c2g(n)的函数集。并记f(n)=(g(n)，它表示f(n)是(g(n)中的一个元素直观含义：f(n)与g(n)同阶【O符号】对于给定的函数g(n),记O(g(n)=f(n):存在c和n0，对于任意nn0，满足0f(n)cg(n)的函数集。并记f(n)=O(g(n)，它表示f(n)是O(g(n)中的一个元素直观含义：f(n)的阶不高于g(n)的阶【符号】对于给定的函数g(n),记(g(n)=f(n):存在c和n0，对于任意nn0，满足0cg(n)f(n)的函数集。并记f(n)=(g(n)，它表示f(n)是(g(n)中的
5、一个元素直观含义：f(n)的阶不低于g(n)的阶【如何求10亿个浮点数中最大的数和最小的数】把n个元素分成两组：A1=A1,.,Aint(n/2)和A2=Aint(n/2)+1,.,An分别求这两组的最大值和最小值，然后分别将这两组的最大值和最小值相比较，求出全部元素的最大值和最小值。如果A1和A2中的元素多于两个，则再用上述方法各分为两个子集。直至子集中元素至多两个元素为止【找出一个无序数组里面前K个最大数】取数组N的前k个数建一个最小堆依次读入其余N-K个数与堆顶元素作比较，若小于或等于堆顶元素，不做操作，若大于，用该数替换堆顶元素并调整堆循环结束后形成的最小堆的所有元素即为所求的K个最大
6、数算法复杂度：建堆O(k) 更新堆O(n-k+(n-k)*lgk)最终的算法复杂度为O(n+(n-k)*lgk)【排名分析】【逆序数】将整个序列分成A和B两个子序列，分别递归将A和B中的元素进行归并排序对于子序列A中的某个数i，子序列B中的某个数j，如果ij，逆序数为子序列A中i后边元素的个数(包括i)，即length(A)-i+1如此遍历下去，即可在归并中得到逆序数分治策略用递归方法实现，递归的时间复杂度为O(logn)每个递归中合并前后两个子序列的时间复杂度是O(n)总的时间复杂度为：T(n) = 2T(n/2) + O(n) 根据master定理，T(n) = O(nlogn)归并排序的
7、复杂度为：T(n) = 2T(n/2) + cn=O(nlogn)【最优化问题】给定若干个约束条件和一个目标函数，在某指定集合中求满足所有约束条件的且使得目标函数值达最大或最小的元素和相应的目标函数值，即求问题的最优值和最优解（或之一）【可行解】指定集合中满足所有约束条件的元素（不一定唯一）【最优解】使目标函数值取最大或最小的可行解（不一定唯一）【最优值】在最优解处的目标函数值（唯一）【最优性原理】给出一个最优的决策序列，每个（连续）子序列自身必须是最优的决策序列【适用动态规划求解的问题的基本要素】具有最优子结构性质、具有重叠子问题【动态规划算法的具体步骤】找出问题的最优子结构分析问题的最优解
8、（最优值）的结构特征递归地定义最优值根据最优子结构，确定最优值所满足的递归公式计算最优值根据最优值的递归公式，自底向上或自顶向下地计算最优值构造最优解根据求最优值时得到的最优解信息构造最优解【动态规划与分治策略】区别：动态规划：分解出的子问题是重叠的 分治策略：分解出的子问题是相互独立的【最优子结构】问题的最优解包含着它的子问题的最优解。即不管前面的策略如何，此后的决策必须是基于当前状态（由上一次决策产生）的最优决策【重叠子问题】在用递归算法自顶向下解问题时，每次产生的子问题并不总是新问题，有些问题被反复计算多次。对每个子问题只解一次，然后将其解保存起来，以后再遇到同样的问题时就可以直接引用，
9、不必重新求解【自底向上】通过反递归实现：调用递归式，子问题逐步往下层递归的求解对给定的输入符号串，从对应文法开始符号的根结点出发，自顶向下地为输入符号串建立一棵分析树实现的关键：根据递归公式正确确定迭代顺序（即子问题的求解顺序）【自顶向下】通过递归实现：直接使用循环来计算所有可能的结果，往上层逐渐累加子问题的解从输入符号串开始，逐步进行归约，直至归约到文法的开始符号实现的关键：对每个子问题标记是否计算过，同一子问题只在第一次递归调用时计算并存储结果 动态规划的式子都是状态P由状态Q1、Q2、Q3之中选择一个或几个计算出来的形式，但是如果一直是一些状态这样递归下去，最后会无限循环的，所以每个式子
10、一直写下去最后都会得到一些状态P是常数（递归边界）的形式。（以上可构造一个DAG）【自底向上】就是已经知道了所有递归边界，把所有可能的状态都算出来。基本步骤是一个拓扑排序的过程，从所有递归边界出发，当一个状态被所有可能的下层状态更新后，就用这个状态去更新后面的状态。直到所求的状态被彻底更新完成为止。【自顶向下】就是不考虑整个图结构，直接从要求的状态开始展开式子，如果式子中的某个状态的值还不清楚，就递归的从这个状态展开。递归结束后式子中的状态都被对应的值替换了，所求状态自然也就清楚了。【编辑距离】两个字符串s1，s2的编辑距离是指把s1和s2变成相同字符串（或者将一个字符串变为另一个字符串）需要
11、下面操作的最小次数 把某个字符ch1变成ch2 删除某个字符 插入某个字符设：从源字符串src1i到目标字符串dest1j的最优编辑距离用ci,j来表示子状态通过编辑距离的3种操作方式状态转移至现在状态插入操作 将ci,j-1转化到ci,j 此时是向src1.i最后增加一个字符转化方程为ci,j=ci,j-1+1删除操作 将ci-1,j转化到ci,j 此时是将src1.i最后一个字符删除转化方程为ci,j=ci-1,j+1替换操作 将ci-1,j-1转化到ci,j 此时考虑srci和destj是否相同，如果相同则不需要替换直接转移状态，如果不同则发生替换操作转化方程为ci,j=ci-1,j-1
12、 srci=destj ci,j=ci-1,j-1+1 srci!=destj而当前状态ci,j到底是从哪种子状态转移得来的，就要比较哪种是最优的选择，即比较这三种转化的最小距离，所以最终得到的转移方程为：【贪心策略的基本思想】在对问题求解时，总是做出在当前看来最好的选择，并不从整体最优考虑，所做出的选择只是在某种意义上的局部最优选择，这种选择依赖于已经做出的选择，但不依赖于未做的选择。贪心策略不能对所有问题都得到整体最优解，但对一些问题它能产生整体最优解或者其近似解【适用贪心策略求解的问题的基本要素】具有贪心选择性质和最优子结构性质【贪心选择性质】所求问题的整体最优解可以通过一系列局部最优选
13、择，即贪心选择来达到算法中每一步选择都是当前看似最佳的选择，这种选择依赖于已经做出的选择，但不依赖于未做的选择【最优子结构性质】问题的最优解包含着它的子问题的最优解 算法中每一次都取得了最优解（即局部最优解），要保证最后的结果最优，则必须满足全局最优解包含局部最优解【贪心策略与动态规划】区别：贪心策略：局部最优选择以自顶向下的方式进行，以迭代的方式作出相继的贪心选择，每作一次贪心选择就将所求问题简化为规模更小的子问题。 动态规划：整体最优选择以自底向上的方式进行，解各子问题相同：都要求问题具有最优子结构性质【如何选择】在所给的活动集合中选出最大的相容活动子集合 先将输入的活动按结束时间非递减排
14、序，并且优先选择最早结束的活动 然后往后依次查找结束时间最近的相容活动加入 具体操作如下： 设已排好序的各个活动构成的集合为S(0，n+1)，最大相容活动集合为A，A初始为空在S(0，n+1)中选择结束时间最早的活动，记为a1，A = A U a1继续选择下一个活动，该活动满足两个条件：与先前已选择的活动相容；是未选择的活动中最早结束的重复上一步直到没有活动可以选择，此时得到的A为最大相容活动集合【理由】这种选择方法可以选出最大的相容活动子集合，为未安排活动留下尽可能多的时间，使剩余的可安排时间段极大化，以便安排尽可能多的相容活动，使最多的活动能相容地使用公共资源，得到最优解【Prim算法】（1）设G=(V,E)是连通无向带权图，V=1,2,n （2）置X=1（3）只要X是V的真子集，就作如下的贪心选择：选取权重最小的边（x,y）,其中xX，yY将边
