文档介绍：软件技术基础
主讲:李琦
计算机学院
四川理工学院
2
目录
第一章数据结构与算法
第二章程序设计基础
第三章软件工程
第四章数据库
3
第一章数据结构与算法
非线性结构
线性结构
数据结构
算法
排序
查找
算法
数据
结构
4
什么是程序?
程序=数据结构+算法
(1)算法是对操作的描述,即操作步骤;解决“做什么”和“怎么做”的问题
(2)数据结构是对数据的描述,包括数据的类型及组织形式
5
算法
算法的基本概念
算法(Algorithm)是指要完成一个任务所需要的具体步骤和方法,即是对解题方案的准确而完整的描述。或者是说给出初始状态或输入数据,能够得出所要求或希望的终止状态或输出的数据。
第一章数据结构与算法
6
算法的基本概念
1. 算法的基本特征
(1)0个或以上的输入
(2)1个或以上的输出
(3)确定性
(4)有限性
(5)有效性
7
算法的基本概念
2. 算法的描述
(1)自然语言。
(2)形式语言。用数学的方法,可以避免自然语言的二义性。
(3)图形,如N-S图、流程图,图的描述与算法语言的描述对应。
(4)算法语言,即计算机语言、程序设计语言、伪代码。
8
算法的基本概念
3. 算法设计基本方法
(1)列举法
(2)归纳法
(3)递推法
(4)递归法
(5)减半递推技术
(6)回溯法
9
算法的复杂度
1. 时间复杂度
时间复杂度(Asymptotic plexity)是指完成一个算法所需要的时间。
一个算法所耗费的时间,是该算法当中每条语句的执行时间之和;而每条语句的执行时间就是该语句的执行次数(也称频度)与该语句执行一次所需时间的乘积。一个算法的时间耗费就是该算法中所有语句的频度之和。
时间复杂度越小,说明该算法效率越高。
10
算法的复杂度
1. 时间复杂度
计算机算法是问题规模n 的函数f(n),算法的时间复杂度被记做:
T(n)=O(f(n))
表示算法执行的时间的增长率与f(n) 的增长率相同。f(n)一般为算法中频度最大的语句频度。