数据布局知识详解 第一章 绪论

界说：是信息的载体，是形貌客观毕竟属性的数、字符及全部能输入到盘算机中并被盘算机步调辨认和处理处罚的符号的聚集

数据的组成：

• 整型、实型等数值范例
  
• 字符及声音、图像、视频等非数值范例
  

界说：数据元素是数据的根本单元，通常作为一个整体举行思量和处理处罚，有肯定意义的根本单元，在盘算机中通常作为整体处理处罚，也被称为元素、记录

数据元素组成：由若干数据项组成

界说：构成数据元素的不可分割的最小单元，若干数据项可以组成数据元素。
注：数据项是数据的最小单元

界说：具有雷同性子的数据元素的组合，是数据的子集。

界说：抽象数据构造及与之相干的操纵

• 数据对象
  
• 数据关系
  
• 根本操纵集
  

界说：一个值的聚集和界说在此聚集上的一组操纵的总称

• 用来说明变量或表达式的取值范围
  
• 说明所能举行的操纵
  

• 原子范例
  界说：值不可再分的数据范例
  例子：int整型
  
• 布局范例
  界说：值可以再分为若干因素(分量)的数据范例
  例子：int整型
  
• 抽象数据范例
  界说：值可以再分为若干因素(分量)的数据范例
  例子：int整型
  

界说：相互之间存在一种或多种特定关系的数据元素的聚集

• 逻辑布局
  对标题抽象后举行研究
  
• 存储布局
  对具体细节举行研究
  
• 数据的运算
  

逻辑布局是指数据对象中数据元素之间的逻辑关系，即从逻辑关系上形貌数据。

界说：布局中的数据元素之间只存在一对一的关系

界说：布局中数据元素之间存在非一对一关系

一对多关系

多对多关系

除同属一个聚集外，再无其他关系

界说：数据对象在盘算机中的存储表示，也称为物理布局

数据域：数据元素由若干个数据项构成时，数据项的表示称为数据域

界说：将逻辑上相邻的节点存储在物理位置上也相邻的存储单元中，节点之间的关系由存储单元的连接关系来体现

• 可以实现随机存取（也可以次序存取）
  
• 每个元素占用最少的空间
  

• 只能利用相邻的一整块存储单元，大概产生较多的外部碎片
  

• 随机存取：就是存取第N个数据时，不须要访问前(N-1)个数据，直接就可以对第N个数据操纵
  
• 非随机存取（又称次序存取）：就是存取第N个数据时，必须先访问前(N-1)个数据
  

界说：不要求逻辑上相邻的节点在物理位置上也相邻，借助指示节点存储地址的指针来表示节点之间的逻辑关系

• 不会出现碎片征象，能充实利用全部存储单元
  

• 每个元素因存储指针而占用额外的存储空间
  
• 只能次序存取
  

• 节点内存储单元地址：肯定连续
  
• 相邻节点存储空间：不愿定连续
  

界说：存储元素信息时，创建附加的索引表

• 检索速率快
  

• 附加的索引表额外占用空间
  
• 增、删数据时也要修改索引表，会耗费更多的时间
  

• 索引表的每项称为索引项，索引项的一般情势是<关键字，地址>
  
• 关键字：标识唯一一个节点
  
• 地址：指向上述节点的指针
  

界说：根据节点的关键字直接盘算出该节点的存储地址，形如location = Hash(key)

• 检索、增长和删除节点操纵很快
  

• 散列函数欠好，会出现元素存储单元辩说，办理辩说会增长时间和空间开销
  

• 该方法本质上是次序存储方法的扩展
  
• key：关键字
  
• Hash()：盘算地址的方法，散列函数
  
• location：存储该节点的地址
  

界说：施加在数据上的运算，包罗运算的界说、实现

• 运算的界说：针对逻辑布局，指出运算的功能
  
• 运算的实现：针对存储布局，指出运算的具体操纵步调
  

界说：算法是对特定标题求解步调的一种形貌，它是指令的有限序列，其中的每条指令表示一个或多个操纵

指令能被人或呆板等盘算装置实验，可以是盘算机指令，也可以是我们平常的语言笔墨

