日志

重学数据结构(序:概览)

 来源    2020-08-02    0  

@


转眼大学毕业已经一年多,计算机专业四大基础课——《数据结构》、《计算机网络》、《计算机组成原理》、《操作系统》,当时学的实在马虎,到现在已经快要还完了。“基础不牢,地动山摇”,曾经偷过的懒,现在都得给它补回去。

图一:数据结构概览


1、数据结构

1.1、数据结构的起源

1968 年, 美国的高德纳( Donald E.Knuth) 教授在其所写的《计算机程序设计艺术》 第一卷《 基本算法》 中, 较系统地阐述了数据的逻辑结构和存储结构及其操作,开创了数据结构的课程体系。

70 年代初, 出现了大型程序, 软件也开始相对独立, 结构程序设计成为程序设计方法学的主要内容, 人们越来越重视 “数据结构” , 认为程序设计的实质是对确定的问题选择一种好的结构, 加上设计一种好的算法。

程序设计 = 数据结构 + 算 法

1.2、基本概念和术语

  • 数据:是描述客观事物的符号, 是计算机中可以操作的对象, 是能被计算机识别, 并输入给计算机处理的符号集合。
  • 数据元素: 是组成数据的、 有一定意义的基本单位, 在计算机中通常作为整体处理。 也被称为记录。
  • 数据项: 一个数据元素可以由若干个数据项组成。
  • 数据对象: 是性质相同的数据元素的集合, 是数据的子集

来重点看看什么是数据结构:

结构, 简单的理解就是关系, 比如分子结构, 就是说组成分子的原子之间的排列方式。 严格点说, 结构是指各个组成部分相互搭配和排列的方式。 在现实世界中, 不同数据元素之间不是独立的, 而是存在特定的关系, 我们将这些关系称为结构。

那数据结构是什么?

数据结构: 是相互之间存在一种或多种特定关系的数据元素的集合。

在计算机中, 数据元素并不是孤立、 杂乱无序的, 而是具有内在联系的数据集合。 数据元素之间存在的一种或多种特定关系, 也就是数据的组织形式。


1.3、逻辑结构和物理结构

数据元素之间存在一种或多种特定关系,接下来就看看这个关系指的是什么关系。

按照视点的不同, 我们把数据结构分为逻辑结构和物理结构。


1.3.1、逻辑结构

逻辑结构体现的是数据元素之间的逻辑关系, 换句话说就是从操作对象中抽象出来的数学模型, 因此又称为抽象结构, 通常我们习惯说的数据结构一般就是指的逻辑结构。

下面是几种逻辑结构:

图二:集合结构



图三:线性结构


图四:树形结构


图五:图形结构


1.3.1、物理结构

物理结构结构是数据在计算机内的存储形式, 又称存储结构。 它包括数据元素的表示和关系的表示。

数据元素的存储结构形式有两种: 顺序存储和链式存储。

  • 顺序存储

顺序存储结构是把数据元素存放在地址连续的存储单元里, 其数据间的逻辑关
系和物理关系是一致的。

图六:顺序存储


  • 链式存储

链式存储结构是把数据元素存放在任意的存储单元里, 这组存储单元可以是连续的, 也可以是不连续的。 数据元素的存储关系并不能反映其逻辑关系。

图七:链式存储


2、算法

2.1、什么是算法?

先来看看算法的定义:

算法是解决特定问题求解步驟的描述, 在计算机中表现为指令的有限序列, 并且每条指令表示一个或多个操作。

通俗来说,算法是指解决问题的一种方法或者一个过程。 一个问题可以用多种算法来解决, 一个给定的算法解决一个特定的问题。

那么数据结构和算法有什么关系呢?算法和数据结构是焦不离孟的关系。

不了解施加于数据上的算法需求就无法决定数据结构; 反之算法的结构设计和选择又依赖于作为其基础的数据结构。

数据结构为算法提供了工具。 算法利用这些工具来实施解决问题的最优方案。

在计算机领域内, 一个算法实质上是根据处理问题的需要, 在数据的逻辑结构和存储结构的基础上施加的一种运算。

因为数据的逻辑结构和存储结构不是惟一的, 所以算法的描述可能不惟一。 即使逻辑结构和存储结构相同, 算法可能也不惟一。 通过学习数据结构,可以使得程序设计者选择一种比较好的算法。


2.1、算法的特性

算法具有五个基本特性: 输入、 输出、 有穷性、 确定性和可行性。

  • 输入/输出

