算法剖析总复习.docVIP

算法分析总复习 第  PAGE 8 页 共  NUMPAGES 8 页 算法分析总复习 考试题型：填空、简答、编程、计算。 算法的定义： 按照某种机械步骤得到问题结果的处理过程。 算法的3要素： 操作、控制结构、数据结构。 算法的3个结构： 顺序结构、选择结构、循环结构。 算法的基本性质： 目的性、分布性、有序性、有限性、操作性。 算法的基本特征： 有穷性、确定性、可行性、输入性、输出性。（前3个是最主要的） 算法的（质量）指标： 正确性、可读性、稳健性、高效率与低存储量需求。 算法的抽象描述： 算法=控制结构+原操作 算法的表示方式包括： 自然语言、流程图、盒图、PAD图、伪代码、程序设计语言。 算法分析的任务： 利用数学工具，讨论算法的复杂度。 评价算法的标准： 1）算法实现所消耗的时间； 2）算法实现所消耗的存储空间； 3）算法应易于理解、易于编码、易于调试。 算法复杂度： 算法的时间复杂度与算法的空间复杂度的统称。 算法时间复杂度的估算： 1）算法的执行时间=原操作的执行次数×原操作的执行时间 2）算法时间复杂度的数量级的形式： ① O(L)称为常数级； ② O(Logn)称为对数级； ③ O(n)称为线性级； ④ O()称为多项式级； ⑤ O()称为指数级； ⑥ O(n!)称为阶乘级； 判断时间复杂度的数量级： 1）顺序结构的算法的时间复杂度是O(L)； 2）循环结构的算法的时间复杂度是O()（x：循环的层数）； 算法时间复杂度的最坏情况： 可操作性最好的，且最有实际价值的，是最坏情况下的时间复杂性。 算法的存储量包括： 1）输入数据所占空间； 2）算法本身所占空间； 3）辅助变量所占空间。 NP完全问题： 多项式复杂程度的非确定性问题，是图灵机在P时间内解决的问题，是世界7大数学难题之一。 递归算法设计： 就是把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题，逐步求解小问题后，再返回得到大问题的解。 递归与非递归的比较程序可读性代码量大小时间占用空间使用范围设计难度递归易小长大广易非递归难大短小窄难算法与数据结构： 1）计算机处理的问题类型： 数值计算问题、非数值性问题。 2）算法设计的实质： 对实际问题要处理的数据选择一种恰当的存储结构，并在选定的存储结构上设计一个好的算法，实现对数据的处理。 好的算法在很大程度上取决于问题中数据所采用的数据结构。 3）常用的数据结构的分类： 连续存储、链式存储。 4）连续存储和链式存储的优缺点比较： ① 基于存储的考虑： 顺序表的存储空间是静态分配的，事先必须明确规定其存储规模；链表不用事先估计存储规模，但存储密度较低。 ② 基于运算的考虑： 运算若按序号访问数据元素，则顺序表优于链表；若是比较操作，则链表优于顺序表。 ③ 基于环境的考虑： 顺序表容易实现；链表的操作是基于指针的。 总之，通常较稳定的线性表选择顺序存储；而动态性较强的线性表宜选择链式存储。 选学生会主席问题（P70）的算法分析： 先为5个候选人设置5个计数器，然后根据选票分别对5个计数器累加1。即数组用于存储统计结果，而其下标则是输入的原始信息。 编程统计身高问题（P71）的算法分析： 由于多数统计区间的大小都固定为5，这样用“身高/5～29”做下标，只须开辟8个元素的数组，对应8个统计档次，即可完成统计工作。 统计3科全及格的学生问题（P71）的算法分析： 从语文名单中逐一抽出及格学生学号，先在代数名单中查找，若有该学号，则代数也及格了，再在外语名单中查找，看该学号是否外语也及格了，若仍在，则该学号学生3科全及格，否则至少有一科不及格。语文名单中没有的学号，不可能3科全及格，所以，语文名单处理完后算法就可以结束了。 数字编号翻译成英文编号问题（P73）的算法分析： 将英文的“zero～nine”存储在数组中，对应下标为“0～9”。通过求余、取整运算，可以取到编号的各个位数字。用这个数字作下标，正好能找到对应的英文数字。 高精度数据×长整数问题（P78）的算法分析： 一个高精度数据与一个自然数的乘法运算过程，用一重循环来实现，循环变量i代表当前参与运算的数组下标，d表示存储进位。 统计50个学生中至少有3门成绩高于90分的人数问题（P91）的算法分析： 对每个同学，先计算其成绩高于90分的课程科目，若超过3，则累加到满足条件的人数中。用二重循环实现以上过程，外层循环模拟50个同学，内层循环模拟5门课程。 开灯问题（P92）的算法分析： 定义有