写点什么

W8- 总结数据结构与算法

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

计算机程序将现实的任务抽象成为数据+算法。数据是抽象的描述,算法是某一些问题的解决方案。

常见的数据结构包括三大类:线性结构,图结构,混合结构。

线性结构常见的有:数组,链表;特殊的数组和队列有队列(只对头尾进行访问的线性结构)与栈(只对头元素进行访问的线性结构)。

图的数据结构可以表示成端点与边的数组。树是数据处理中最常用的图数据组织形式。最简单的树结构是二叉树,为了达到搜索的目的,构建二叉搜索树。由于在对树元素增删改查的过程中,会导致二叉搜索树不平衡,于是红黑树一定的规则,保证二叉搜索树保持平衡,是最工业级的,常用的二叉搜索树。

比二叉搜索树简单是堆,大顶堆,小顶堆是简化的二叉搜索树;因为大小顶堆只保证树的根元素最大最小。

跳表使得数组与链表在修改删除元素的过程保持稳定的复杂度,但其结构变动比线性结构复杂不少(但相对于红黑树简单不少,所以redis的sorted set使用跳表)。



程序算法主要完成排序和搜索的目的。用时间复杂度与空间复杂度来表示算法的效率。

选择不同数据结构主要为满足存储与搜索的要求。通常来讲,有序的数据更利于数据搜索。排序算法为了将无序的数据构建成为有序的数据。快速排序,冒泡排序等都是简单基于线性数据结构的排序算法。也可以通过构建搜索数的过程,完成数据从无序到有序的转换。所以沟通二叉搜索树,构建调表,沟通大小顶堆,构建B+树的过程可以理解成数据的排序过程。



搜索算法是为了在已经沟通好的结构里面搜索符合条件的数据。所以搜索通常与数据结构本身是不能分开的。基于Hash表的搜索理论上是O(1)的复杂度(如果有hash冲突,导致hash表退化,会使得退化到O(n)),由于结构的数据搜索,如二叉搜索树,调表,搜索时间复杂度为O(log(N))。复杂图的搜索算法时间复杂度一般来讲远高于O(logN)。



时间复杂度简单理解,它计算过程循环的次数。空间复杂度表示计算过程额外存储空间的消耗(内存、磁盘)。不能简单理解时间复杂度越低,消耗时间越少;但一般来讲,对于时间复杂度越少,程序越有优势。



作为程序员,算法的理解是不可缺少的,作为架构师,算法也是不可缺少的。理解算法,肯定可以让系统开发过程更快,更好。



用户头像

麻辣

关注

还未添加个人签名 2018.10.13 加入

还未添加个人简介

评论

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