数据结构和算法

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



时间、空间复杂度



关注最大阶,忽略系数、低阶、常数 ; 2n2+2n +10000 => O(n2)



O(1) : 执行时间不随 n 的增大而增长, 没有循环、递归,即使有成千上万行,都是O(1)



O(logn):



O(nlogn): 把O(logn)的代码执行n遍



均摊时间复杂度:一个算法,操作最耗时的一种情况,是否可以平摊到其他的不耗时的操作上,如果可以,一般均摊时间复杂度为最好情况的复杂度。




数组



定义:使用连续的存储空间存放相同数据类型数据的线性表

特性:随机访问;下标访问时间复杂度O(1);低效的中间、开头插入和删除

适用场景:正常开发,用动态数组替代, 如果是特别底层的开发,使用数组可能会更合适




链表

  • 双向链表:

在已知链表节点情况下,插入、删除比单向链表更快,O(1)复杂度;如果是有序的链表,在查找元素时,可以每次记录上次查找的结果,通过与上次的值比较,可以知道向前还是向后查找,比单向链表快。

空间换时间思想



  • 和数组的访问效率差异: 数组读取可以借助 CPU 的缓存机制,预读数组中的数据(cpu从内存读取数据,不只是读取要访问的那个地址,而是把一个连续的数据块读取到cpu缓存,以供下次使用)。由于数组连续存储,而链表的内存分布在各处,所以访问效率更高。




  • 特点:先进先出

  • 应用:

  • 函数调用栈

  • 表达式求值,一个操作数栈,一个操作符栈




队列

  • 特点:先进后

  • 顺序队列:用数组实现。链式队列:用链表实现

  • 循环队列判断是否已满条件:(tail + 1)% n == head

实现出循环队列--方式1:比较head和tail的值, 方式2:用size记录队列大小

  • 应用场景:对大部分资源有限的场景,当没有空闲资源时,基本都可以通过“队列”这个方式来实现请求排队,削峰填谷。




递归

可用递归来解决的问题要满足3个条件:

  1. 问题可以拆解成几个更小的子问题

  2. 分解后的子问题,除了数据规模不一样,求解思路完全一样

  3. 存在递归终止条件



写出递归代码方法:写出递推公式,找到终止条件。

递归是把问题传递出去,回来的过程为“归”。

把他抽象成一个公式,不用想每一层的调用关系,不用试图分解每一个步骤,只需假设分解出的子问题都解决了,分析主问题和其他子问题的关系



  • 注意事项

使用递归时,警惕堆栈溢出,系统栈一般不大,容易造成堆栈溢出。

要小心重复计算问题:随着调用层次深入,可能会分解出相同的子问题,而这些子问题会重复计算。虽然可以用一个map来缓存已经计算过的问题,但函数调用带来的开销依然很高。递归每调用一次,都要保存一份现场数据到内存栈,空间复杂度为O(n)




跳表



  • 特点:一个已排序的链表 + 多个用于作索引的链表;

可以动态高效插入、删除,O(logn);

查找速度类似于二分查找;

有着树一样的搜索性能;

  • 应用:redis上的有序集合使用跳表实现:

——按照区间查找数据比红黑树更快,O(logn)

——代码更容易实现,不易出错

——可以通过改变索引策略,来平衡执行效率和空间的开销,索引间隔为2最快






平衡二叉树

  • 定义:任意一个节点,它的左右子树高度差不能超过1。

AVL树严格符合这个标准,它高度平衡,但是删除、插入相对耗时,不适用频繁变动的树

红黑树做到了近似的平衡,各种操作性能非常稳定,工业级的平衡二叉查找树

  • 目的:解决树在频繁的插入、删除等修改后,可能导致查找时间复杂度退化的问题(慢慢的长得像个链表,两边不再平衡)



  • 和其它功能类似的结构体对比:

散列:

——优势:操作耗时,O(1)

——劣势:无序动态扩容和缩容性能不稳定;额外需要O(n)空间;散列冲突;散列函数设计要求高

——应用场景:数据变化不大,内存不敏感

跳表:

——优势:数据有序

——劣势:额外需要O(n)空间,操作耗时O(n)

——应用场景:内存不明感,需要数据有序的地方(顺序遍历、区间查找)

红黑树:

——优势:性能非常稳定,不额外占用空间,比散列应用了更多地方。中序遍历就是顺序遍历

——劣势:难理解,操作O(n),区间查找复杂度O(n)

——应用场景:内存敏感,对性能稳定性要高特别高




贪心算法

  • 使用场景:在给定的限制值下获得一个最大的期望值,每次操作都要对期望值贡献最大。

  • 缺点:并不是每次都可以得出最优解




动态规划



  • 原理:把问题分解为多个阶段,每个阶段对应一个决策。我们记录每一个阶段可达的状态集合(用于减少重复计算),然后通过当前阶段的状态集合,来推导下一个阶段的状态集合,动态地往前推进。

  • 组成: 阶段 + 状态(取/不取/最值)

  • 适用场景:求最优解

  • 优点:相对于用回溯法,可以非常显著的降低时间复杂度



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

GalaxyCreater

关注

还未添加个人签名 2019.04.21 加入

还未添加个人简介

评论

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