页面顶部广告代码
通知
这是一条没用的通知

01基本概念与算法简介

51人浏览 / 0人评论 | 作者:  | 分类: CS 数据结构  | 

作者:

链接:https://www.anix.xyz/article/ds1_1

声明:请尊重原作者的劳动,如需转载请注明出处


#1 基本术语

数据

- 数、字符及所有能输入到计算机中并被程序识别、处理的符号的集合

- 例如:学生成绩、声音、图像、视频

数据元素

- 数据的基本单位,通常作为一个整体考虑。由若干个数据项组成,也被称为记录、结点、顶点

- 数据项是组成数据元素的不可分割的最小单位

- 例如:学生记录就是一个数据元素,它由学号、姓名、性别等数据项构成

数据对象

- 具有相同性质的数据元素的集合,是数据的一个子集

- 例如:整数;西安人

数据类型

- 一个值的集合和定义在此集合上的一组操作的总和

- 用来说明取值范围、存储方式、所能进行的操作

- 分类:

- 原子类型

    - 值不可再分的数据类型

    - 例如:int整型

- 结构类型

    - 可以再分为若干成分的数据类型

    - 例如:结构体,由int、double、struct等组成

- 抽象数据类型

    - 抽象数据组织及与之相关的操作

    - 例如:抽象类

抽象数据类型(ADT)

- 取出事物具有的普遍性的本质

- 抽象数据组织+相关操作

- ADT组成:

     - 数据对象

     - 数据关系

     - 基本操作

- 例如:排队处理系统中的队列

数据结构

- 相互之间存在一种或多种特定关系的数据元素的集合

- 例如:对抽象类的继承,具体实现;对建筑蓝图的具体实现

#2 数据结构

三要素: 逻辑结构,存储结构,数据的运算,必须要三者相同才能被认为是同一个数据结构

逻辑结构

对问题抽象后进行研究

线性结构 :一一对应关系

    - 线性表

    - 栈

   - 队列

非线性结构:非一一对应关系

   - 树:一对多关系

   - 图:多对多关系

   - 集合:除同属一个集合外,再无其他关系

存储结构

对具体细节进行研究

顺序存储

- 逻辑相邻的结点存储在物理位置相邻的存储单元中

- 优点:随机存取

- 缺点:可能产生较多外部碎片

链式存储

- 由指针表示存储单元的物理位置

- 优点:不会出现碎片现象

- 缺点:因指针域占用额外存储空间,只能顺序存取

索引存储

- 额外存储关键字和地址,<关键字,地址>

- 优点:检索速度快

- 缺点:增加索引表,占用额外空间;增删数据时要修改索引表,花费更多时间

散列存储

- 根据关键字和散列函数计算位置,location=Hash(key)

- 优点:检索、增加、删除结点操作快

- 缺点:散列函数不好会出现元素存储地址冲突、解决冲突会增加时空开销

数据的运算

施加在数据上的运算,包括运算的定义、实现;

定义:逻辑结构

实现:存储结构

- 运算的定义、实现

- 数据+关系=数据结构

- 逻辑结构决定算法设计

- 存储结构决定算法实现

 

#3 算法基本概念

算法的定义

Algorithm

- 算法是对特定问题求解步骤的一种描述,它是指令的有限序列,其中一条指令表示一个或多个操作

 

五大特征

有穷性

    - 在有穷步骤之后能结束,每一步能在有穷时间内完成

    - 死循环的代码就不满足有穷性

    - 持续运行的软件,是一个程序,不是算法,因为不满足有穷性

确定性

    - 每一条指令必须有确切的含义

    - 读者对其理解不会产生二义性

    - 相同输入得到相同的输出

可行性

    - 算法中的操作都能在有限次执行后结束

    - 可以转换为程序上机运行,并得到正确的结果

输入

    - 零个或多个输入

输出

    - 有一个或多个输出

“好”算法

- 正确性、可读性、健壮性、效率与低存储量

 

#4 算法的效率度量

时间复杂度

- 频度:该语句在算法中被重复执行的次数

- 问题的规模n

- 所有语句频度之和T(n)是该算法问题规模n的函数,算法中基本运算(最深层循环的语句)的频度f(n)与T(n)同数量级,算法时间复杂度记为:T(n)=O(f(n))

- 加法规则:T(n)=T1(n)+T2(n)=O(max(f(n),g(n)))

- 乘法规则:T(n)=T1(n)*T2(n)=O(f(n)*g(n))

- O(1)<O(log2n)<O(n)<O(nlog2n)<O(n²)<O(2^n)<O(n!)<O(n^n)

空间复杂度

- 算法消耗的存储空间是问题规模n的函数:S(n)=O(g(n))

- 除存放本身的指令、常数、变量和输入数据外,还要额外辅助空间

- 原地工作:所需辅助空间为常量,即O(1)

 

 

 

点赞(1) 打赏

全部评论

还没有评论!
广告位-帮帮忙点下广告
列表广告代码2