输入和输出特性比较容易理解, 算法具有零个或多个输入。 尽管对于绝大多数算法来说, 输入参数都是必要的, 但对于个别情况, 如打印 “hello world!”这样的代码, 不需要任何输入参数, 因此算法的输入可以是零个。 算法至少有一个或多个输出, 算法是一定需要输出的, 不需要输出, 那这个算法就没有意义了。

  • 有穷性
    算法在执行有限的步骤之后, 自动结束而不会出现无限循环, 并且每一个步骤在可接受的时间内完成。 现实中经常会写出死循环的代码, 这就是不满足有穷性。

  • 确定性

算法的每一步骤都具有确定的含义, 不会出现二义性。 算法在一定条件
下, 只有一条执行路径, 相同的输入只能有唯一的输出结果。 算法的每个步骤被精确
定义而无歧义。

  • 可行性

算法的每一步都必须是可行的, 也就是说, 每一步都能够通过执行有限次数完成。 可行性意味着算法可以转换为程序上机运行, 并得到正确的结果。

2.2、算法设计要求

设计一个好的算法通常应考虑达到以下目标:正确性、可读性、健壮性、效率与低存储量需求。


2.3、算法分析

算法是解决计算问题的工具。 算法的好与坏直接影响解决问题的效率, 为提高解决问题的效率, 针对一个具体问题的解决方法, 除了需要考虑对算法的具体描述外, 还应具有衡量该算法好坏的方法。

算法的分析主要是指判断算法的优劣, 判断一个算法的好坏一般从两个方面考虑, 即从时间角度和从空间角度上衡量算法。 一般算法分析从时间角度考虑的比较多。 当然判断一个算法的好与坏, 也不能只以时间或空间衡量简单化, 而应该根据实际情况综合考虑。

算法度量主要有这两个方法:

  • 事后统计方法

这种方法的缺点是, 必须先运行依据算法编制的程序; 所花时间的统计量依赖于计算机的软件、 硬件等环境因素, 容易掩盖算法本身的优劣。 因此人们常用第 2 种方法。

  • 事前分析估算方法

一个用高级语言编写的程序在计算机上运行时所消耗的时间取决于下列因素:
• 算法选用何种策略
• 问题规模
• 书写程序的语言
• 编译产生的机器代码质量
• 机器执行指令的速度

当然,抛开硬件方向来讲,算法效率依赖于问题的规模, 或者说, 它是问题规模的函数。

但在实践中, 我们可以把两种方法结合起来使用。一般地, 我们将算法的求解问题的输入称为问题的规模, 并用一个整数 n 表示。 例如, 矩阵乘积问题的规模是矩阵的阶数, 而一个图论问题的规模则是图中的顶点个数或
边的条数。

在算法的每个步骤中, 可能有若干条语句, 而频度就是指每条语句的执行次数。 一个算法的时间复杂度是指算法的时间耗费。

简单地说, 就是以一条基本语句的执行时间为基本单位, 该算法所有语句中总的基本语句的执行次数就是该算法的时间耗费, 它是该算法所求解的问题规模n的函数。 当问题的规模n趋向无穷大时, 我们把时间复杂度的数量阶称为算法的渐进时间复杂度。


2.3.1、时间复杂度

算法时间复杂度定义:

在进行算法分析时, 语句总的执行次数 T ( n ) 是关于问题规模 n 的 函 数 。 进 而 分 析 T ( n ) 随 n 的变化情况并确定 T ( n ) 的 数 量级。 算法的时间复杂度,也就是算法的时间量度, 记作: T ( n )= O(f(n))。它表示随问题规模 n 的增大, 算法执行时间的增长率和f ( n ) 的增长率相同, 称作算法的渐近时间复杂度, 简称为时间复杂度。 其中 f ( n ) 是问题规模 n 的某个函数。

用大写的O()来表示时间复杂度,称之为大O表示法。

图八:大O表示法



2.3.1.1、常数阶

顺序结构的时间复杂度。

例如下面这个算法:

int sum=0,n=100;    //执行1次
        sum=sum+n/2;        //执行1次
        System.out.println(sum);    //执行1次

这个算法的运行次数函数是 f (n) =3。 执行次数不会随着n的变化而增大,所以这个算法的时间复杂度为 O(1)。

除了顺序结构,对于分支结构而言, 无论是真, 还是假, 执行的次数都是恒定的, 不会随着 n 的变大而发生变化 , 所以单纯的分支结构 ( 不包含在循环结构中) , 其时间复杂度也是O(1)。


