数据结构与算法

用户头像
满山李子
关注
发布于: 2020 年 07 月 30 日

1. 时间与空间复杂度



1.1 时间复杂度

时间复杂度是用于衡量算法性能的重要指标

我们平常最直观的测试的算法性能:

  1. 在算法开始之前, 获取系统时间, 作为起始时间

  2. 执行算法

  3. 在算法执行完毕, 获取系统时间, 作为结束时间

  4. 结束时间 - 起始时间 = 算法耗时

这种测试算法性能的做法, 与系统有关;



比如: 相同的代码在 80年代的 IBM 5150: 16 KB的内存,16位、4.77MHz的Intel 8088处理器 和 2020年的Macbook Pro: 3.5GHz的 Intel i9 执行花费的时间肯定是不一样的



我们需要更加客观衡量算法指标, 就是时间复杂, 它是以算法执行语句的次数来衡量; 通常使用大O表示法, 来表示算法的时间复杂度; n是数据规模(可以理解数据条数)

T(n) = O(1) : 算法语句执行次数, 不随数据规模n而发生改变

T(n) = O(log(n)) 算法语句执行次数 是 数据规模n的对数

T(n) = O(n): 算法语句执行次数 是 数据规模n

T(n) = O(n^a) 算法语句执行次数 是 数据规模n的a次方;

以上时间复杂度, 就多项式时间复杂度

O(a^n) 算法语句执行次数 是a的n(数据规模)次方;

O(n!) 算法语句执行次数 是数据规模n的阶乘;

这两个时间复杂度是非多项式时间复杂度



1.2 空间复杂度

用于衡量一个算法临时占用空间大小的指标

O(1) 算法不占用额外存储空间

O(n) 算法临时存储数据规模n个数据

2. 数据结构

2.1 数组

数组 是 用于存储一组数据的容器

特点:

  1. 占用一块连续的内存空间

  2. 存储的元素数据类型必须相同

效率:

  1. 随机访问(读写), 根据下标访问数据时间复杂度O(1), 根据数组的首地址和下标直接算出元素的内存地址, 根据数据类型占用空间, 取出相应的数据即可

  2. 添加和删除数据: 时间复杂度O(n) ; 由于要移动数据, 最坏时间复杂度为O(n)

2.2 链表

链表 也是用于存储一组数据容器

特点:

  1. 可以使用零散的内存空间

  2. 链表中每一个数据元素都必须包含一个指向下一个数据的内存地址的指针

效率:

  1. 在链表中找一个数据, 只能从表头开始遍历链表, 查找的时间复杂度是O(n)

  2. 添加和删除数据: 时间复杂度O(n); 只需要更改有限个指针的指向即可

扩展:

可以把数组和链表结合起来, 快速实现增删



2.3 Hash表

既可以快速访问数据又可以快速增删数据; 缓存的常用结构

Hash表中key冲突

有些恶意攻击, 会利用hash表中key冲突, 让hash表产生一个长长的冲突链, 从而拖慢整个系统;



栈:

是一种后进先出的线性数据结构, 可以通过数组或链表实现;

线程运行的线程栈, 就是一个典型的栈结构.



队列:

是一种先进先出的线性数据结构

典型应用场景: 生产者, 消费者

举例: 用队列搜索好友关系中最近的有钱人



你先进入队列, 然后你出栈, 把你的朋友入栈, 然后再把你的朋友出栈, 看一下这个朋友是不是有钱人, 如果是就结束了, 这个朋友就是距离你最近的有钱人, 如果不是把朋友的朋友入栈, 递归求解, 就可以找到距离你最近的有钱人了。

2.4 树

2.4.1 二叉排序树

左子树上所有结点的值均小于或者等于它的根节点的值

右子树上所有节点的值均大于或者大于它的根节点的值

左, 右子树也分别为二叉排序树。

排序树目的: 是为了提高查询的速度, 一般情况为 log(n);





2.4.2 不平衡的排序树



不平衡排序二叉树, 查询时间复杂度退化到O(n)





2.4.2 平衡二叉排序树



从任何一个节点出发, 左右子树深度之差的绝对值不超过1, 左右子树仍然为平衡二叉树;



平衡二叉树主要目的, 也是了保证查找速度;



2.4.3 旋转二叉树 恢复平衡



插入时, 最多只需要两次旋转就会重新恢复平衡

删除时, 需要维护被删节点到根节点这条路径上所有节点的平衡性, 时间复杂度为O(logn)





2.4.4 红黑(排序)树

每一个节点只有两种颜色: 红色与黑色

根节点是黑色的

