文档介绍：计算机软件基础知识
软件基础
算法
算法的基本概念
算法:是一组有穷指令集,是解题方案的准确而完整的描述。通俗地说,算法就是计算机解题的过程。算法不等于程序,也不等于计算方法,程序的编制不可能优于算法的设计。
算法的基本特征:是一组严谨地定义运算顺序的规则,每一个规则都是有效的,是明确的,此顺序将在有限的次数下终止。算法不等于程序,程序不可能优于算法。
基本特性
可行性:根据实际问题设计的算法,执行得到满意结果
确定性:每一步骤必须有明确定义,不允许有多义性。
有穷性:算法必须能在有限的时间内做完。
输入和输出:拥有足够的情报,方可执行。
算法的基本要素
算术运算:+、-、×、÷等
逻辑运算:>、<、=、>=、<=、!=等
关系运算:and、or、not等
数据传输:w、r等
算法中各操作之间的执行顺序
描述算法的工具通常有传统流程图、N-S结构化流程图、算法描述语言等
算法可以用顺序、选择、循环三种基本机构组合而成。
算法基本设计方法
(1)列举法:根据问题,列举所有可能的情况,并用问题中给定的条件检验哪些是需要的,哪些是不需要的。
(2)归纳法:通过列举少量的特殊情况,经过分析,最后找出一般的关系。
(3)递推:是指从已知的初始条件出发,逐次推出所要求的各中间结果和最后结果。
(4)递归:将问题逐层分解的过程。
(5)减半递推技术: “减半”,是指将问题规模减半,而问题性质不变; “递推”,是指重复“减半”过程。
(6)回溯法:分析问题,找出一个解决总线索,然后沿着这个线索逐步试探。
算法效率度量——算法的复杂度
算法的复杂度:时间复杂度、空间复杂度
算法的时间复杂度
算法时间复杂度是指执行算法所需要的计算工作量。
工作量用算法所执行的基本运算次数来度量,而算法所执行的基本运算次数是问题规模的函数,即
算法的工作量=f(n)
算法空间复杂度
算法空间复杂度是指执行这个算法所需要的内存空间。
存储空间包括:①算法程序所占的空间、②输入数据所占的空间、③算法执行过程中所需要的额外空间
数据结构基本概念
能输入到计算机中
并能被计算机程序处理的
符号的集合。
整数(1,2)、实数(,)
字符串(Beijing)、
图形、声音。
数据结构是一门研究数据组织、存储和运算的一般方法的学科。
数据结构基本概念
计算机管理图书问题
图书馆里有各种卡片:有按书名编排的、有按作者编排的、有按分类编排。
如何将查询图书的这些信息存入计算机中既要考虑查询时间短,又要考虑节省空间
数据结构是一门研究数据组织、存储和运算的一般方法的学科。
数据结构基本概念
最简单的办法之一是建立一张表,每一本书的信息在表中占一行,如
数据结构是一门研究数据组织、存储和运算的一般方法的学科。
数据结构基本概念
如何将0,1,2,3,4,5,6,7,8,9这10个数存放在
计算机中能最快地达到你所需要的目的?
目的不同,最佳的存储方方法就不同。
从大到小排列:9,8,7,6,5,4,3,2,1,0
输出偶数:0,2,4,6,8,1,3,5,7,9
数据元素在
计算机中的表示
数据结构是一门研究数据组织、存储和运算的一般方法的学科。
数据结构基本概念
对数据结构中的节点进行操作处理
(插入、删除、修改、查找、排序)
数据结构是一门研究数据组织、存储和运算的一般方法的学科。