2.3.1.2、线性阶

线性阶的循环结构会复杂很多。 要确定某个算法的阶次, 我们常常需要确定某个特定语句或某个语句集运行的次数。 因此, 我们要分析算法的复杂度, 关键就是要分析循环结构的运行情况。

for(int i=0;i<n;i++){
            //时间复杂度为O(1)的运算
            System.out.println(n);
        }

上面这个算法的时间复杂度为O(n),因为算法要执行n次。


2.3.1.3、对数阶

看一下下面这个算法,乍一看时间复杂度是O(n)。

int n=10;
        int count=1;
        while (count<n){
            count=count*2;
            //时间复杂度为O(1)的运算
            System.out.println(count);
        }

每次 count 乘以 2 之后, 就距离n更近了一分。 也就是说, 经过log2^n次之后退出循环,所以这个循环的时间复杂度为O(logn)。


2.3.1.4、平方阶

看一下下面这个双循环,把 O(n) 的代码再嵌套循环一遍。它的执行次数是m*n,时间复杂度是O(n²)。

for (int i=0;i<n;i++){
            for (int j=0;i<m;j++){
                //时间复杂度为O(1)的操作
                System.out.println(i*j);
            }
        }

在平方阶上扩展,立方阶O(n³)、K次方阶O(n^k),也都很好理解,3层循环,k层循环。


2.3.2、空间复杂度

空间复杂度是对一个算法在运行过程中临时占用存储空间大小的一个量度,同样反映的是一个趋势,我们用 S(n) 来定义。

S(n)= 0(f(n))

一般情况下, 一个程序在机器上执行时, 除了需要存储程序本身的指令、 常数、变量和输入数据外, 还需要存储对数据操作的存储单元。 若输入数据所占空间只取决于问题本身, 和算法无关, 这样只需要分析该算法在实现时所需的辅助单元即可。 若算法执行时所需的辅助空间相对于输入数据S而言是个常数, 则称此算法为原地工作, 空间复杂度为 0(1)。

通常, 我们都使用 “时间复杂度” 来指运行时间的需求, 使用 “空间复杂度” 指空间需求。 当不用限定词地使用 “复杂度” 时, 通常都是指时间复杂度。





本文为学习笔记类博客,主要资料来源如下!

参考:

【1】:邓俊辉 编著. 《数据结构与算法》
【2】:王世民 等编著 . 《数据结构与算法分析》
【3】: Michael T. Goodrich 等编著.《Data-Structures-and-Algorithms-in-Java-6th-Edition》
【4】:严蔚敏、吴伟民 编著 . 《数据结构》
【5】:程杰 编著 . 《大话数据结构》
【6】:VisuAlgo
【7】:看动画轻松理解时间复杂度(一)

