算法设计与实现个人课程总结

1、算法课程总结指导教师所在院（系）班 级学生姓名学 号一、算法概述什么是算法？算法是解一确定类问题的任意一种特殊的方法。在计算机科学中，算法是使 用计算机解一类问题的精确、有效方法的代名词。算法是一组有穷的规则，它规 定了解决某一特定类型问题的一系列运算。算法的五个重要特性：确定性、能行性、输入、输出、有穷性/有限性。确定性：算法每种运算必须有确切定义，不能有二义性。能行性：算法中有待实现的运算都是基本的运算，原理上每种运算都能 由人用纸和笔在有限的时间内完成。输入：每个算法有0个或多个输入。这些输入是在算法开始之前给出的 量，取自于特定的对象集合一一定义域输出：一个算法产生一个或多个输出，这些

2、输出是同输入有某种特定关 系的量。有穷性/有限性：一个算法总是在执行了有穷步的运算之后终止。计算过程：只满足确定性、能行性、输入、输出四个特性但不一定能终止的一 组规则。准确理解算法和计算过程的区别：不能终止的计算过程：操作系统；算法是“可 以终止的计算过程”；算法的时效性：只能把在相当有穷步内终止的算法投入到 计算机上运行。算法的语言主要有：自然语言，流程图，盒图，PAD图，伪代码，计算机程序 设计语言。算法分类：多项式时间算法：可用多项式(函数)对其计算时间限界的算法。常见的 多项式限界函数有：。(1) 。(logn) 0 (n) 0 (nlogn) 0 (n2) 0 (n3)指数时间算法

3、：计算时间用指数函数限界的算法。常见的指数时间限界 函数：0 (2n) 0(n!) 0 (nn)算法基本工具：循环与递归，算法与数据结构，优化算法的数学模型。主要算法：迭代算法，蛮力法，分治法，动态规划法，贪婪算法，图搜索基础。二、算法的核心是思想我们学习这门课不是仅仅掌握那几个经典算法例子，更重要的是为了学习蕴 含在其中的思想方法。为什么呢？举个例子。有同学曾问我这样一个问题：1000 只瓶子装满水，但有一瓶有毒，且毒发期为1个星期。现在用10只老鼠在一个 星期内判断那只瓶子有毒，每只老鼠可以喝多个瓶子的水，每个瓶子可以只喝一 点。问如何解决？其实一开始我也一头雾水，但是他提醒我跟计算机领域

4、相关， 我就立马有了思路，运用二进制。因为计算机的最基本思想就是二进制。所以说， 我们不仅要学习算法，更得学习思想方法。算法最基本的设计方法包括分治法，动态规划法，贪婪算法，周游法，回 溯法，分支定界法。我们可利用分治法做快速排序，降低找n个元素中最大元和 最小元的量级，降低n位二进制x和y相乘的量级，做Strassen矩阵乘法等等。 它的思想就是规模很大的问题分解为规模较小的独立的子问题，关键是子问题要 与原问题同类，可以采取平衡法来提高性能。动态规划法是把大问题分解为子问题，但是子问题是重复的，后面的问题可 以利用前面解决过的问题的结果。如构造最优二叉查找树，解决矩阵连乘时最小 计算次数问

5、题，寻找最长公共子序列等等。贪婪算法就是局部最优法，先使局部最优，再依次构造出更大的局部直至整 体。如Kruscal最小生成树算法，求哈夫曼编码问题。周游法就是简单理解就是采取一定的策略遍历图中所有的点，典型的应用就 是图中的深度优先搜索(DFS)和广度优先搜索(BFS)。回溯法就是就是在满足一定的条件后就往前走，当走到某步时，发现不满足 条件就退回一步重新选择新的路线。典型的应用就是8皇后问题，平面点集的凸 包问题和0-1背包问题。分支定界法：它是解决整数规划问题一种最常用的方法。典型应用就是解决 整数规划问题。评价算法性能的方法如平摊分析中的聚集法，会计法和势能法。聚集法就 是把指令分为几

6、类，计算每一类的消耗，再全部叠加起来。会计法就是计算某个 指令时提前将另一个指令的消耗也算进去，以后计算另一个指令时就不必再算 了。势能法计算每一步的势的变化以及执行这步指令的消耗，再将每一步消耗全 部累计。这几种方法都是平摊分析法，平摊分析的实质就是总体考虑指令的消耗时 间，尽管某些指令的消耗时间很大也可以忽略不计。上述三种方法难易程度差不 多，每种方法都有属于它的难点。如聚集法中如何将指令有效分类，会计法中用 什么指令提前计算什么指令的消耗，势能法中如何选取势能。因此掌握这些方法 原理还不够，还要学会去应用，在具体的问题中去判断分析。三、重点学习贪婪算法贪婪+其他算法：由于贪婪往往能大幅化

