复杂性分析及简单枚举

《复杂性分析及简单枚举》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、复杂性分析及简单枚举算法什么是算法做什么事情，都有一个解决问题基本方法。写程序也是一样，我们在写程序之前，事先需要有一个思路，然后根据自己的思路，用程序设计语言来描述出来，这个思路，我们称为算法。例N×N的矩阵的每一个元素都是整数，求这个矩阵中所有数的和，我们可以设计一个统计变量，用两重循环枚举每一个数，然后将数值统计到统计变量中即可。因此可设计算法如下。Sum:=0;{未统计时，统计变量清0}FORi:=1TOnDOFORj:＝1TOnDOSum:=Sum+a[i,j];{统计}设计算法的基本目标1）正确性（corre

2、ctness）。算法应当满足具体问题的需求。包括给定的输入数据，得到正确的输出结果。2）可读性（readability)。算法要求能便于人的阅读与交流，这样有助于交流、调试和修改。3）健壮性（robustness）。要考虑输入数据非法时，算法也能适当地作出反应或进行处理，而不会产生莫明其妙的输出结果。例如，给出三角形的三条边长，求三角形的面积。要考虑当输入的数据不能构成三角形的情形。4）高效率（efficiency）。算法设计出来后，必须考虑在运行时间和存储空间方面的需求。算法的效率通常是指的算法执行时间。算法必须能在有

3、限步终止，并且在可终止的前提下，算法的效率应尽可能的高。对于同一个问题如果有多个算法可以解决，执行时间短的算法效率高。存储量需求指算法执行过程中所需要的最大存储空间，这两者都与问题的规模有关。例如，要对n个数进行排序，当n越大时，所需的空间和运行的时间跟n有关。时空分析——时间复杂度时间复杂度又称计算复杂度，是指执行程序的计算工作量。同一问题，采用不同的算法，程序的计算工和量是不一样的。衡量一个算法的时间复杂度，可以采用两种方法：执行时间和执行运算次数。执行时间，指在计算机上运行程序从开始到结束所花费的时间。执行时间与计

4、算机配置有关，配置越高的机器，运算速度越快，执行时间越少，反之越多。因计算机配置差异太大，这种方法可取性不高。执行运算次数是根据程序中执行指令条数和语句条数来度量的，它大致等于计算机执行一种简单操作所需时间与算法中简单操作次数的乘积。这种方法不以计算机的配置为依据，而以算法中的操作次数总耗时为依据，耗时越少，执行时间越快；耗时越多，执行时间越慢。这种方法已经被作为衡量时间复杂度的最有效方法。下面通过一个例子来分析简单操作次数。从键盘上读入100个正整数，输出其中最大的数。Max:=0;Fori:=1to100dobegi

5、nread(tmp);iftmp>maxthenmax:=tmp;end;writeln(max);1次100次根据输入数据的情况，最坏为100次。程序执行次数所以，该程序的简单操作数在最坏情况下为201次。在NOI的各类比赛和网上的题库中，每道题在时间上都有详细的要求，比如说有些题要求在1秒钟内出答案，有些题要求在5秒钟内出答案，那么，如何用运算次数估算运行时间呢？运算的快慢与计算机硬件配置有很大的关系，配置越高，运算越快，在1秒钟内的运算次数就越多，反之越少。而且1秒钟能进行的运算次数也只能粗略地估算。一般来说，根据

6、CCF发布在官肉上的现用评测机配置来看，在1秒钟的时限内可以运行1亿的操作次数。为了在给定的时间内跑出题目中的所有数据，在衡量时间复杂度时，应着重考虑输入数据。输入数据包括输入规模和输入情况。用n表示输入规模，当用选择排序法对n个数进排序时，在忽略耗时较少的赋值、交换等操作语句情况下，对应的操作次数如下表：数据规模操作数n=10100n=10010000n=10001000000n=10000100000000不同数据规模对应的操作次数选择排序的时间复杂度为n*n，从表中可以看出，当n成10倍数增长时，操作次数成百倍增长

7、。当某些算法是指数级别时，输入数据的规模稍大一点，就极易超时。所以在编程时，尤其要考虑输入数据的规模。从输入文件中读入n(n=100)个整数，输出第一次出现数字1的位置。Fori:=1tondobeginreadln(num);ifnum=1thenbreak;end;Write(i);输入数据，当第一个数字为1时，操作次数仅有1次；当第n个数字才为1时，操作次数则有n次，两种情况下操作次数相差近n倍。所以同一个程序，当输入数据情况不一样时，操作次数可能会相差很大。因此在计算时间复杂度时，需要考虑输入数据的不同情况。但是

8、，输入情况非常多，每种情况都计算时间复杂度的话，是不现实的。比如本题，数字1出现的位置有n种情况，对应的操作次数也有n种情况。我们用O(n)表示此算法的时间复杂度，n为问题的规模；当语句执行次数为常数时，我们用O(1)表示时间复杂度。根据现在NOI中各类竞赛和各大题库中的题目，对于每组输入数据，都有测试时间限制，我们