数据结构–绪论(少量基本概念)

作者 : 开心源码 本文共3384个字,预计阅读时间需要9分钟 发布时间: 2022-05-13 共260人阅读

本文是《数据结构(C语言版)》– 清华大学出版社 的读书笔记。

基本概念和术语

数据:(data)是对客观事物的符号表示,在计算机科学中是指所有能输入到计算机中并被计算机程序解决的符号的总称。

数据元素:(Data element)是数据的基本单位,在计算机程序中通常作为一个整体进行考虑和解决,一个数据元素可由若干个数据项 组成,数据项是构成数据元素不可分割的最小单位

7dd49858803a4b80aaebb0faf05d1221png

数据对象: (Data Object)是性质相同的数据元素的集合是数据的一个子集

数据结构:(Data Structure)是相互之间存在一种或者多种特定关系的数据元素的集合。数据元素之间的关系成为结构。(一组具备相同结构的值)

3219e7b62ab74dd0afba01014a4e39dfpng

数据结构的形式定义为:数据结构是一个二元组

Data_Structure = (D, S)
D:数据元素的有限集
S:D上关系的有限集

结构定义中的关系形容的是数据元素之间的逻辑关系,因而又称为数据的逻辑结构。数据结构在计算机中的表示(又称映像)称为数据的物理结构,它包括数据元素的表示和关系的表示。

数据元素之间的关系

  • 顺序映像: 顺序存储结构;借助元素在存储器中的相对位置来表示数据元素之间的逻辑关系。
  • 非顺序映像: 非顺序存储结构链式、索引、散列(哈希);借助指示元素存储地址的指针表示数据元素之间的逻辑关系。

虚拟存储结构: 数据结构在C虚拟解决器中的表示

2c5c553b53a442a8808657ce00ed1ceepng

顺序存储: 把逻辑上相邻的元素存储在物理位置上也相邻的存储单元中,元素之间的关系由存储单元的相邻关系来表现。

链式存储: 逻辑上相邻的元素在物理位置上可以不相邻,借助元素存储地址的指针来表示元素之间的逻辑关系。

索引存储: 在存储信息的同时,还建立附加的索引表。索引表中的每项称为索引项,索引项的一般形式是<Key,Addr>

散列存储: 根据元素的关键字直接计算出该元素的存储地址,又称哈希(Hash)存储。

数据运算

施加在数据上的运算包括运算的定义和实现,运算的定义是指针对逻辑结构的,指出运算的功能;运算的实现是针对存储结构的,指出运算的具体操作步骤。

数据类型

数据类型:(Data Type)一个值的集合和定义在这个值集上的一组操作的总称。

高级程序语言中的数据类型:

  • 原子型:不可分解
  • 结构型:
    • 可分解
    • 由若干成分按照某种结构组成
    • 可以是结构的,也可以是非结构的

笼统数据类型: (Abstract Data Type 简称ADT)一个数学模型以及定义在该模型上的一组操作。笼统数据类型和数据类型实质上是一个概念。

例如:
整型

  • 不同解决器上实现的方法可以不同
  • 数学特性相同
  • 在客户看来都是相同的

笼统的意义在于数据类型的数学笼统特性

原子类型: 变量的值是不可分解的。
固定聚合类型: 值由确定数目的成分按照某种结构组成,如:复数,由两个数依确定的次序关系构成。
可变聚合类型: 值的成分数目不确定

笼统数据类型(D, S, P)

D:数据对象
S:D上关系集
P:D的基本操作

多数据类型: (Polymorphic data type)是指其值的成分是不确定的数据类型

※ 算法和算法分析

算法