每一个叶子节点(NIL), 都是黑色的空节点

从根节点到叶子节点, 不会出现两个连续的红色节点。

从任何一个节点出发, 到叶子节点, 这条路径上都有相同数目的黑色;



这样规则也是为了, 让这颗排序数尽可能的平衡;从而有高效的查找速度。



增删节点的时候, 红黑数通过染色和旋转, 保持红黑树满足定义

2.4.5 红黑树 VS 平衡二叉树



红黑树最多只需要3次旋转就会重新达成红黑平衡, 时间复杂度O(1)

在大量增删的情况下, 红黑树的效率更高。

红黑树的平衡性不如平衡二叉树, 查找效率要差一些。



2.5 跳表

链表加多级索引的结构,就是跳表。

跳表查找数据的时间复杂度是: O(logn)

插入、删除操作的时间复杂度也是 O(logn)

Redis的有序集合就是通过跳表实现的





3. 常用算法

  1. 穷举算法

  2. 递归算法

  3. 贪心算法

  4. 动态规划



3.1 穷举算法

穷举算法是一种最简单的一种算法,其依赖于计算机的强大计算能力来穷尽每一种可能的情况,从而达到求解的目的。穷举算法效率不高,但适用于一些没有明显规律可循的场合。

比如: 选择排序和冒泡排序



3.2 递归算法



重复将问题分解为同类的子问题而解决问题的方法,其核心思想是分治策略。

比如: 快速排序算法

其实归并排序算法, 也是递归算法

递归算法的好处:

逻辑清晰, 代码实现简单



递归算法的注意事项有:

  1. 递归算法必须有出口, 否则就会栈内存溢出

  2. 递归算法调用层级不能太深, 否则也会内存溢出 或 速度奇慢

  3. 子问题在规模上比原问题小,或更接近终止条件;

  4. 子问题可通过再次递归调用求解或因满足终止条件而直接求解;

  5. 子问题的解应能组合为整个问题的解

3.3 贪心算法

贪心算法(又称贪婪算法)是指,在对问题求解时,总是做出在当前看来是最好的选择。也就是说,不从整体最优上加以考虑,算法得到的是在某种意义上的局部最优解



算法思路:将物品按照单位重量价值进行排序(从大到小),将尽可能多的单位重量价值最高的物品装入背包,若将这种物品全部装入背包后,背包还有多余容量,则选择单位重量价值次高的并尽可能多地装入背包。如果最后一件物品无法全部装入,则计算可以装入的比例,然后按比例装入。



背包问题: 小偷背了一个4磅背包去商城偷东西, 将那些商品放入背包才能收益最大化。

单位重量价值:

音响:3000/4 = 750

笔记本电脑: 2000/3 = 666.67

吉他: 1500

假设每种商品只有一件: 步骤如下

  1. 先单位重量价值最大吉他 1 把

  2. 然后放入单位重量价值次大的音响发现超重了,

  3. 接着放入笔记电脑, 正好可以放入;

放入背包的物品是: 吉他(1500) + 笔记本电脑(2000) = 3500



3.4 改进贪心算法 - 迪杰撕特拉算法(最快路径)



迪杰斯塔拉算法(最快路径)

迪杰斯特拉算法(Dijkstra) 是单源最短路算法,不能处理带负边权的情况。

迪杰斯特拉算法(Dijkstra)步骤:



  1. 找出 “最便宜”的节点, 即可在最短时间内到达的节点。

  2. 更新该节点的邻居的开销, 检查是否有前往他们的更短路径, 如果有, 就更新器开销。

  3. 重复这个过程, 直到对图中的每一个节点都这样做了。

  4. 计算最终路径



狄杰斯特拉算法核心是找到起点到每一个节点的最快路径

  1. 首先是起点到A, B点的直接耗时

  1. 通过B点, 到达A点, 耗时更短为5, 把6更改为5

  2. 从B点到达终点的耗时是5, 那么起点 -2-> B -5-> 终点, 总耗时为 7



A 到终点的耗时是1, 从起点到A点的最短耗时是5, 起点到终点的最短耗时更新为6

到此我们就找到了一条从起点到终点的最短路径, 起点-2->B-3->A-1->终点, 总耗时时间为6

3.5 动态规划算法解决背包问题, 通过找到合适的角度, 讲所有求解的目标值在某(几)个维度上展开, 讲一个大问题拆解为若干小问题, 小问题的最优解, 寻找大问题的最优解



每一个动态规划算法都从一个网格开始, 背包问题的网格如下





用户头像

满山李子

关注

还未添加个人签名 2018.09.18 加入

还未添加个人简介

评论

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