《算法与技术重点》由会员分享，可在线阅读，更多相关《算法与技术重点（4页珍藏版）》请在金锄头文库上搜索。
1、算法与技术重点算法与技术重点1.算法：算法：是对特定问题求解步骤的一种描述，它是指令的有限序列。算法具有五大特征：（1）输入：输入：算法有零个或多个输入量（2）输出：输出：算法至少产生一个输出量（3）确定性：确定性：算法的每一条指令都有确切的定义，没有二义性（4）能行性：能行性：算法的每一条指令必须足够基本，它们可以通过已经实现的基本运算执行有限次来实现2.算法可以没有输入，但算法至少应产生一个输出。3.算法算法是由一系列明确定义的基本指令序列所描述的，求解特定问题的过程。它能够对合法的输入，在有限时间内产生所要求的输出。如果取消有穷性限制，只能称作计算过程计算过程。4.可用来描述算法的方法：
2、可用来描述算法的方法：自然语言，流程图，伪代码和程序设计语言5.程序：程序：当一个算法使用计算机程序语言描述时6.欧几里得算法欧几里得算法又称辗转相除法用于计算两个整数 m 和 n（0=0式中，n mod m 表示 n 除以 m 之后的余数。因为 gcd(0,n)=n,n 的最后取值也就是 m 和 n 的最大公约数。例如，gcd（24,60）=gcd（12,24）=gcd（0,12）=12.7.基础情况：基础情况：确认被证明的结论在某种（某些）基础情况下是正确的8.归纳步骤：归纳步骤：这一步又可以分成两个子步：首先进行归纳假设，假定当问题实例的规模小于某个量 K 时，结论成立；然后使用这个假设
3、证明对问题规模为 K 的事例，结论也成立。9.算法的四个重要特性：算法的四个重要特性：1.正确性 2.简明性 3.效率 4.最优性10.健壮性：健壮性：当程序万一遇到意外时，能按某种预定方式作出适当处理11.可靠性：可靠性：一个可靠的程序应当能在正常情况下正确的工作，而在异常情况下，亦能做出适当处理12.影响程序运行时间的因素：影响程序运行时间的因素：（1）程序所依赖的算法 （2）问题规模和输入数据 （3）计算机系统性能13.一个算法的时间复杂度一个算法的时间复杂度是指算法运行所需的时间14.最好情况：最好情况：待查元素恰好是第一个元素，则所需查找时间最短15.最坏情况：最坏情况：待查元素是最
4、后一个元素，所需的查找时间最长16.平均情况：平均情况：需要多次在数组中查找元素，并且假定以某种概率查找每个元素，最典型的是以想等概率查找每个元素，则需平均检索约 n/2 个元素17.程序步：程序步：指在语法上或语义上有意义的程序段，该程序段的执行时间必须与问题实例的规模无关18.固定空间需求：固定空间需求：这部分空间与所处理数据的大小和个数无关，也就是说，与问题实例的特征无关，主要包括程序代码、常量、简单变量、定长成分的结构变量所占的空间19.可变空间需求：可变空间需求：这部分空间大小与算法在某次执行中处理的特定数据的规模有关20.20.大大 O O 记号记号 P19P1921.21. 记号
5、记号 P20P2022.22. 记号记号 P21P2123.)()()log()(log132nOnOnnOnOnOOppppp）（）（24.)() !(2nnnOnOOpp）（25.迭代方法：迭代方法：11 1112 n nnTLLLLLLLL fLLL）（26.一个问题能够用分治法求解的要素是：一个问题能够用分治法求解的要素是：第一，问题能够按照某种方式分解成若干个规模较小，相互独立且与原问题类型相同的子问题；第二，子问题足够小时可以直接求解；第三，能够将子问题的解组合成原问题的解。27.定理定理 5-15-1：设 abc 和 k 为常数，则CT) 1 (,cn+aT(n/b)=T(n)k
6、kkkkkabanbannbanbpLLLLLLfLL如果如果如果)()log()(log28.二分搜索过程的算法行为可以用一颗二叉树来描述29.从根节点到每个内结点的一条路径代表成功搜索的一条比较路径。如果搜索成功，则算法在内结点处终止，否则算法在外结点处终止30.30.性质性质 5-25-2：P72P7231.31.性质性质 5-35-3：P72P7232.32.定理定理 5-45-4：P73P7333.33.定理定理 5-55-5：P73P7334.快速排序：快速排序：P76 里脊肉第一轮快速排序35.快速排序最好情况：快速排序最好情况：O(nlogn)，平均情况：O(nlogn)，最坏
7、情况：)(2nO36.两路合并排序最坏情况：两路合并排序最坏情况：O(nlogn)，平均情况：O(nlogn)，最坏情况：O（nlogn）37.贪心法 P9138.最优量度标准最优量度标准一般并不从整体考虑，他只是在某种意义上的的局部最优选择，也就是说，每一步决策只是在当前看来是最优的，因此，贪心法不能保证对所有问题都得到整体最优解39.背包问题：P9240.普里姆算法普里姆算法适用于边较多的算法，采用邻接表存储 P10941.克里斯卡尔算法克里斯卡尔算法适用于边少的算法，克鲁斯卡尔算法形成的生成森林对应于一个并查集，克鲁斯卡尔算法的时间复杂度为（O（eloge） ）42.贪心法的基本要素：贪
8、心法的基本要素：最优量度标准和最优子结构 P11943.贪心法的特征贪心法的特征是自顶向下44.最优子结构特性：最优子结构特性：当一个问题的最优解中包含了子问题的最优解45.动态规划法动态规划法的实质也是将较大的问题分解为较小的同类子问题，分治法分治法的子问题相互独立，相同的子问题被重复计算，而动态规划法解决了这种子问题重叠现象。贪心法贪心法要求针对问题设计最优量度标准，但这在很多情况下并不容易做到，而动态规划法利用最优子结构，自底向上从子问题的最优解逐步构造出整个问题的最优解，动态规划法可以处理不具备贪心准则的问题46.设计一个动态规划算法，按设计一个动态规划算法，按 4 4 个步骤进行：个
9、步骤进行：（1）刻画最优解的结构特性， （2）递归定义最优解值， （3）以自底向上方式计算最优解值， （4）根据计算得到的信息构造一个最优解47.动态规划求解有两个要素：动态规划求解有两个要素：最优子结构特性和重叠子问题48.动态规划法采用自底向上的方式分步计算49.49.备忘录备忘录 P123P12350.50.关键路径问题：关键路径问题：P127P12751.51.最长公共子序列：最长公共子序列：P137-P138P137-P13852.52.由于每组数组元素的计算时间为由于每组数组元素的计算时间为 O(1)O(1)则程序则程序 7-57-5 时间复杂度为时间复杂度为 O(m*n)P138
10、O(m*n)P13853.53.0/10/1 背包背包 P144P14454.54.使用启发式方法使用启发式方法 P153P15355.使用贪心法和动态规划法求解的一类问题，它们的解都被表示成一个 n-元组56.约束条件：约束条件：用于判定一个候选解是否可行解57.可行解：可行解：满足约束条件的候选解58.目标函数：目标函数：也称代价函数，用于衡量每个可行解的优劣59.最优解：最优解：是目标函数取最大或最小值得可行解60.60.显示约束，隐式约束显示约束，隐式约束 P160P16061.61.剪枝函数和回溯法剪枝函数和回溯法 P161P16162.蒙特卡洛方法：蒙特卡洛方法：用于估计回溯算法处
11、理一个实例时，所实际生成的结点数的方法63.63.回溯法的效率分析回溯法的效率分析 P163P16364.64.回溯法求解回溯法求解 P170P17065.65.图着色算法图着色算法 P171P17166.分枝限界法：分枝限界法：采用广度优先产生状态空间树的结点，并使用剪枝函数的方法67.分枝限界法分为：分枝限界法分为：FIFO 分枝限界法，LIFO 分枝限界法和 LC 分枝限界法68.FIFOFIFO 分枝限界法分枝限界法的活结点表是先进先出队列，LIFOLIFO 是堆栈（即 D-检索）LCLC 是优先权队列；三种不同的活结点表，规定了从活结点表中选取下一个 E-结点的不同次序。LC 分枝限界法将选取具有最高优先级的活结点出队列，成为新的 E-结点
