算法分析总复习

《算法分析总复习》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、算法分析总复习考试题型：填空、简答、编程、计算。算法的定义：按照某种机械步骤得到问题结果的处理过程。算法的3要素：操作、控制结构、数据结构。算法的3个结构：顺序结构、选择结构、循坏结构。算法的基木性质：冃的性、分布性、冇序性、冇限性、操作性。算法的棊本特征：有穷性、确定性、可行性、输入性、输出性。(前3个是最主要的)算法的(质量)指标：正确性、可读性、稳健性、高效率与低存储量需求。算法的抽象描述：算法二控制结构+原操作算法的表示方式包括：口然语言、流程图、盒图、PAD图、伪代码、程序设计语言。算法分析的任务：利用数学工具，讨论算法的复杂度。评价算法

2、的标准：1)算法实现所消耗的时间;2)算法实现所消耗的存储空间；3)算法应易于理解、易于编码、易于调试。算法复杂度：算法的吋间复朵度•算法的空间复杂度的统称。算法时间复杂度的佔算：1)算法的执行时间二工原操作的执行次数X原操作的执行时间2)算法时间复杂度的数量级的形式：①0(L)称为常数级；②O(Logn)称为对数级；③0(n)称为线性级；④0(")称为多项式级；⑤0(c")称为指数级；⑥0(n!)称为阶乘级;判断时间复杂度的数量级：1)顺序结构的算法的时间复杂度是0(L)；2)循环结构的算法的时间复杂度是0(//)(x：循环的层数)；算法时间复杂

3、度的最坏情况：可操作性最好的，且最有实际价值的，是最坏情况下的时间复杂性。算法的存储量包括：1)输入数据所占空间；2)算法本身所占空间；3)辅助变量所占空间。NP完全问题：多项式复杂程度的非确定性问题，是图灵机在P时间内解决的问题，是世界7大数学难题之一。递归算法设计：就是把一个大型复杂的问题层层转化为一个与原问题相似的规模佼小的问题，逐步求解小问题后，再返冋得到人问题的解。递归与非递归的比较程序可读性代码量大小时间占用空间使用范围设计难度递归易小长大广易非递归难人短小难算法与数据结构：1）计算机处理的问题类型:数值计算问题、非数值性问题。2）算法

4、设计的实质：对实际问题要处理的数据选择一种恰当的存储结构，并在选定的存储结构上设计一个好的算法，实现对数据的处理。好的算法在很大程度上取决于问题小数据所采用的数据结构。3）常用的数据结构的分类：连续存储、链式存储。4）连续存储和链式存储的优缺点比较：①基于存储的考虑：顺序表的存储空间是静态分配的,事先必须明确规定其存储规模;链表不用事先估计存储规模，但存储密度较低。②基于运算的考虑：运算若按序号访问数据元素，则顺序表优于链表；若是比较操作，则链表优于顺序表。③基于环境的考虑：顺序表容易实现；链表的操作是基于指针的。总之，通常较稳定的线性表选择顺序存

5、储；而动态性较强的线性表宜选择链式存储。选学牛会主席问题（P70）的算法分析：先为5个候选人设置5个计数器，然后根据选票分别对5个计数器累加lo即数组用于存储统计结果，而其下标则是输入的原始信息。编程统计身高问题（P71）的算法分析：由于多数统计区间的人小都固定为5,这样用“身高/5〜29”做下标，只须开辟8个元素的数组，对应8个统计档次，即可完成统计工作。统计3科全及格的学生问题（P71）的算法分析：从语文名单中逐一抽出及格学生学号，先在代数名单中查找，若有该学号，则代数也及格了，再在外语名单屮查找，看该学号是否外语也及格了，若仍在，则该学号学生

6、3科全及格，否则至少有一科不及格。语文名单中没有的学号，不可能3科全及格，所以，语文名单处理完后算法就可以结束了。数字编号翻译成英文编号问题（P73）的算法分析：将英文的"zero-nine"存储在数组中，对应下标为“0〜9”。通过求余、取整运算，可以取到编号的各个位数字。用这个数字作下标，止好能找到对应的英文数字。高精度数据X长整数问题（P78）的算法分析：一个高精度数据与一个自然数的乘法运算过程，用一重循环來实现，循环变量i代表当前参与运算的数组下标，d表示存储进位。统计50个学生中至少冇3门成绩高于90分的人数问题(P91)的算法分析：对每个

7、同学，先计算其成绩高于90分的课程科目，若超过3,则累加到满足条件的人数中。用二重循环实现以上过程，外层循环模拟50个同学，内层循环模拟5门课程。开灯问题(P92)的算法分析：定义有n个元素的3数组，它的每个下标变量a[i]视为一灯，i表示其编号。afi]=l表示第i盏灯处于打开状态，汕]=0表示第i盏灯处于关闭状态。通过算术运算a[i]=l-a[i],就能很好地模拟开关灯的操作。数字圆圈问题(P93)的算法分析：数组定义为alnj,则有a[0]-a[n-l]共n个元素。用i代表下标,题目就是顺序将a(i・l)与a(i+l)相乘，通过求余运算求出乘

8、积的最人值和最小值。任意3个数的最小公倍数问题(P97和P136)的算法分析：用蛮力法最方便，但运算吋间最长。警察抓小偷问