C# · 12月 20, 2021

02 | 如何抓住重点,系统高效地学习数据结构与算法?

从广义上讲,数据结构就是指一组数据的存储结构。算法就是操作数据的一组方法。

数据结构和算法是相辅相成的。数据结构是为算法服务的,算法要作用在特定的数据结构之上。因此,我们无法孤立数据结构来讲算法,也无法孤立算法来讲数据结构。

因为数据具有随机访问的特点,常用的二分查找算法需要用数据来存储数据。但如果我们选择链表这种数据结构,二分查找算法就无法工作了,因为链表不支持随机访问。

数据结构是静态的,它只是组织数据的一种方式。如果不在它的基础上操作、构建算法、孤立的数据结构就是没用的。

数据结构:

线性表:数组,链表【单链表,双向链表,循环链表,双向循环链表,静态链表】,栈【顺序栈,链式栈】,队列【普通队列,双端队列,阻塞队列,并发队列,阻塞并发队列】;

散列表:散列函数,冲突解决【链表法,开放寻址,其他】,动态扩容,位图;

树:二叉树【平衡二叉树,二叉查找树,平衡二叉查找树【AVL树,红黑树】,完全二叉树,满二叉树】,多路查找树【B树,B+树,2-3树,2-3-4树】,堆【小顶堆,大顶堆,优先级队列,斐波那契堆,二项堆】,其他【树状数组,线段树】。

图:图的存储【邻接矩阵,邻接表】,拓扑排序,最短路径,关键路径,最小生成树,二分图,最大流。

算法:

复杂度分析:空间复杂度,时间复杂度【最好,最坏,平均,均摊】;

基本算法思想:贪心算法,分治算法,动态规划,回溯算法,枚举算法;

排序:O(n^2)【冒泡排序,插入排序,选择排序,希尔排序】,O(nlogn)【归并排序,快速排序,堆排序】,O(n)【技术排序,基数排序,梯排序】;

搜索:深度优先搜索,广度优先搜索,A*启发式搜索;

查找:线性表查找,树结构查找,散列表查找;

字符串匹配:朴素,KMP,Robin-Karp,Boyer-Moore,AC自动机,Trie,后缀数组

其他:数论,计算几何,概率分析,并查集,拓扑网络,矩阵运算,线性规划。

数据结构和算法解决的是如何更省、更快地存储和处理数据的问题,因此,我们就需要一个考量效率和资源消耗的方法,这就是复杂度分析方法。

主要:

10个数据结构:数组,链表,栈,队列,散列表,二叉树,堆,跳表,图,Trie树。

10个算法:递归,排序,二分查找,搜索,哈希算法,贪心算法,分治算法,回溯算法,动态规划,字符串匹配算法。

/*** 当我们要谈一个事物/概念的时候,需要问自己三个终极问题–是什么?为什么?怎么样?

什么是数据结构和算法

数据结构,就是一组数据的存储结构。

算法,就是操作数据的一组方法。

数据结构是为算法服务的,算法要作用在特定的数据结构之上。

为什么需要数据结构和算法

来谈谈应用层面的原因。在计算机科学和互联网迅猛发展下,需要计算的数据量越来越庞大。但是计算机的计算能力是有限的,这么大量的数据计算,需要越来越多的计算机,需要越来越长的计算时间,注重效率的我们需要尽可能的提高计算效率。其中重要的一项,就是使用合适的数据结构和算法。选用合适的数据结构和算法,特别是在处理体量非常庞大的数据的时候,可以极大提高计算效率。那么,第三个问题来了,我们怎么选用合适的数据结构和算法?有什么衡量标准吗?

怎么样衡量数据结构和算法

需要引入一个衡量的标准(metric)—时间复杂度和空间复杂度。

学习数据结构和算法的基石,就是要学会`复杂度分析`。知道怎么去分析复杂度,才能作出正确的判断,在特定的场景下选用合适的正确的算法。而不是盲目的死记烂背,机械操作。****/