第一章:绪论
第一章:绪论
一、基本概念
1.Data数据
Data数据:是能够输入计算机且能被计算机处理的各种符号的集合。
Data数据包括:
- 数值型数据:整数、实数
- 非数值型数据:文字、图像、图形、声音等
2.DataElement数据元素
DataElement数据元素(元素/记录/结点/顶点):是Data数据的基本单位,在计算机程序中通常被作为一个整体进行考虑和处理
3.DataItem数据项
DataItem数据项:是构成数据元素的不可分割的最小单位。
数据三者之间的关系:数据 > 数据元素 > 数据项
4.DataObject数据对象
DataObject数据对象:是性质相同的数据元素的集合,是数据的一个子集。
==数据元素与数据对象之间的不同==:
- 数据元素是组成数据的基本单位,是数据集合的个体
- 数据对象是性质相同的数据元素的集合,是数据集合的子集
5.DataStructure数据结构
(1)逻辑结构:
划分方式1 | 说明 |
---|---|
线性结构 | 有且仅有一个开始和一个终端结点,并且所有结点都最多只有一个直接前驱和直接后继。 |
非线性结构 | 一个结点可能有多个直接前驱和直接后继。 |
划分方式2 | 说明 |
---|---|
集合结构 | 结构中的数据元素之间属于同一集合,无任何其他关系 |
线性结构 | 结构中的数据元素存在一对一关系 |
树形结构 | 结构中的数据元素存在一对多关系 |
图/网状结构 | 结构中的数据元素存在多对多关系 |
(2)存储结构:
物理/存储结构:数据元素及其关系在计算机内存中的表示/映像
- 顺序存储结构:用一组连续的存储单元依次存储数据元素,数据元素之间的逻辑关系由元素的存储位置来表示。
- 链式存储结构:用一组任意的存储单元存储数据元素,数据之间的逻辑关系用指针来表示。
- 索引存储结构:在存储结点信息的同时,还建立附加的索引表。
- 散列存储结构:根据结点的关键字直接计算出该结点的存储地址。
(3)数据的运算:
数据的运算:包括运算的定义和实现
- 定义针对逻辑结构,指出运算的功能。
- 实现针对存储结构,指出运算的具体操作步骤。
二、算法分析
算法是对特定问题求解步骤的一种描述,是指令的有限序列(其中每个指令表示一个或多个操作)。
1.算法特性
- 有穷性:一个算法必须总是在执行有穷步之后结束,且每一步都在有穷的时间内完成
- 确定性:对于相同的输入只能得到相同的输出
- 可行性:算法可执行
- 输入:一个算法有零个或多个输入
- 输出:一个算法有一个或多个输出
2.时间复杂度
(1)语句执行次数:
可假设执行每条语句所需要的时间均为单位时间,则对算法运行时间的讨论可转化为讨论算法中所有语句的执行次数,即频度之和。
算法运行时间效率比较 = 算法语句执行次数比较
1 | //两个n*n矩阵相乘的算法时间效率分析 |
(2)时间复杂度的定义:
为了便于比较不同算法的时间效率,我们仅比较他们的==数量级==来粗略的替代执行次数
若有某个辅助函数f(n),使得当n趋近于无穷大时T(n)/f(n)的极限为不等于零的常数,则称f(n)是T(n)的同数量级函数。记作T(n)=O(f(n))
称O(f(n))
为算法的渐进时间复杂度,简称时间复杂度。
(3)时间复杂度的计算:
算法中基本语句重复执行的次数是问题规模n的某个函数f(n)
,算法的时间度量记作T(n)=O(f(n))
==时间复杂度计算步骤==:
- 找出语句频度最大的那条语句作为基本语句
- 计算基本语句的频度,得到问题规模n的某个函数
f(n)
- 取其数量级用符号O表示
- 对于复杂的算法,可以将其分成几个容易估算的部分,然后利用加法规则和乘法规则计算时间复杂度
==时间复杂度分类==:
- 最坏时间复杂度
- 最好时间复杂度
- 平均时间复杂度:所有可能输入实例在等概论出现情况下,算法的期望运行时间
==时间复杂度T(n)按数量级递增顺序为==:
常数阶 | 对数阶 | 线性阶 | 线性对数阶 | 平方阶 | 立方阶 | … | 指数阶 | 阶乘 | |
---|---|---|---|---|---|---|---|---|---|
O(1) | O(log2n) | O(n) | O(nlog2n) | O(n2) | O(n3) | … | O(2n) | O(n!) | O(nn) |
(4)实例分析:
1 | //例1 |
1 | //例2 |
1 | //例3 |
3.空间复杂度
(1)空间复杂度定义:
算法所需存储空间的度量,记作S(n)=O(f(n))
,其中n为问题的规模大小
注:算法本身要占用的空间:输入/输出、指令、常数、变量、辅助空间
(2)空间复杂度计算:
- 普通程序
- 找到所占用空间大小与问题规模相关的变量
- 分析所占空间x与问题规模n的关系
x = f(n)
- x的数量级O(x)即为空间复杂度S(n)
- 递归程序
- 找到递归调用的深度x与问题规模n的关系
x = f(n)
- x的数量级O(x)即为空间复杂度S(n)
- 找到递归调用的深度x与问题规模n的关系
(3)实例分析:
实现将一维数组a中的n个数逆序存放到原数组中(数组逆置):
1 | //算法1:S(n) = O(1)辅助空间为变量temp |
1 | //算法2:S(n) = O(n)辅助空间为数组b[] |
All articles on this blog are licensed under CC BY-NC-SA 4.0 unless otherwise stated.