7、简状态，利用问题的某些“单调性”， 加上贪婪的思想，往往能是问题大幅简化，从而结合其他算法解决问题经典例题: 田忌赛马，利用贪婪来确定状态。分治法分而治之的思想在信息学竞赛中是非常重要的，下面主要介绍一下分治的经 典应用二分查找思想很简单，功能很强大，边界要注意，负数要特判(NOI2010 PIANO) 在非负数范围内的二分一般写法如果是 l :二 mid - 1 或+ 1 则 mid := (l + r) div 2而如果是 r := mid - 1 或 +1 则 mid := (l + r + 1) div 2快速幕ab = (a(b div 2)”2 + ord(odd(b)*a 取模也

8、适用快速排序，归并排序任何一本算法书上都会讲的，这里就略过了，值得一提的是快排记得加上随 机化k := arandom(r - l + 1) + l二分答案(0-1分数规划)当答案满足在解集空间中连续分布时可以使用二分答案，将最优性问题转化 为判定性问题，通常标志：最大值最小等。差分约束系统中有时也需要二分答案以解决最优性问题，顺便能多得到一个 信息。二分答案还有一个优势，那就是已经知道了答案，那就可能可以将一些直接 做必须在线的操作转化为离线操作。0-1分数规划也是经典的利用二分答案来做的一类问题通常是要求你最小化f(x)/g(x)令 ans = f(x)/g(x)，则 f(x) - g(x

9、)*ans = 0重构权，将f(i) -g(i)*ans作为新权值，用相应算法求出一个“最小值”， 判断是否=0，接着二分即可树的分治一般用来解决树上的路径或统计类问题，每次只考虑跟树根有关的信息，然 后递归分治处理树的分治通常有基于点或基于边的分治，基于点的难合，基于边的复杂度太 高，这里只介绍基于点的分治步骤：处理跟当前树根有关的信息，重新计算子树大小，在子树中选择重心 为根，递归到相应子树处理。因为每次选了重心，所以递归总共logn层，每层O(n)的复杂度，总复杂度 就是 O(nlogn)二分搜索直接搜的复杂度是指数级的的话，一般是40左右的数据量，hash 一半，搜 一半，搜后面的时候

10、利用之前的hash信息合并出原问题的解。而直接搜的复杂度达到阶乘级的话n 一般就不超过20 了，做法一般差不多经典例题：POI02szy，NOI2001方程的解数。搜索作为信息学竞赛中的所谓“万能算法”，搜索可以说是计算机学科所具有的 最大特点了，自然地，搜索算法的应用自然也是非常之广泛，除了专门的搜索题， 搜索一般可以用来部分预处理，打表找规律，当然还有骗分。搜索的一般步骤：确定状态选择搜索方式(dfs、bfs)确定产生式规则一一开始搜索。搜索的常见优化方式：改变状态表示这个需要根据题目而定，确定一个漂亮的状态表示，可能就有希望转向记忆 化了，即使不行，搞出一个漂亮的状态表示是解决一道麻烦题

11、的最重要的一步， 再者，调试起来也会容易许多。优化搜索顺序这个优化在多数搜索中能起到摧枯拉朽的提速效果，通常我们选择枝叶较少 的儿子先扩展，例如大名鼎鼎的dancing Links，除了利用双向十字链表去除冗 余状态，每次选择可扩展数最少的儿子扩展同样给它的神速创造了条件。可行性剪枝以及最优性剪枝这是非常常用的剪枝思路之一，因题目而异，在迭代加深搜索中尤为重要一般思路:考虑每次解最多变优多少，从当前的层数来看还有多少改进空间， 如果已经不可能成为解或更新答案则可以剪枝了A*及IDA*算法：本质就是给搜索加上一个满足相容性的估价函数，然 后用估价函数剪枝，理论上很牛B，实际上不常用，因为考场上很

12、难想出满足那 么多条件的估价函数，但记得一些常见模型的估价函数还是有价值的。例如15 数码的估价函数就可以选择除了 0之外每个元素到自己该到的位置的曼哈顿距 离之和，因为每次最多使一个数距离减少1，所以这个估价函数是相容的，再例 如求k短路的A*算法就是用个堆维护min f(s) + g(s) 估价函数就是从汇点 反搜的“反向最短路”的长度。四、总结在计算机软件专业中，算法分析与设计是一门非常重要的课程，很多人为它 如痴如醉。很多问题的解决，程序的编写都要依赖它，在软件还是面向过程的阶 段，就有程序二算法+数据结构这个公式。算法的学习对于培养一个人的逻辑思维 能力是有极大帮助的，它可以培养我们

13、养成思考分析问题，解决问题的能力。作 为IT行业学生，学习算法无疑会增强自己的竞争力，修炼自己的“内功”。经过这门课的学习，我深刻的领悟到数学是一切算法分析与设计的基础。这 门课的很多时间多花在了数学公式定理的引入和证明上。虽然很枯燥，但是有必 不可少。我们可以清晰的看到好多算法思路是从这些公式定理中得出来的，尤其 是算法性能的分析更是与数学息息相关。其中有几个定理令我印象深刻。主定理本门课中它主要应用在分治法性能分析上。例如：T(n)=a*T(n/b)+f(n)，它 可以看作一个大问题分解为a个子问题，其中子问题的规模为b。而f(n)可看作 这些子问题的组合时的消耗。这些可以利用主定理的相关结论进行分析处理。当 f(n)量级高于时，我们可以设法降低子问题组合时的消耗来提高性能。反之我们 可以降低的消耗，即可以扩大问题的规模或者减小子问题的个数。因此主定理可 以帮助我们清晰的分析出算法的性能以及如何进行有效的改进。随机算法中的许多定理的运用在这门课中，我学到了以前从未遇见过的随机算法，它给予我很大的启示。 随机算法不随