《计算机软件技术基础 第1-2-3讲课件》由会员分享，可在线阅读，更多相关《计算机软件技术基础 第1-2-3讲课件（18页珍藏版）》请在金锄头文库上搜索。
1、计算机软件技术基础,徐士良 葛兵 编著 清华大学出版社,第 1 章 算 法,1.1 算法的基本概念,1.2 算法设计基本方法,1.3 算法的复杂度分析,1.1 算法的基本概念,算法：对解题方案准确而完整的描述。（广义） 算法不等于程序，算法不等于计算方法。 （算法是一种解决问题的方案，程序则是具体的语言实现，计算方法则是更为具体的数值计算）,1.1.1 算法的基本特征,算法的基本特征： 能行性。 算法中的每一个步骤必须能够实现。 算法执行的结果要能够达到预期的目的。 确定性。不可以模棱两可，不可以有多义性。,1.1.1 算法的基本特征,有穷性。必须在有限的时间内做完， 拥有足够的情报。 算法：
2、是一组严谨地定义运算顺序的规则，并且每一个规则都是有效的，且是明确的，此顺序将在有限的次数下终止。（狭义）,1.1.2 算法的基本要素 算法的基本要素： 对数据对象的运算和操作； 算法的控制结构。 基本的运算和操作： 算术运算，主要包括加、减、乘、除等运算 逻辑运算，主要包括“与”、“或”、“非”等运算； 关系运算，主要包括“大于”、“小于”、“等于”、“不等于”等运算； 数据传输，主要包括赋值、输入、输出等操作。,算法的控制结构：一个算法的功能不仅取决于所选用的操作，而且还与各操作之间的执行顺序有关。算法中各操作之间的执行顺序称为算法的控制结构。 基本控制结构：顺序、选择、循环。 描述算法的
3、工具：传统流程图、N-S结构化流程图、算法描述语言等。,设每只母鸡值3元，每只公鸡值2元，两只小鸡值1元。现要用100元钱买100只鸡，设计买鸡方案。 假设买母鸡i只，公鸡j只，小鸡k只。,procedure baiji for i=0 to 100 do for j=0 to 100 do for k=0 to 100 do m=i+j+k n=3i+2j+0.5k if (m=100)and(n=100) then output i、 j 、k ,此节内容讲授的是C+程序基础知识，及课本中的程序和课后习题1.1的编写。详见代码。,1.3 算法的复杂度分析,算法的复杂度包括： 时间复杂度 空
4、间复杂度,1.3.1 算法的时间复杂度,算法的时间复杂度：指执行算法所需要的计算工作量。 一个算法是由控制结构（顺序、分支和循环三种）和原操作（指固有数据类型的操作）构成的，则算法时间取决于两者的综合效果。,为了便于比较同一问题的不同算法，通常的做法是，从算法中选取一种对于所研究的问题来说是基本操作的原操作，以该操作重复执行的次数作为算法的时间量度。,Eg)在如下所示的两个N*N矩阵相乘的算法中，“乘法”运算是“矩阵相乘问题”的基本操作。整个算法的执行时间与该基本操作（乘法）重复执行的次数n3成正比，记作 T(n)=O(n3),for (i=1;i=n;+i) for (j=1;j=n;+j) cij=0; for(k=1;k=n;+k) cij+=aik*bkj; ,eg) a)+x;s=0; b)for (i=1;i=n;+i)+x;s+=x; c)for (j=1;j=n;+j) for(k=1;k=n;+k) +x;s+=x;,含基本操作“x增1”的语句的频度分别为：1，n，n2 则三段程序的时间复杂度分别为：O(1),O(n),O(n2),1.3.2 算法的空间复杂度,一个算法的空间复杂度一般是指执行这个算法所需要的内存空间。 一个算法所占用的存储空间包括算法程序所占的空间，输入的初始数据所占的存储空间以及算法执行过程中所需要的额外空间。 Sn=O(f(n),
