一、基础篇
1、数据结构基本术语
-
数据:程序的操作对象,用于描述客观事物。
特点: 1.可以输入到计算机。2.可以被计算机处理。 - 数据对象:性质相同的数据元素的集合(类似于数组)。
- 数据元素:组成数据对象的基本单位。
- 数据项:一个数据元素由若干数据项组成。
- 结构: 数据元素之间不是独立的,存在特定的关系.这些关系即是结构;
- 数据结构: 指的数据对象中的数据元素之间的关系
2、逻辑结构和物理结构
2.1、逻辑结构
数据对象中数据元素之间的逻辑关系。分为四种:
-
集合结构
集合结构中的数据元素除了同属于一个集合外,它们之间没有其他关系。各个数据元素是"平等"的。 -
线性结构
数据和数据之间一对一关系
常见:线性表、站、队列、字符串 -
树形结构
数据和数据之间一对多关系 -
图形结构
数据和数据之间多对多关系
2.2、物理结构
物理结构: 又称“存储结构”,指的是数据的逻辑结构在计算机的存储形式。
- 顺序存储结构
-
链式存储结构
不需要提前开辟连续空间
二、算法基础
算法: 算法就是解决特定问题求解步骤
的描述
,在计算机中表现为指令的有限序列, 并且每个指令表示一个或多个操作.
算法特性:
- 输⼊输出
- 有穷性
- 确定性
- 可行性
设计要求(评价标准)
- 正确性
- 可读性
- 健壮性
- 时间效率⾼高和储存量量低
1、复杂度
1.1时间复杂度
大O表示法
- 用常数1取代运行时间中所有常数 3->1 O(1)
- 在修改运行次数函数中,只保留最高阶项 n3+2n2+5 -> O(n^3)
- 如果在最高阶存在且不等于1,则去除这个项目相乘的常数 2n^3 -> n^3
O(1) < O(log n) < O(n) < O(nlog n) < O(n2) < O(n3) < O(2n) < O(n!) < O(nn)
1.2空间复杂度
算法的空间复杂度通过计算算法所需的存储空间实现,算法空间复杂度的计算公式 记做: S(n) = n(f(n)),其中,n为问题的规模,f(n)为语句句关于n所占存储空间的函数。
网友评论