数据结构与算法的一些基础概念

基本数据单位

数据:所有能输入到计算机中去的描述客观事物的符号

数据对象:相同特性数据元素的集合,是数据的一个子集

数据元素:数据的基本单位,也称结点(node)或记录(record)

数据项:有独立含义的数据最小单位,也称域(field)

如下图

基本数据单位

假设有一座学校,这个学校就是数据。那么学校中的老师,学生,教室等就是数据对象。单个老师、学生和教室就是数据元素。单个老师和学生的信息,如姓名身高体重等就是一个个数据项

数据结构

数据结构可以从两个视角划分,分别是逻辑结构物理结构

逻辑结构

逻辑结构是按数据元素间的逻辑关系来划分的,分成集合结构、线性结构、树形结构和图形结构。


集合结构和线性结构

集合结构:一种松散的逻辑结构,元素之间除同属该集合这一联系外没有其他的关系。如哈希表。

线性结构:一对一,集合中必存在唯一的一个“第一个元素”和“最后一个元素”,除最后一个元素之外,其他数据元素均有唯一的"后继",除第一元素之外,其它数据元素均有唯一的"前驱"。如线性表,栈,队列,字符串等。


树形结构

树形结构:一对多,在树形结构中,树根结点没有前驱结点,其余每个结点有且只有一个前驱结点。叶子结点没有后续结点,其余每个结点的后续节点数可以是一个也可以是多个。如二叉树。


图形结构

图形结构:多对多,在图形结构中,任意两个结点之间都可能相关,即结点之间的邻接关系可以是任意的。

其中除了线性结构外的三种又统称为非线性结构

物理结构

物理结构是按数据的物理存储方式来划分的,分成顺序结构链式结构

顺序结构:把逻辑上相邻的结点存储在物理位置上相邻的存储单元中,结点之间的逻辑关系由存储单元的邻接关系来体现。直白点就是用一段连续的地址存放数据元素,数据间的逻辑关系和物理关系相同,便于查询数据。

链式结构:在计算机中用一组任意的存储单元存储线性表的数据元素(这组存储单元可以是连续的,也可以是不连续的).它不要求逻辑上相邻的元素在物理位置上也相邻,便于插入删除。

算法

算法就是解决特定问题求解步骤的描述,在计算机中表现为指令的有限序列列,并且每个指令表示⼀一个或多个操作。也就是说,能够对一定规范的输入,在有限时间内获得所要求的输出。如果一个算法有缺陷,或不适合于某个问题,执行这个算法将不会解决这个问题。不同的算法可能用不同的时间、空间或效率来完成同样的任务。一个算法的优劣可以用空间复杂度时间复杂度来衡量。

算法的特性包括:有穷性确定性可行性输入输出。而评价一个算法的优劣,也不能仅仅依靠空间复杂度和时间复杂度,还需要考虑到其正确性可读性健壮性

大O符号

算法的时间/空间复杂度常用大O符号来表示,大O符号计算时,对于确定的结果都取常数阶1,对于不确定的则只保留最高阶,不保留低阶项和首项系数,其考虑的是一个算法在最坏情况下的复杂度。常见的复杂度如下图

常见复杂度

时间复杂度

相同大小的不同输入值仍可能造成算法的运行时间不同,因此我们通常使用算法的最坏情况复杂度,记为T(n),定义为任何大小的输入n所需的最大运行时间。另一种较少使用的方法是平均情况复杂度,通常有特别指定才会使用。时间复杂度可以用函数T(n) 的自然特性加以分类,举例来说,有着T(n) =O(n) 的算法被称作“线性时间算法”;而T(n) =O(M^n) 和M= O(T(n)) ,其中Mn> 1 的算法被称作“指数时间算法”。

在我看来其实就是计算一个算法需要执行的次数。如

常数阶

其中不管输入n为多少,执行次数都是唯一确定的3次,根据大O表示法则为常数阶O(1)。

线性阶

这段算法则根据输入n的不同,执行次数也不同,需要执行n次,则其复杂度为O(n)。

对数阶

执行次数为log2 n,则其复杂度为O(log n),log2,log3,log10都不用考虑,仅记作log。

平方阶


立方阶

平方阶和立方阶同理,不过只保留最高阶,最高阶的首项系数和其他阶都忽略。

空间复杂度

算法的空间复杂度通过计算算法所需的存储空间实现,算法空间复杂度的计算公式记做: S(n) = n(f(n)),其中,n为问题的规模,f(n)为语句句关于n所占存储空间的函数。我们常说的空间复杂度一般指算法中需要的辅助空间。比如交换数组中元素的位置,如果使用中间变量来实现,那么就只需要一个中间变量,则其空间复杂度就是常数阶O(1);如果用另一个数组来存储的话,则会根据数组元素个数n的不同,使用n个不同的空间,所以其空间复杂度就是O(n)。


参考资料:

https://www.jianshu.com/p/32eca07444d5https://www.cnblogs.com/surenjiesu/p/11514312.html、百度百科。

©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容