算法(Algorithm)是对特定问题求解步骤的一种形容,它是指令的有限序列。其中每一条指令表示一个或者多个操作。算法还具备下列5个重要特性。

  • 有穷性: 一个算法必需总是(合法的输入值)在执行有穷步之后结束,且每一步都可在有穷时间内完成。
  • 确定性: 每一条指令必需有确切的含义,不能产生二义性。在任何条件下算法只有唯一的一条执行路径,即对于相同的输入只能得出相同的输出。
  • 可行性: 算法中形容的操作都可以通过已经实现的基本运算执行有限次来实现。
  • 输入: 一个算法有0个或者多个的输入
  • 输出: 一个算法有一个或者多个的输出

算法可以没有参数。

算法设计的要求

  • 正确性: (correctness)算法应当满足具体问题的需求(正确反映需求)
    • a. 程序不含语法错误
    • b. 程序对于几组输入数据能够得出满足规格说明要求的结果
    • c. 程序对于精心选择的类型,苛刻带有刁难的几组输入数据能够得出满足规格说明要求的结果。
    • d. 程序对于一切合法的输入数据都能产生满足规格说明要求的结果。
  • 可读性:(readability)算法主要是为了人的阅读与交流,其次才是机器执行。
  • 健壮性: (robustness) 当输入数据非法时,算法也能适当地做出反应或者进行解决,而不会产生莫名其妙的输入结果。
  • 效率与低存储量需求: 效率指的是算法执行的时间,执行时间短的算法效率高。存储量指的是算法执行过程中所需的最大存储空间。

算法效率的度量。

基本操作

测定运行时间
: 测定运行时间的最可靠方法就是计数对运行时间有贡献的基本操作的执行次数。运行时间与这个计数成正比。

下表中列举了少量基本操作的例子。

程序基本操作
排序一组整数比较两个整数
把一个文件复制到另一个文件复制一个字节
把两个多项式相加把两个系数相加

重要的是程序所实现的算法
: 在分析程序的运行时间时,重要的是把程序看成算法,即独立于实现它的程序设计语言的一系列步骤。

例子:多项式求值,在多项式求值中通常乘法比加法慢。因而,乘法是主导的基本操作。

输入规模

基本操作与输入规模
: 在分析一个算法的运行时间时,重要的是把基本操作的数量与输入规模关联起来,即基本操作的数量必需表示成输入规模的函数。

算法输入规模
排序n:要排序的整数的个数
文件复制n:输入文件中的字节数量
多项式加法n:第一个多项式的次数
m:第二个多项式的次数

函数的渐近增长

假设存在两个如下两个算法A和B。
A = 3n-10\\ B = 2n+10
当n=20时,A与B的比较次数相等。当n>20时,B的比较次数小于A的比较次数。即B比A快(这里的快指运行时间,也可以了解为执行的基本操作次数少)。

显然,在比较次数中,重要的是与n相乘的常数,而不是加或者减的常数。因而,当作为n的函数测定运行时间时,可以忽略这些加法常数。

函数的渐近增长
: 给定两个函数f(x) \text{和} g(n),假如存在一个整数N,使得对于所有的n>N,f(n)总是比g(n)大,那么,我们就说f(n)的增长渐近快于g(n)。

考虑两个执行相同任务的算法P和Q
\begin{array}{ll} f_p(n)=4n+20\\ f_q(n)=2n^2-10 \end{array}

nf_pf_q
54040
1060190
20100790
502204990

显然与f_p相比较f_q是在跳跃式的增长。这是由于的f_q主导项是二次的,而f_p的主导项只是线性的(次数为1),即便前者的乘积常数比后者的小,f_q还是比f_p增长的快,在这种情况下,与主导项相乘的常数不重要。

P的线性运行时间与Q的二次运行时间属于不同的级别,或者不同的复杂度的阶。我们说Q的运行时间是n^2阶的,而P的运行时间是n阶的。


阶与大O

在比较算法的运行时间时,重要的是确定运行时间去除了乘法常数和加法常数后的阶。有相同运行时间阶的算法被认为是处于相同的速度水平。记号O成为大O,是阶的一种简捷记法。因而,用O(n)表示“阶为n”,用O(n^2)表示“阶为n^2”。

