复杂性分析及简单枚举.ppt

复杂性分析及简单枚举算法 什么是算法 做什么事情，都有一个解决问题基本方法。写程序也是一样，我们在写程序之前，事先需要有一个思路，然后根据自己的思路，用程序设计语言来描述出来，这个思路，我们称为算法。 例 N×N的矩阵的每一个元素都是整数，求这个矩阵中所有数的和，我们可以设计一个统计变量，用两重循环枚举每一个数，然后将数值统计到统计变量中即可。因此可设计算法如下。 设计算法的基本目标 1）正确性（correctness）。算法应当满足具体问题的需求。包括给定的输入数据，得到正确的输出结果。 2）可读性（readability)。算法要求能便于人的阅读与交流，这样有助于交流、调试和修改。 3）健壮性（robustness）。要考虑输入数据非法时，算法也能适当地作出反应或进行处理，而不会产生莫明其妙的输出结果。例如，给出三角形的三条边长，求三角形的面积。要考虑当输入的数据不能构成三角形的情形。 4）高效率（efficiency）。算法设计出来后，必须考虑在运行时间和存储空间方面的需求。算法的效率通常是指的算法执行时间。算法必须能在有限步终止，并且在可终止的前提下，算法的效率应尽可能的高。对于同一个问题如果有多个算法可以解决，执行时间短的算法效率高。存储量需求指算法执行过程中所需要的最大存储空间，这两者都与问题的规模有关。例如，要对n个数进行排序，当n越大时，所需的空间和运行的时间跟n有关。 时空分析——时间复杂度 时间复杂度又称计算复杂度，是指执行程序的计算工作量。同一问题，采用不同的算法，程序的计算工和量是不一样的。衡量一个算法的时间复杂度，可以采用两种方法：执行时间和执行运算次数。 下面通过一个例子来分析简单操作次数。 从键盘上读入100个正整数，输出其中最大的数。 Max:=0; For i:=1 to 100 do begin read(tmp); if tmpmax then max:=tmp; end; writeln(max); 在NOI的各类比赛和网上的题库中，每道题在时间上都有详细的要求，比如说有些题要求在1秒钟内出答案，有些题要求在5秒钟内出答案，那么，如何用运算次数估算运行时间呢？运算的快慢与计算机硬件配置有很大的关系，配置越高，运算越快，在1秒钟内的运算次数就越多，反之越少。而且1秒钟能进行的运算次数也只能粗略地估算。一般来说，根据CCF发布在官肉上的现用评测机配置来看，在1秒钟的时限内可以运行1亿的操作次数。为了在给定的时间内跑出题目中的所有数据，在衡量时间复杂度时，应着重考虑输入数据。 输入数据包括输入规模和输入情况。用n表示输入规模，当用选择排序法对n个数进排序时，在忽略耗时较少的赋值、交换等操作语句情况下，对应的操作次数如下表： 从输入文件中读入n(n=100)个整数，输出第一次出现数字1的位置。 For i:=1 to n do begin readln(num); if num=1 then break; end; Write(i); 时间复杂度的等级 时间复杂度排序 O(1) O(loglogn) O(logn) O(n) O(n) O(nloglogn) O(nlogn) O(n2) O(n2) O(n３) O(2ｎ) O(n!) O(nｎ) 空间复杂度 与时间复杂度类似，空间复杂度是指一个程序在计算机中执行时所需要的存储空间大小的一个度量，包括程序本身、程序的输入输出相关的全局变量和在运行过程中临时占用的存储空间。 程序本身所占用的空间与程序的长短成正比，要压缩这方面的空间，应使用较短程序的算法，如递归算法。 程序输入输出相关的全局变量占用的空间随题目而异，在题目给出输入输出规模后，就要分配相应的存储单元。 在运行过程中临时占用的存储空间与算法有关，不同的算法有不同的函数参数和局部变量，占用的空间也不一样。 在考虑一个算法的空间复杂度时，一般只需考虑根据题意设定的全局变量的大小和在运行过程中临时战胜的存储空间。 从NOIP2008开始，CCF为联赛规定了内在限制，规定其中静态内存和动态内存占用的空间。静态内存指程序初始时设定的全局变量占用的空间，动态内存指执行程序时形参变量分配的存储空间和函数体或过程体中定义的局部变量等占用的空间。 全局变量占用的空间为静态内存，可以详细地计算出来。计算全局变量占用的空间时，要根据所用的变量类型、数组长度来计算。 例1　判断下列式子的时间复杂度 (1) 3n4+8n2+n+2 (2) 2n+1+n100+5 (3) 12+…+n2 (