算法+数据结构=程序
基本概念和常用术语
- 数据(data)是描述客观事物的数、字符以及能输入计算机中并被计算机处理的符号的集合。
- 数据元素(data element)是数据的基本单位。
- 数据对象(data object)是具有相同性质的数据元素的集合，是数据的一个子集。比如，大写字母数据对象就是集合{‘A’,’B’,…’Z’}.
数据结构包含的内容
数据结构是带有结构的数据元素的集合。结构指的是数据元素之间的相互关键，即数据的组织形式，结构中的数据元素称为结点。
- 数据元素之间的逻辑(或抽象)关系，也称为数据的逻辑
- 线行数据结构的特征是：数据袁术(结点)之间存在着一对一的关系，并且结构中仅有一个开始结点和一个终端结点，其余结点都是仅有一个直接前趋和一个直接后继.
- 非线性数据结构的特点是：数据元素之间存在着一对多或多对多的关系，即一个结点可能有多个直接前趋和多个直接后继。该结构包括树形结构、图形结构和网状结构等
- 数据元素及其关系在计算机内的存储方式，称为数据的存储接口(物理结构)
- 顺序存储方法
- 链接存储方法
- 索引存储方法
- 散列存储方法
数据结构的逻辑结构、存储结构及运算这三方面看错一个整体
- 数据的运算，即对数据元素施加的操作(行为)
- 检索
- 插入
- 删除
- 更新
- 排序
算法的描述
算法是对问题求解步骤的一种描述。通俗地说，一个算法就是一种解题的方法。严格地说，算法是由若干条指令组成的有穷序列，其中每条指令表示一个或多个操作。
- 输入
- 输出
- 有穷性
- 确定性
- 可行性
算法分析
- 执行算法所耗费的时间，即时间复杂度
- 执行算法所耗费的存储空间，主要是辅助空间，即空间复杂性
- 算法应易于理解，易于编程，易于调试等，即可读性和可操作性
- 算法时间复杂度大O表示法
按数量级递增排序，依次为：常数阶O(1)、对数阶O(log2n)、线性阶O(n)、线性对数阶O(nlog2n)、平方阶O(n2)、立方阶O(n3)、…k次方阶O(nk)、指数阶O(2n)和阶乘阶O(n!)
- 算法空间复制度S(n)
算法空寂复杂度S(n)定义为该算法所耗费的存储空间，它是对一个算法在运行过程中临时占用空间大小的度量，是问题规模n的函数.一个算法在计算机存储器上所占用的存储空间，包括存储算法本身占用的存储空间、算法的输入输出数据所占用的存储空间和算法在运行过程中临时占用存储空间这三个方面