大O

给定两个函数f(n)和g(n),f(n)=O(g(n))当且仅当存在一个常数c使得c*g(n)的增长渐近快于f(n)。

假设f(n)=4n+20且g(n)=n。那么,对于c=5,c*g(n)的增长渐近快于f(n),所以,f(n)=4n+20=O(n)。换句话说,4n+20是阶n的(或者它的阶是n)。

推导大O

  1. 用常数1取代运行时间中所有的加法常数(减法可以了解为加一个负数)。
  2. 在修改后的运行时间中,只保留最高阶项
  3. 假如最高阶项不是1,去除与这个项相乘的常数。剩下的就是大O阶

求多项式的阶

多项式求值P=a_{n}x^{n}+a_{n-1}x^{n-1}+a_{n-2}x^{n-2}+...+a_{3}x^{3}+a_{2}x^{2}+a_{1}x,

在多项式的计算中通常乘法比加法慢。因而,乘法是主导的基本操作。假设有一个次数为n的多项式,并且各项系数均不为0。

常规解法
使用常规解法就必需求下列各幂的值。
x^n,\;x^{n-1},\;x^{n+2},\;x^{n-3},\;...\;,\;x^3,\;x^2,\;x^1
第一项执行n-1次乘法,第二项是n-2以此类推,执行乘法的总数是
(n-1)+ (n-2) + (n-3) + ... + 3 + 2 + 1 = \frac{n(n-1)}{2} = \frac{n^2}{2} - \frac{n}{2}
除常数外,每项需要与系数的一次乘法,总共是n次,因而总的乘法次数是
\frac{n^2}{2} - \frac{n}{2} + n = \frac{n^2}{2} + \frac{n}{2}

根据上面的步骤推导出大O的阶为n^2

使用霍纳法则
使用霍纳法则求值多项式,只要要进行n此乘法就可,所以说运行时间是O(n)。

典型运行时间的阶

典型的运行时间的阶有:常数阶、线性阶、二次阶、对数阶、三次阶、指数阶。

运行时间阶非正式术语
10O(1)常数
3n+25O(n)线性
1.5n^2+25n-55O(n^2)二次
250n+10n\log{n} + 25O(n\log{n})en\quad log \quad en
3\log{n}+30O(\log{n})对数
10n^3+2nO(n^3)三次
12 * 2^nO(k^n)指数

阶的相对顺序
1 < \log{n} < \sqrt{n} < n < n\log{n}< n\sqrt{n}<n^2<n^3<k^n

阶的算术运算

阶函数中的变量
: 对于出现在算法输入规模中的每一个变量,算法的运行时间的阶函数中至多有一项包含该变量。

如O(n + n\log{n}),由于项n\log{n}是主导项,所以应该写成O(n\log{n}),相似的如O(n + n^2)应写为O(n^2)。


最坏情况与平均情况

负责度的最坏情况
: 通常,计算机科学家使用“时间复杂度”指运算时间需求,并使用“空间复杂度”指空间需求。当不用限定词地使用“复杂度”时,他们通常指时间复杂度。另外,假如他们没有特指平均情况或者最坏情况,一般指的是最坏情况。

一个算法的空间需求总是小于或者等于它的时间需求。

说明
1. 本站所有资源来源于用户上传和网络,如有侵权请邮件联系站长!
2. 分享目的仅供大家学习和交流,您必须在下载后24小时内删除!
3. 不得使用于非法商业用途,不得违反国家法律。否则后果自负!
4. 本站提供的源码、模板、插件等等其他资源,都不包含技术服务请大家谅解!
5. 如有链接无法下载、失效或广告,请联系管理员处理!
6. 本站资源售价只是摆设,本站源码仅提供给会员学习使用!
7. 如遇到加密压缩包,请使用360解压,如遇到无法解压的请联系管理员
开心源码网 » 数据结构–绪论(少量基本概念)

发表回复