当前位置： 移动技术网 > 科技>人工智能>机器学习 > 荐 数据结构和算法1-介绍

荐 数据结构和算法1-介绍

2020年07月15日  | 移动技术网科技  | 我要评论

数据结构和算法系列共八篇

1.为什么要学习

为什么要学习开始数据结构？

  • 了解计算底层原理
  • 提升编程能力
  • 基本功，面试常问

推荐网址

再介绍个工具

2.概念

什么是数据、数据项、数据元素、数据对象？

  • 数据：

数据:是描述客观事物的数值、字符以及能输入机器且能被处理的各种符号集合。比如：数值数据、字符、字符串、声音、图像等

  • 数据对象

数据对象（data object ）是性质相同的数据元素的集合，是数据的子集。(比如：数据库一张表)

  • 数据元素

数据元素（data element ）是数据的基本单位，是数据集合的个体，通常由若干个数据项组成，在计算机程序中通常作为一个整体来进行处理。(比如：数据库一张表里的一行记录)

  • 数据项

数据项（data item）具有原子性，是不可分割的最小数据单位。(比如：数据库一张表里的一行记录里的某个列数据)

2.数据结构

数据结构（data structure ）是指相互之间存在一种或多种特定关系的数据元素的集合。(按照表现形式不同分为)

  • 逻辑结构（数据结构的逻辑层面）
  • 存储结构（计算机世界的物理层面）

数据结构=逻辑结构+存储结构+运算

  • 非线
  • 线性表、栈、队列、（字符）串、数组、广义表
  • 非线性
  • 树、二叉树、图
    在这里插入图片描述

2-1.逻辑结构

数据的逻辑结构指数据元素之间的逻辑关系，而不是物理上。

2-1-1.分类1

分类1：线性结构和非线性结构

线性结构 (1对1)

  • 集合中必存在唯一的一个"第一个元素"；
  • 集合中必存在唯一的一个"最后的元素"；
  • 除最后元素之外，其它数据元素均有唯一的"直接后继"；
  • 除第一元素之外，其它数据元素均有唯一的"直接前驱"。

比如：排队，有头有尾，中间一个挨着一个。

非线性结构 (1对多，多对多)
相对应于线性结构，非线性结构的逻辑特征是一个结点元素可能对应多个直接前驱和多个直接后继。

比如：树(二叉树等)，公司组织关系，地铁交通图

2-1-2.分类2

分类2：集合结构、线性结构、树状结构、网络结构

  • 集合结构

set，元素之间没有关系独立的，没有重复

  • 线性结构

数据结构中线性结构指的是数据元素之间存在着1:1的线性关系的数据结构。

  • 树状结构

除了一个数据元素以外每个数据元素有且仅有一个直接前驱元素，但是可以有多个直接后续元素。特点是数据元素之间是1:n的联系

  • 网络结构

每个数据元素可以有多个直接前驱元素，也可以有多个直接后续元素。特点是数据元素之间是n:n的联系

img

2-2.存储结构

数据的存储结构主要包括数据元素本身的存储以及数据元素之间关系表示，是数据的逻辑结构在计算机中的表示。（物理的，逻辑在物理上的体现）

常见的存储结构有顺序存储，链式存储，索引存储，以及散列存储。

2-2-1.顺序存储

把逻辑上相邻的节点存储在物理位置上相邻的存储单元中，结点之间的逻辑关系由存储单元的邻接关系来体现

img
数据元素的存储对应于一块连续的存储空间，数据元素之间的前驱和后续关系通过数据元素。(java中的数组，ArrayList)

优点：

  • 节省存储空间，因为分配给数据的存储单元全用存放结点的数据（不考虑c/c++语言中数组需指定大小的情况），结点之间的逻辑关系没有占用额外的存储空间。
  • 采用这种方法时，可实现对结点的随机存取，即每一个结点对应一个序号，由该序号可以直接计算出来结点的存储地址。

缺点：

  • 插入和删除操作需要移动元素，效率较低。
  • 必须提前分配固定数量的空间，如果存储元素少，可能导致空闲浪费。

2-2-2.链式存储

数据元素的存储对应的是不连续的存储空间，每个存储节点对应一个需要存储的数据元素。(逻辑上相邻的节点物理上不必相邻)

img
数据元素的存储对应的是不连续的存储空间。(java中的LinkedList)

