计算机软件技术基础及实验指导 教学课件 作者 席晓慧 袁玲 第2章 算法.ppt

《计算机软件技术基础及实验指导 教学课件 作者 席晓慧 袁玲 第2章 算法.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第2章算法2.1算法的概念2.1.1算法的基本概念（1）有穷性算法中执行的步骤总是有限次数的，不能无休止地执行下去。（2）确定性算法中的每一步操作的内容和顺序必须含义确切，不能有二义性。（3）可行性算法中的每一步操作都必须是可实现的，也就是说算法中的每一步都能通过所选用的计算机语言中的语句来实现，这称为有效性。（4）输入一个算法中有零个或多个输入。这些输入数据应在算法操作前提供。（5）输出一个算法中有一个或多个输出。算法的目的是用来解决一个给定的问题，因此，它应向人们提供产生的结果，否则，就没有意义了。2.2算法的描述自然语言计算机程序设计语言传统流程

2、图N-S流程图伪代码语言2.3算法的评估2.3.1算法设计的要求1．正确性2．可读性3．效率和低存储量要求4．简单性2.3.2算法效率的度量1．时间度量算法的执行时间需要依据该算法编制的程序在计算机上运行时所消耗的时间来度量。它大致等于计算机执行一种简单操作（如赋值、比较等）所需的平均时间与算法中进行简单操作的次数的乘积。通常把算法中进行简单操作的次数的多少称为算法的时间复杂度，它是一个算法执行时间的相对度量。1）时间复杂度的概念：若所需解决问题的数据规模（数据量）为n，那么算法的时间复杂度就是数据规模n的一个函数f（n），假定时间复杂度记作T（n），

3、则：T(n)=O(f(n))例如，求n个整数的平均值，算法如下：intave(inta[],intn){ints,i;s=0;/*1*/for(i=0;i

4、<=n;i++)for(j=1;j<=n;j++)x=x+1;以上三个程序段的时间复杂度分别为O（1）、O（n）、O（n2），分别称为常量阶、线性阶和平方阶。算法的时间复杂度随问题规模变化的关系可表示为：O(log2n)

5、hlist(inta[],intn,intx){i=0;while(ia[j+1]){t=a[j];a[j]=a[j+1];a[

6、j+1]=t;CHANGE=1;}/*交换两个相临的数*/i++;}}假设a中数据出现n!种排列情况的概率相等，则平均复杂度不会超过n（n1）/2。即该算法的时间复杂度为O（n2）。2．空间度量一个算法在计算机存储器上所占用的存储空间，包括三个方面存储算法本身所占用的存储空间算法中的输入输出数据所占用的存储空间算法在运行过程中临时占用的存储空间算法在执行过程中临时占用的存储空间被定义为算法的空间复杂度算法的空间复杂度包括局部变量所占用的存储空间和系统为实现递归（如果采用递归算法）所占用的堆栈这两个部分。算法的空间复杂度也用数量级的形式给出。S(n)=

7、O(f(n))其中，n为问题的规模。