Data_Structure 绪论

概念和术语

• 数据(data) 对客观事物的符号表示，在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号总称，其含义非常广泛，如图像、声音都可以通过编码而归之于数据的范畴
• 数据元素(data element) 数据的基本单位，在计算机程序中有时候也作为整体进行考虑和处理。数据元素也可以由若干个数据项(data item)组成，如一本书的书目信息是一个数据元素，而信息中每一项（作者、书名等）都是一个数据项，数据项是数据不可分割的最小单位。
• 数据对象(data object) 性质相同的数据元素的集合，是数据的一个子集。
• 数据结构(data structure) 相互之间存在的一种或多种特定的关系数据元素的集合。通常有以下四种常见数据结构：1.集合 2.线性结构 3.树形结构 4.图状结构或网状结构

常见数据结构(data structure)

• 数据结构是一个二元组：Data_Structure = (D,S),其中D是数据元素的有限集，S是D上关系的有限集。

• 数据结构在计算机中存储称为数据的物理结构，又称为存储结构，包括数据元素的表示和关系的表示。数据元素之间的关系在计算机中有两种不同的表示方法，分别是：顺序映像和非顺序映像，并由此得到两种不同的存储结构：顺序存储结构和链式存储结构，前者(图1.6.a)是借助元素在存储器中的相对位置表示元素之间的逻辑关系，后者(图1.6.b)借助指示元素存储地址的指针(pointer)表示数据元素之间的逻辑关系。

复数存储结构示意图

• 算法(aigorithm)是对特定问题求解步骤的一种描述，它是指令的有限序列，具有5个非常重要的特性：(1) 有穷性 在合法输入值下，算法执行有穷步之后结束，并每一步都可以有穷时间内完成。(2) 确定性 任何条件下算法只有唯一的一条执行路径，即对于相同的输入只能得到相同的输出。(3) 可行性 算法中描述的操作都是可以通过已经实现的基本运算执行有限次实现的。 (4) 输入 一个算法会有零个或若干个输入。(5) 输出 一个算法会有一个或若干个输出，这些输出同输入有着某种特定关系。

• 算法设计的要求： 正确性(correctness) + 可读性(readability) + 健壮性(robustness) + 效率与低存储量需求。（ps：感觉又学了不少英文单词呢。。。）

• 算法效率的度量：
  (1) 事后统计：一看就不是什么正经方法😄，这种方法误差性太大，和硬件运行环境等关系太大。一般都不用这个。
  (2) 事前统计：1. 算法策略 2.问题规模 3.算法语言(一般语言越高级，效率越低) 4.编译机器代码的质量 5.机器指令的执行速度

• 时间复杂度
  问题规模记为n，算法基本操作执行的重复次数记为f(n),则随着规模n的增大，执行时间的增长率和f(n)的增长率一致，称为算法的渐进时间复杂度(asymptotic time complexity)：T(n) = O(f(n))
  eg.
  (a) {++x;}
  (b) for(i=1;i<=n;i++) {++x;}
  (c) for(j=1;j<=n;j++) for(k=1;k<=n;k++) {++x;}
  以上三段程序的时间复杂度分别为：O(1),O(n),O(n^2)，分别称为常量阶、线性阶、平方阶。当然还有其他的对数阶O(log n) 和指数阶O(2^n)等。

不同数量级时间复杂度性状

有些算法的时间复杂度难以确定，对于多项式可以只取增长最快的项，例如对于(n-1)(n-2)／2，可以只取n^2。另外对于一些算法，f(n)还会随着输入的数据不同而变化。例如冒泡排序，此时可以用平均时间复杂度（不推荐），推荐分析最坏情况下的时间复杂度。

• 空间复杂度(space complexity)
  记为：S(n) = O(f(n))
  一段代码本身要占用存储空间，包括指令、常数、变量、输入数据等，此外还需要某些辅助空间。假设输入数据所占空间与算法无关，分析除了输入和程序本身之外的额外空间。如果额外空间对于输入数据来说是个常数，则称此算法为原地工作。如果所占空间依赖于输入，则计算最坏情况下的空间复杂度。（这段话很饶舌有木有，其实就是说你的算法在忽略自身存储需求和输入数据的存储需求之外，这个空间的大小，就酱。）

小记

第一章主要是一些概念和术语，是入门数据结构的基础，因此必须要仔细读一遍，在这里，我也是在阅读过程中记录一些比较重要的概念，还有很多细节需要读课本。1.3小节的抽象数据类型的表示与实现没有记录，主要是介绍了类C语言。
读绪论差不多用了三天的零碎时间吧，一边看一边记笔记，效果还可以。
该文是用markdown格式写的，还没有用过的可以搜搜相关资料，推荐有时间可以学习一下，目测十几分钟就学会了。之前还创建了一个公众号wulierdan（wuli二蛋），取了个这么蛋疼的名字。。。关注之后就可以定期接受推送咯，一起学习，共同进步。