前言：数据结构与算法作为计算机经典的基础理论课程，同时作为计算机类专业考研课程，并且在校招面试时常被提及，其重要性可见一斑。除此之外，学习这门课程有助于我们用编程去解决、思考问题，设计出更简洁、效率更高的代码。
一.课程概述
-
数据结构课程研究什么？
- 内存中基本数据组织和数据处理的方法
- 非数值问题
-
通过学习数据结构获得什么？
- 经典数据结构和经典算法的基本原理
-
学习重点
- 数据结构的逻辑特性和存储结构设计
- 数据结构算法设计基本方法和分析方法
- 利用数据结构解决实际问题
二.基本概念与术语
-
数据
- 能输入到计算机中，被程序识别和处理的一切事物的符号化表示
-
数据元素
- 数据的基本单位
-
数据项
- 构成数据元素的最小单位
-
存储结构（由想法到算法）
- 顺序存储结构
- 链式存储结构
-
逻辑结构（由问题到想法）
- 一种逻辑结构可由多种存储结构实现
-
数据结构
- 逻辑结构
- 存储结构
- 数据运算
-
抽象数据类型（ADT）
ADT 抽象数据类型名{ 数据对象的定义 数据元素之间的逻辑关系定义 基本运算定义 }ADT -
算法的定义
- 基于存储结构的运算实现的步骤
- 满足有穷性、确定性、可行性
- 有0个或多个输入，1个或多个输出
-
什么是好的算法
- 正确性：对于合法输入，算法能得出正确结果
- 健壮性：对于非法输入，算法能做出特别处理
- 可理解性：算法容易理解、实现
- 高效性：具有较短执行时间并占用较少空间
- 可修改、可拓展性
三.算法分析
-
时间复杂度
- 是算法求解问题规模n的函数，T(n)=F(n)，F(n)是基本语句的执行频度
- 增长率：忽略低次幂和最高次幂系数
-
分析规则
- 加法规则：针对并列程序段
- 乘法规则：针对嵌套程序段
-
例子
++x; //复杂度O(1) for(i=1;i<=n;++i) ++x; //复杂度O(n) for(i=1;i<=n;++i) for(j=1;j<=n;++j) ++x; //复杂度O(n²) -
常见的时间复杂度
O(1)<(log2n)<(n)<(nlog2n)<(n²)<...<(2的n次方)<(n!) -
空间复杂度
- 除去输入输出占用空间，算法临时占用的存储空间
- S(n)=O(f(n))
完整内容可以访问我的个人博客：数据结构 515code.com