相关文章
重学数据结构——快速排序,二分法查找
日志每次提起快排,内心中都有点隐隐作痛. 当时腾讯的那个面试官让我写快排的前两遍排序结果,结果,我当时居然没写上来…… 这个,就是所谓的关键时刻掉链子吧,这么经典的快排都不会,真是丢死人了…… 今天在实验 ...
1
重学数据结构系列之——平衡树之SB Tree(Size Blanced Tree)
日志学习来源:计蒜客 平衡树 1.定义 对于每一个结点.左右两个子树的高度差的绝对值不超过1,或者叫深度差不超过1 为什么会出现这样一种树呢? 假如我们依照1-n的顺序插入到二叉排序树中,那么二叉排序树就 ...
1
重学计算机 数据结构与算法
日志PS:根据极客时间<数据结构与算法之美 -- 王争>学习总结,极客时间版权所有: https://time.geekbang.org 一.复杂度分析 时间复杂度: 表示方式:大O表示法,表 ...
1
重学JavaScript之面向对象的程序设计(继承)
日志1. 继承 ES 中只支持实现继承,而且其实现继承主要依靠原型链来实现的. 2. 原型链 ES中 描述了 原型链的概念,并将原型链作为实现继承的主要方法.其基本思想是利用原型让一个引用类型继承另一个引 ...
1
重学js之JavaScript 面向对象的程序设计(创建对象)
日志注意: 本文章为 <重学js之JavaScript高级程序设计>系列第五章[JavaScript引用类型]. 关于<重学js之JavaScript高级程序设计>是重新回顾js基 ...
1
前端学数据结构之图
日志前面的话 本文将详细介绍图这种数据结构,包含不少图的巧妙运用 数据结构 图是网络结构的抽象模型.图是一组由边连接的节点(或顶点).图是重要的,因为任何二元关系都可以用图来表示 任何社交网络,例如Fac ...
1
前端学数据结构之树
日志前面的话 前面介绍过一种非顺序数据结构是散列表,本文将详细介绍另一种非顺序数据结构——树,它对于存储需要快速查找的数据非常有用 数据结构 树是一种分层数据的抽象模型.现实生活中最常见的树的例子是家谱, ...
1
前端学数据结构之字典和散列表
日志前面的话 集合.字典和散列表可以存储不重复的值.在集合中,我们感兴趣的是每个值本身,并把它当作主要元素.在字典中,我们用[键,值]的形式来存储数据.在散列表中也是一样(也是以[键,值]对的形式来存储数 ...
前端学数据结构之集合
日志前面的话 本文将详细介绍集合,这是一种不允许值重复的顺序数据结构 数据结构 集合是由一组无序且唯一(即不能重复)的项组成的.这个数据结构使用了与有限集合相同的数学概念,但应用在计算机科学的数据结构中. ...
1
前端学数据结构之链表
日志前面的话 本文将介绍如何实现和使用链表这种动态的数据结构 数据结构 要存储多个元素,数组(或列表)可能是最常用的数据结构.每种语言都实现了数组.这种数据结构非常方便,提供了一个便利的[]语法来访问它的 ...
1
前端学数据结构之队列
日志前面的话 队列和栈非常类似,但是使用了不同的原则,而非后进先出.本文将详细介绍队列的JS实现 数据结构 队列是遵循FIFO(First In First Out,先进先出,也称为先来先服务)原则的一组 ...
1
前端学数据结构之栈
日志前面的话 学习数据结构和算法十分重要.首要原因是数据结构和算法可以很高效地解决常见问题,这对今后的代码质量至关重要(也包括性能,要是用了不恰当的数据结构或算法,很可能会产生性能问题).其次,对于计算机 ...
1
BZOJ 3551: [ONTAK2010]Peaks加强版 Kruskal重构树+dfs序+主席树+倍增
日志建出来 $Kruskal$ 重构树. 将询问点向上跳到深度最小,且合法的节点上. 那么,得益于重构树优美的性质,这个最终跳到的点为根的所有子节点都可以与询问点互达. 对于子树中求点权第 $k$ 大的问 ...
1
重学计算机组成原理(六)- 函数调用怎么突然Stack Overflow了!
日志用Google搜异常信息,肯定都访问过Stack Overflow网站 全球最大的程序员问答网站,名字来自于一个常见的报错,就是栈溢出(stack overflow) 从函数调用开始,在计算机指令层面 ...
1
重学计算机组成原理(九)- 动态链接
日志把对应的不同文件内的代码段,合并到一起,成为最后的可执行文件 链接的方式,让我们在写代码的时候做到了"复用". 同样的功能代码只要写一次,然后提供给很多不同的程序进行链接就行了. ...
1
重学计算机组成原理(七)- 程序无法同时在Linux和Windows下运行?
日志既然程序最终都被变成了一条条机器码去执行,那为什么同一个程序,在同一台计算机上,在Linux下可以运行,而在Windows下却不行呢? 反过来,Windows上的程序在Linux上也是一样不能执行的 ...
重学计算机组成原理(二)- 制定学习路线,攀登“性能”之巅
日志0 学习路线的知识点概括 学习计算机组成原理,就是学习计算机是如何协调运行的 计算机组成原理的英文叫Computer Organization Organization 意"组织机构&quo ...
重学树状数组6/14(P3368 模板 树状数组 2)
日志前几天考了个树状数组的题.....不会 别人都A了 十分丢人 于是回来重学一遍 幸亏60min学会了(我好菜啊) 首先树状数组是一种树形结构,与线段树不同的是它只能查前缀和,只支持单点修改.(以后可能 ...
1
bzoj 3551 kruskal重构树dfs序上的主席树
日志强制在线 kruskal重构树,每两点间的最大边权即为其lca的点权. 倍增找,dfs序对应区间搞主席树 #include<cstdio> #include<cstring> ...
1
(1/18)重学Standford_iOS7开发_iOS概述_课程笔记
日志写在前面:上次学习课程对iOS还是一知半解,由于缺乏实践,看公开课的视频有时不能很好地领会知识.带着问题去学习永远是最好的方法,接触一段时间iOS开发以后再来看斯坦福iOS公开课,又会有许多新的发现, ...
1