认识和理解数据结构里面的概念和术语很重要,这篇主要就是在通读课本第一章绪论之后作的简要笔记。
数据结构是一个二元组: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;} © 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)还会随着输入的数据不同而变化。例如冒泡排序,此时可以用平均时间复杂度(不推荐),推荐分析最坏情况下的时间复杂度。
第一章主要是一些概念和术语,是入门数据结构的基础,因此必须要仔细读一遍,在这里,我也是在阅读过程中记录一些比较重要的概念,还有很多细节需要读课本。1.3小节的抽象数据类型的表示与实现没有记录,主要是介绍了类C语言。 读绪论差不多用了三天的零碎时间吧,一边看一边记笔记,效果还可以。 该文是用markdown格式写的,还没有用过的可以搜搜相关资料,推荐有时间可以学习一下,目测十几分钟就学会了。之前还创建了一个公众号wulierdan(wuli二蛋),取了个这么蛋疼的名字。。。关注之后就可以定期接受推送咯,一起学习,共同进步。