为了办理某个或某类标题，须要把指令表示成肯定的操纵序列，操纵序列包罗一组操纵，每一个操纵都完成特定的功能

• 指令1. 打开冰箱门
  
• 指令2. 把大象塞进去
  
• 指令3. 关上冰箱门
  

一个算法必须总是在实验有穷步之后竣事，且每一步都必须在有穷时间内完成。

每一条指令必须有确切的寄义，雷同的输入只能得出雷同的输出，读者对其明白不会产生二义性

算法中形貌的操纵都可以通过已经实现的根本运算实验有限次来实现

有零个或多个输入，这些输入取自于某个特定的对象的聚集

输出是算法举行信息加工后得到的结果，无输出的算法是没故意义的

算法能正确地办理求解标题

• 算法步调没有语法错误
  
• 算法步调对于合法的输入数据可以或许产生满意要求的输出结果
  
• 算法步调对于非法的输入数据可以或许得出满意规格说明的结果
  
• 算法步调对于经心选择的，以致刁难的测试数据都有满意要求的输出结果
  

有助于人们阅读、明白和交换

输入非法数据时，算法能适本地做出反应或举行处理处罚，而不是产生莫名其妙的错误

服从：指时间，服从越高越好，时间短的算法服从高。
存储量：指空间，存储量越低越好，指算法在实验过程中须要的最大存储空间。

• 时间复杂度
  
• 空间复杂度
  

紧张是通过计划好的测试步调和数据，利用盘算机计时器对差异算法体例的步调的运行时间举行比力，从而确定算法服从的高低

• 必须依据算法事先体例好步调，通常须要耗费大量的时间和精力
  
• 时间的比力依靠盘算机硬件和软件等环境因素，偶尔会粉饰算法本身的优劣
  
• 所用的操纵体系、编译器、运行框架等软件的差异，也可以影响它们的结果
  
• 步调的运行时间每每还与测试数据的规模有很大的关系，服从高的算法在小的测试数据面前每每得不到体验
  

在盘算机步调体例前，依据统计方法对算法举行估算

• 算法接纳的战略和方法 —— 算法优劣的根本
  
• 编译产生的代码质量 —— 由软件来支持
  
• 标题标输入规模
  
• 呆板实验指令的速率
  

界说：一个语句在算法中被重复实验的次数

界说：算法中全部语句的频度之和

• n：表示该算法标题标规模
  
• T(n)是该算法标题规模n的函数
  
• 分析时间复杂度，紧张是分析T(n)的数目级
  

界说：最深处循环内语句

界说：用算法的根本运算的频度f(n)来分析

• O：T(n)的数目级
  
• 常见阶的叫法
  O(1)：常数阶；O(2)：线性阶；O(logn)：对数阶；O(n²)：平方阶
  
• 常见T(n)的巨细关系
  O(1)≤O(log₂(n))≤O(n)≤O(n·log₂(n))≤O(n²)≤O(n³)≤O(2ⁿ)≤O(n!)≤O(nⁿ)
  
• 复杂度盘算规则
  
  
  
  • 加法规则
    T(n)=T1(n)+T2(n)=O(f(n))+O(g(n))=O(max(f(n),g(n)))
    
  • 乘法规则
    T(n)=T1(n)T2(n)=O(f(n))O(g(n))=O(f(n)*g(n))
    
  
  
• 影响时间复杂度的因素
  
  
  
  • 标题规模n
    
  • 输入数据的性子（输入数据的初始状态）
    
  
  
• 最坏环境与匀称环境
  
  
  
  • 最坏时间复杂度
    界说：最坏环境下的时间复杂度
    
  • 匀称时间复杂度
    界说：全部输入等概率的环境下，算法渴望运行的时间
    
  • 最好时间复杂度
    界说：最好环境下的时间复杂度
    
  
  

算法的空间复杂度：记为S(n)，表示该算法所斲丧的空间，它是标题规模n的函数

• 递归类：递归步调一般利用公式举行递推
  T(n)=1+T(n-1)=1+1+T(n-2)=···=n-1+T(1)即T(n)=O(n)
  
• 非递归类
  直接计数
  

• 递归类
  
  
  

• 非递归类