优点：

  • 插入、删除灵活 (不必移动节点，只要改变节点中的指针)。
  • 有元素才会分配结点空间，不会有闲置的结点。

缺点：

  • 比顺序存储结构的存储密度小 (每个节点都由数据域和指针域组成，所以相同空间内假设全存满的话顺序比链式存储更多)。
  • 查找结点时链式存储要比顺序存储慢。

2-2-3.索引存储

除建立存储结点信息外，还建立附加的索引表来标识结点的地址。

书本的目录，字典的拼音和部首，数据库的表的索引，lucene、es等

2-2-4.散列存储结构

根据结点的关键字直接计算出该结点的存储地址 HashSet HashMap

img

3.算法

算法是针对于存储结构操作的，而不是逻辑结构。这是很显然的(逻辑是虚拟的，而存储是实际的)。

算法四种境界

  • 境界1：听懂理论、听懂算法思路 (理论家、眼高手低，总比不知道强多了)
  • 境界2：完成主要数据结构基本算法的实现（理论+实践，数据结构入门了）
  • 境界3：完成更多数据结构更多算法的实现（进步提高数据结构功底）
  • 境界4：融会贯通、举一反三，在后续开发中综合应用数据结构知识（数据结构就是哲学思想，只要和实践结合才能学好）

学习数据结构不是一日之功，对于初学者要达到境界2，后续学习和工作中不断研究学习

3-1.算法是什么

是指令的集合，是为解决特定问题而规定的一系列操作。

算法是利用计算机解决问题的处理步骤，简而言之，算法就是解决问题的步骤。

img

算法通常来说具有以下特性：

  • 输入：一个算法应以待解决的问题的信息作为输入。
  • 输出：输入对应指令集处理后得到的信息。
  • 可行性：算法是可行的，即算法中的每一条指令都是可以实现的，均能在有限的时间内完成。
  • 有穷性：算法执行的指令个数是有限的，每个指令又是在有限时间内完成的，因此整个算法也是在有限时间内可以结束的。
  • 确定性：算法对于特定的合法输入，其对应的输出是唯一的。即当算法从一个特定输入开始，多次执行同一指令集结果总是相同的。

示例：如何求0+1+2+3+…100=?

对于一个问题，可能有多种方法来解决这个问题。

  • 高斯解法
  • 循环
  • 递归求解

出现这么算法，那那种算法好了？

这就引出了算法的优劣判断方法：

  • 空间复杂度: 指执行这个算法所需要的内存空间
  • 时间复杂度: 指执行算法所需要的计算工作量

3-2.空间复杂度

Space Complexity

3-2-1.是什么

空间复杂度是对一个算法在运行过程中临时占用的存储空间大小的量度，一般也作为问题规模n的函数，以数量级形式给出S(n) = O(g(n))

算法的存储量包括:

  • 输入数据所占空间
  • 程序本身所占空间
  • 辅助变量所占空间

输入数据所占空间只取决于问题本身，和算法无关，不参与计算。

3-2-2.计算

演示1

int fun(int n){   
	int i，j，k，s; 
    	s=0;
    	for (i=0;i<=n;i++)           
       		for (j=0;j<=i;j++)  	
           			for (k=0;k<=j;k++)     
              			s++; 
    	return(s);
}

不管for循环了多少层，但是只定义了几个变量。没有参数多余的空间。空间复杂度均为S(n)=O(1)。

演示2

void fun(int a[]，int n，int k) 
   //数组a共有n个元素
 {	int i;
	if (k==n-1)
	   for (i=0;i<n;i++)　　
	   	printf(“%d\n”，a[i]);  //执行n次
	else
	{  for (i=k;i<n;i++)
		a[i]=a[i]+i*i;	　　//执行n-k次
	   fun(a，n，k+1);
	}
 }

递归算法，每次调用本身都要分配空间，fun(a,n,0)的空间复杂度为O(n)。

上面两种算法比较：

  • 对于递归算法来说，代码一般都比较简短，算法本身所占用的存储空间较少，但运行时需要占用较多的临时工作单元；
  • 若写成非递归算法，代码一般可能比较长，算法本身占用的存储空间较多，但运行时将可能需要较少的存储单元。

3-3.时间复杂度

Time Complexity

3-3-1.时间频度

