什么是数据结构？什么是算法？

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

从狭义上讲，是指某些著名的数据结构和算法，比如队列、栈、堆、二分查找、动态规划等。这些都是前人智慧的结晶，我们可以直接拿来用。我们要讲的这些经典数据结构和算法，都是前人从很多实际操作场景中抽象出来的，经过非常多的求证和检验，可以高效地帮助我们解决很多实际的开发问题。

数据结构与算法之间的关系？

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

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

数据结构结构与算法包含哪些内容？

一级分类 二级分类 子类 备注
线性表 数组
链表 单链表、双向链表、循环链表、双向循环列表、静态链表、跳表
栈 顺序栈、链式栈
队列 普通队列、双端队列、阻塞队列、并发队列、阻塞并发队列
散列表 散列函数
动态扩容
位图
冲突解决 链表法、开放寻址、其他
树 二叉树 平衡二叉树、二叉查找树、平衡二叉查找树（AVL、红黑树）、完全二叉树、满二叉树
堆 小顶堆、大顶堆、优先级队列、斐波那契堆、二顶堆
多路查找树 B树、B+树、2-3树、2-3-4树
其他 树状数组、线段树
图 图的存储 邻接矩阵、邻接表
其他 拓扑排序、最短路径、关键路径、最小生成树、二分图、最大流
复杂度分析 空间
时间 最好、最坏、平均、均摊
基本算法 贪心算法、分治算法、动态规划、回溯算法、枚举算法
排序 平方级O(n^2) 冒泡排序、插入排序、选择排序、希尔排序
线性对数级O(nlogn) 归并排序、快速排序、堆排序
线性级O(n) 计数排序、基数排序、桶排序
搜索 深度优先搜索
广度优先搜索
A*启发式搜索
查找 线性表查找
树结构查找
散列查找
字符串匹配 朴素、KMP、Robin-Karp、Boyer-Moore、AC自动机、Trie、后缀数组
其他 数论
计算几何
概率分析
并查集
拓扑网路
矩阵运算
线性规划

补充：大数据领域的算法和数据结构，很多都是采用多种数据结构和算法设计组合而成，例如：布隆过滤器、跳表、LSM树、Merkle哈希树、Snappy与LZSS算法、Cuckoo哈希。

重点掌握哪些？

10个数据结构：数组、链表、栈、队列、散列表、二叉树、堆、跳表、图、Trie树（前缀树或字典树）

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

算法时间复杂度：

  • 多项式阶：常数级O(1)、对数级O(logn)、线性级O(n)、线性对数级O(nlogn)、平方级O(n^2)、立方级O(n^3)
  • 非多项式阶：指数级O(2^n)、阶乘级O(n!)。性能极差

算法空间复杂度：主要有O(1)、O(n)、O(n^2)，对数级或线性对数级不常见

要学习它的“来历”、“自身的特点”、“适合解决的问题”以及“实际的应用场景“。工作中遇到实际需求，能够想到它们并做出选择。

学习这些有哪些技巧？

边学边练，适度刷题

多问、多思考、多互动

设立切实可行的目标，针对知识点的学习，输出学习笔记或心得

知识需要沉淀、反复迭代

推荐资源

刷题网站：leetcode

入门级书：《大话数据结构》、《算法图解》

进阶级书：《算法导论》、《算法第四版》