本文转载：https://xiaochuhe.blog.csdn.net/article/details/122937438
五、算法和数据结构
(一 ) 程序 = 数据结构 + 算法 （瑞士 计算机科学家 尼·沃思）
1. 软件的主体是程序，程序的核心是算法，数据结构能使算法有效的实现
2. 算法和数据结构之间关系密切，算法建立在数据结构基础上，数据结构不同时，对应问题的 求解算法也有差异
(二 ) 算法：
1. 定义：解决问题的方法与步骤
2. 地位：计算机科学就是研究 算法 的学问（尼·沃思）
3. 性质：
（1) 确定性：算法的 每一个运算必须有确切的定义 ，即每一个运算应该执行何种操作必须是 清楚明确的，无二义性
（2) 有穷性 （可终结性）：有限步运算后终止
（3) 能行性 ：算法中有待实现的运算都是 可执行的 ，即在计算机的能力范围之内，且在有限 的时间内能够完成
（4) 输入：具有 0 个或多个输入
（5) 输出 ： 至少 1 个输出
4. 描述工具：
（1) 文字说明、流程图、 伪代码 （介于自然语言和程序设计语言之间的文字和符号表达工具）、 程序设计语、决策表 ……
（2) 根据需要选择使用
5. 算法与程序的区别：
（1) 程序是算法的具体实现
（2) 程序可以无穷，算法必须有穷
（3) 程序中的语句必须是机器可执行的，算法中的操作则不此限
（4) 算法与程序是相应的，但不一一对应
6. 算法分析
（1) 时间代价 ：
A. 定义：依据算法编制为程序后在计算机中运行时所耗费的时间，记为 T（n ）
B. 若 T（ n ） = 2n 3 +3n 2 +2n+1 ，则 T(n) ≈ O(n 3 )
C. 排序（按数量级递增）：常数阶 O(1)、对数阶 O(log 2 n) 、线性阶 O(n) 、线性对数阶 O(nlog2n) 、平方阶 O(n ² ) 、立方阶 (n ³ ) … K 次方阶 O(n K ) 、指数阶 O(2ⁿ) 等
D. 若程序需反复运行多次，则应重点考虑时间代价，选用快速的算法
（2) 空间代价 ： 和求解问题的规模关系密切
7. 算法设计：
（1) 一般采用 由粗到细、由抽象到具体 的逐步求解的方法
（2) 对于同一个问题可采用不同的算法去解决，但不同的算法具有不同的效率
(三 ) 数据结构
1. 内容：
（1) 数据的 逻辑结构 ： 用于抽象地反映数据元素之间的约束关系而不考虑其在计算机中的存 储方式
（2) 数据的 物理存储结构 ： 数据的逻辑结构在计算机存储器上的实现
（3) 数据的 运算
2. 常用的数据结构：
（1) 集合结构
（2) 线性结构（ 线性表是由若干同类 型数据元素组成的有限序列，其中任意两个数据元素之间具有先 后关系 ）
（3) 树形结构
（4) 网状结构六、计算机软件技术
(一 ) 定义：研制开发计算机软件所需的所有技术的总称
(二 ) 组成：软件工程技术、程序设计技术、软件工具环境技术、系统软件技术、数据库技术、网络软 件技术、与实际工作相关的软件技术
(三 ) 软件开发环境：相关的一组软件工具集合，它支持一定的软件开发方法或按照一定的软件开发模 型组织而成
