数据结构与算法概述

用户头像
破晓_dawn
关注
发布于: 2020 年 07 月 29 日

数据结构

数组与链表

数组存储相同的数据类型,在内存中占用一块连续的内存空间。

链表可以使用零散的空间存储数据,各个元素通过指针连接,没有元素包括指向下一个元素的内存地址。

从存储的方式可以看出。数据可以迅速查找,给定下标,查找的时间复杂度O(1)。但是,由于需要用连续的存储空间,数组的插入时间复杂度为O(N),需要将插入元素的后面的元素整体后移,如果空间不够,还需要开辟新的内存空间存储。

链表查找需要逐个遍历,因此查找的时间复杂度为O(N),但是插入,删除元素,不用移动后面的元素,时间复杂度O(N)。

因此,可以根据数据操作的特点,选择合适的数据结构。

Hash表

Hash表可以看作数组和链表结合,可以实现快速增删。访问数据和增删数据,都是O(1)。

Hash表由一个固定大小的数组加一个链表组成。

查找元素时,先计算出元素对应hash值,然后根据hash值从数组中快速获取数据。插入数据,也通过hash值,找到应该插入的位置,如果两个元素的hash值相同,通过链接,解决碰撞问题。

数组和链表都是线性表。栈就是在线性表,添加上“后进先出”的限制的数据结构。

栈的一个典型应用是函数调用栈。在操作系统中,函数调用产生和局部变量都存储在栈中。

队列

和栈相对的是队列,队列也是添加限制的线性表,和栈不同,队列需要“先进先出”

典型的应用场景是生产者消费者,生产者将任务放入队列,多个消费者从队列中去任务处理。

树是由n(n>0)个有限节点组成一个具有层次关系的集合。

典型的一种树是二叉排序树。其左子树上的所有节点的值都小于根节点,右子树上所有的节点都大于根节点。且左右子树也为二叉排序树。

平衡二叉(排序)树如果从任何一个节点出发,左右子树的深度之差的绝对值不超过1。平衡二叉树的左右子树也为平衡二叉树。

红黑(排序)树每个节点有两种颜色——红色和黑色。根节点都是黑色。每个叶子节点都是黑色的空节点。从根节点到叶子节点不会出现连续的红色节点。从任何一个节点出发到叶子节点,这条路径上都有相同数目的黑色节点。

增删节点时,红黑树通过染色和旋转满足定义。

红黑数 vs. 平衡二叉树

红黑树增删的时间复杂度O(1),比平衡二叉树性能好。在大量增删的情况下,红黑树的效率高。但是,由于红黑树平衡性不如二叉树,因此,查找效率要差一些。

跳表

所有的数据构建为一个有序链表,时间复杂度为O(N)。

跳表:在原来的链表的基础上,在构建一个更系数的链表。

缺点:空间复杂度高,多出1倍的空间。

算法

常用算法有:穷举算法、递归算法、贪心算法、动态规划

  1. 穷举算法

暴力遍历,时间复杂度一般为 2^n,数字很大时,无法计算。

  1. 递归算法

典型的如快速排序算法。

特点:递归函数要写写退出条件,如果没有退出条件会导致栈溢出错误。

死循环,不会导致栈溢出。

  1. 贪心算法

不从总体上考虑最优,总是作出当前看起来最好的选择。算法得到的是某种意义上的局部最优。

例如,背包问题,背包容量为4磅,需要装最优价值的东西。用贪心算法的思路,如果选用最大价值的原则,先放入最值钱的,即音箱。则最终获得3000。而实际最优是,放入笔记本和吉他 3500。

可见,贪心算法,通常不能得到令人满意的结果。

  1. 动态规划算法

动态规划将问题分解为相似的子问题,试图解决每个子问题一次,并存储解,下次用到相同子问题直接查询。

动态规划在查找有很多重叠子问题的情况的最优解时有效。动态规划只能应用于有最优子结构的问题。

比如上面的(0-1)背包问题。

建立网格,网格中填写的值为c[i][j],i为可以选择的商品,j为背包容量。

v[i]为i的价值,w[i]为i的重量。

决定是否选择商品i的方案,比较选与不选的获得的价值

即,c[i][j] = max(c[i-1][j] ,v[i]+c[i-1][j-w[i]])



  • 第一行,由于只有吉他可选,且吉他重量为1,因此,c[1][j]都为1500。

  • 第二行,可选的有吉他和音响,由于音响4磅,因此,当容量小于4时,c[2][j] = 1500(只能放下吉他),当容量为4时,c[2][4]=3000。

  • 第三行,笔记本为3磅,当j<=2时,还是只能选吉他,1500。

  • 当j为3时,有两种选择,

1)不放笔记本,值为c[2][3]=1500

2)放笔记本,值为v[3]+c[2][3-w[3]]=2000

因此,最大价值的c[3][3] = 2000

  • 当j为4时,也是2种选择,

1)不放笔记本,值为c[2][4]=3000

2)放笔记本,值为v[3]+c[2][4-w[3]]=2000 + 1500 = 3500

因此,c[3][4] = 3500。

由此,得到最优解,背包为4时,放吉他和笔记本,价值3500。



发布于: 2020 年 07 月 29 日 阅读数: 36
用户头像

破晓_dawn

关注

慢慢,稳稳 2017.12.06 加入

业余选手,但是有一颗向往专业的心

评论

发布
暂无评论
数据结构与算法概述