一个算法需要花多少时间，可能跟机器的位数、性能等有关系，而且每次跑花的时间都可能不一样。
但是一点它们是相同的，那就是算法语句执行的次数是固定的。可以这么认为：哪个算法中语句执行次数多，它花费时间就多。

一个算法中的语句执行次数称为语句频度或时间频度，表示为T(n)，n表示问题的规模

3-3-2.时间复杂度

有时只像知道它变化时呈现什么规律(比如：指数级的)，而不是具体的次数，此时引入时间复杂度。

上面介绍过时间频度T(n)，当某个辅助函数f(n)，使得当n趋近于无穷大时，T(n)/f(n)的极限值为不等于零的常数，则称f(n)是T(n)的同数量级函数。

T(n)=O(f(n)) 其中：O(f(n))为算法的渐进时间复杂度，简称时间复杂度

时间复杂度就是时间频度去掉低阶项和首项常数

比如：T(n)=99n3+10000n2+1T(n)=99n^3+10000n^2+1 和 T(n)=n3T(n)=n^3，它们的时间复杂度是一样的都是T(n)=O(n3)T(n)=O(n^3)

用哪个计算？(最坏时间复杂度还是平均时间复杂度？)

最坏情况下的时间复杂度称最坏时间复杂度。一般不特别说明，讨论的时间复杂度均是最坏情况下的时间复杂度。
这样做的原因是：最坏情况下的时间复杂度是算法在任何输入实例上运行时间的上界，这就保证了算法的运行时间不会比任何更长。
在最坏情况下的时间复杂度为T(n)=O(n)，它表示对于任何输入实例,该算法的运行时间不可能大于O(n)。

平均时间复杂度是指所有可能的输入实例均以等概率出现的情况下，算法的期望运行时间。鉴于平均复杂度

3-3-3.计算

根本没有必要计算时间频度，即使计算处理还要忽略常量、低次幂和最高次幂的系数，所以可以采用如下简单方法：

  • 找出算法中的基本语句

算法中执行次数最多的那条语句就是基本语句，通常是最内层循环的循环体。

  • 计算基本语句的执行次数的数量级

只需计算基本语句执行次数的数量级，这就意味着只要保证基本语句执行次数的函数中的最高次幂正确即可，
可以忽略所有低次幂和最高次幂的系数。这样能够简化算法分析，并且使注意力集中在最重要的一点上：增长率。

  • 用O记号表示算法的时间性能

将基本语句执行次数的数量级放入大O记号中。

演示1

int count=0;

时间复杂度为O(1)

演示2

int count=0, count=1; 
...省略n行...
int count=1000;

不管多少行，时间复杂度为O(1)

演示3

int n=10000, count=0;
for (int i=1; i<=n; i++)
    count++;

for循环，不管n是多少值(1、1百、1万、一亿)，只关注是一个for循环，时间复杂度为O(n)

演示4

int n=10000, count=0;
for (int i=1; i<=n; i*=2)
    count++;

for循环,但是按着2幂来出现(1、2、4、8、16、32…)
时间复杂度为O(log⁡2n)O(\log_2^{n})的循环语句。

演示5

int n=1000, count=0;
for (int i=1; i<=100n; i++) 
    for (int j=1; j<=10n; j++)
        count++;

for循环，不管n是多少值(1、1百、1万、一亿)，只关注是两个for循环，时间复杂度为 O(n2)O(n^2)

演示6

int n=10000, count=0;
for (int i=1; i<=n; i*=2)
    for (int j=1; j<=n; j++)
        count++;

for循环，不管n是多少值(1、1百、1万、一亿)，只关注是两个for循环,但是其中一个按着2的幂来，时间复杂度为 O(nlog⁡2n)O(n\log_2^{n})

常用的时间复杂度级别

以下六种计算算法时间的多项式是最常用的。其关系为：O(1) < O(logn) < O(n) < O(nlogn) < O(n2)<O(n3)
指数时间的关系为：O(2n)<O(n!)<O(nn)

当n取得很大时，指数时间算法和多项式时间算法在所需时间上非常悬殊。

img

4.推荐

能读到文章最后，首先得谢谢您对本文的肯定，你的肯定是对博主最大的鼓励。

你觉本文有帮助，那就点个

您可能感兴趣的文章:

如对本文有疑问， 点击进行留言回复！！

相关文章:

验证码：
最近更新的文章
大家感兴趣的文章
移动技术网