【灵魂 |数据结构与算法】 数据结构必备经法（开山篇），一起修炼算法经法！

🤵‍♂️ 个人主页: @AI_magician 📡主页地址： 作者简介：CSDN内容合伙人，全栈领域优质创作者。 👨‍💻景愿：旨在于能和更多的热爱计算机的伙伴一起成长！！🐱‍🏍 🙋‍♂️声明：本人目前大学就读于大二，研究兴趣方向人工智能&硬件（虽然硬件还没开始玩，但一直很感兴趣！希望大佬带带）

该文章收录专栏 [✨— 《深入解析机器学习：从原理到应用的全面指南》 —✨

数据结构必备经法

目标

学习数据结构与算法的理由

1. 大厂面试

比如 BAT、Google、Facebook，面试的时候都喜欢考算法、让人现场写代码。公司只能考察他们的基础知识是否牢固。社招就更不用说了，越是厉害的公司，越是注重考察数据结构与算法这类基础知识。相比短期能力，他们更看中你的长期潜力。

1. 业务开发性能优化

对于大部分业务开发来说，我们平时可能更多的是利用已经封装好的现成的接口、类库来堆砌、翻译业务逻辑，很少需要自己实现数据结构和算法。但是，不需要自己实现，并不代表什么都不需要了解。

如果不知道这些类库背后的原理，不懂得时间、空间复杂度分析，如何能用好、用对它们？存储某个业务数据的时候，你如何知道应该用 ArrayList，还是 Linked List 呢？调用了某个函数之后，你又该如何评估代码的性能和资源的消耗呢？

作为业务开发，我们会用到各种框架、中间件和底层系统，比如 Spring、RPC 框架、消息中间件、Redis 等等。在这些基础框架中，一般都揉和了很多基础数据结构和算法的设计思想。比如，我们常用的 Key-Value 数据库 Redis 中，里面的有序集合是用什么数据结构来实现的呢？为什么要用跳表来实现呢？为什么不用二叉树呢？

如果你能弄明白这些底层原理，你就能更好地使用它们。即便出现问题，也很容易就能定位。因此，掌握数据结构和算法，不管对于阅读框架源码，还是理解其背后的设计思想，都是非常有用的。

而在面对新的问题或者业务场景中，也能够设计更好的方案来解决问题

在平时的工作中，数据结构和算法的应用到处可见。我来举一个你非常熟悉的例子：如何实时地统计业务接口的 99% 响应时间？ 你可能最先想到，每次查询时，从小到大排序所有的响应时间，如果总共有 1200 个数据，那第 1188 个数据就是 99% 的响应时间。很显然，每次用这个方法查询的话都要排序，效率是非常低的。但是，如果你知道“堆”这个数据结构，用两个堆可以非常高效地解决这个问题。

1. 提升代码水平（个人能力！）

达到开源水平的代码能力，高手之间的竞争其实就在细节。这些细节包括：你用的算法是不是够优化，数据存取的效率是不是够高，内存是不是够节省等等。这些累积起来，决定了一个框架是不是优秀。

何为编程能力强？代码的可读性好、健壮、还是扩展性好等等，其中性能好坏起码是其中一个非常重要的评判标准。而对代码的时间复杂度、空间复杂度分析才能写出高性能的代码

如果你在一家成熟的公司，或者 BAT 这样的大公司，面对的是千万级甚至亿级的用户，开发的是 TB、PB 级别数据的处理系统。性能几乎是开发过程中时刻都要考虑的问题。一个简单的 ArrayList、Linked List 的选择问题，就可能会产生成千上万倍的性能差别。这个时候，数据结构和算法的意义就完全凸显出来了。之前你可能需要费很大劲儿来优化的代码，需要花很多心思来设计的架构，用了数据结构和算法之后，很容易就可以解决了。

掌握了数据结构与算法，你看待问题的深度，解决问题的角度就会完全不一样。因为这样的你，就像是站在巨人的肩膀上，拿着生存利器行走世界。数据结构与算法，会为你的编程之路，甚至人生之路打开一扇通往新世界的大门。

核心数据结构与算法

核心学习数据结构与算法

10 个数据结构：数组、链表、栈、队列（线性表）、散列表、二叉树、堆、跳表、图、Trie树

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

对于每一种数据结构或算法学习它的**“来历”“自身的特点”“适合解决的问题”以及“实际的应用场景”**,千万不要被动地记忆，要多辩证地思考，多问为什么。如果你一直这么坚持做，你会发现，等你学完之后，写代码的时候就会不由自主地考虑到很多性能方面的事情，时间复杂度、空间复杂度非常高的垃圾代码出现的次数就会越来越少。你的编程内功就真正得到了修炼。

时间复杂度&空间复杂度分析

事后统计分析： 把代码跑一遍，通过统计、监控，就能得到算法执行的时间和占用的内存大小。（局限性大）

大O复杂度表示法：体现整体算法随着规模增大的趋势表现，也叫作渐进时间复杂度（asymptotic time complexity），简称时间复杂度。

1. 只关注循环最多的一段 代码
2. 加法原则：取量级最大的复杂度
3. 乘法原则：取量级结果最大的

分为两类，多项式量级和非多项式量级。其中，非多项式量级只有两个：O(2^n) 和 O(n!)。 当数据规模 n 越来越大时，非多项式量级算法的执行时间会急剧增加，求解问题的执行时间会无限增长。所以，非多项式时间复杂度的算法其实是非常低效的算法。

空间复杂度分析：时间复杂度的全称是渐进时间复杂度，表示算法的执行时间与数据规模之间的增长关系。类比一下，空间复杂度全称就是渐进空间复杂度（asymptotic spacecomplexity），表示算法的存储空间与数据规模之间的增长关系。

查看循环最多的变量生成的一段代码

常见的复杂度并不多，从低阶到高阶有：O(1)、O(logn)、O(n)、O(nlogn)、O(n )。几乎都是这些

其中还有四种复杂度分析方法 最好情况时间复杂度（best case timecomplexity）、最坏情况时间复杂度（worst case time complexity）、平均情况时间复杂度（average case time complexity）、均摊时间复杂度（amortized time complexity）。 平均则是引入概率论，均摊则是平摊思想

1. 数组和字符串：
   • 数组操作（插入、删除、查找等）

   前缀和算法 ：

   1. 寻找数组的中心索引 （左边之和等于右边）（前缀和）

   排序：

   1. 搜索插入位置（查找相同值或插值） （二分查找）
   2. 合并区间 （排序 + 二维数组）

   十大排序

   • 字符串操作（反转、查找、匹配等）
   • 双指针技巧（快慢指针、滑动窗口等）
2. 链表：
   • 单链表和双链表的基本操作
   • 快慢指针技巧在链表中的应用
   • 链表反转、环检测等问题
3. 栈和队列：
   • 栈和队列的基本操作（入栈、出栈、入队、出队等）
   • 用栈解决的问题（括号匹配、逆波兰表达式等）
   • 用队列解决的问题（广度优先搜索等）
4. 哈希表：
   • 哈希表的原理和实现
   • 哈希函数的设计和冲突解决方法
   • 哈希表在查找和去重等问题中的应用
5. 树与图：
   • 二叉树的遍历（前序、中序、后序）
   • 二叉搜索树的性质和操作
   • 堆和优先队列的基本概念和应用
   • 图的表示方法和遍历算法（深度优先搜索、广度优先搜索）
6. 排序和搜索：
   • 常见排序算法（冒泡排序、插入排序、快速排序等）
   • 高级排序算法（归并排序、堆排序等）
   • 二分查找和其他搜索算法的实现和应用
7. 动态规划：
   • 动态规划的基本概念和解题思路
   • 斐波那契数列和背包问题等经典动态规划案例
   • 动态规划的优化技巧和常见变种
8. 贪心算法：
   • 贪心算法的基本思想和适用条件
   • 贪心算法的经典案例（任务调度、区间覆盖等）
   • 贪心算法与动态规划的比较和区别
9. 图算法：
   • 最短路径算法（Dijkstra算法、Bellman-Ford算法等）
   • 最小生成树算法（Prim算法、Kruskal算法等）
   • 拓扑排序和关键路径等问题
10. 高级数据结构：
    • 并查集的原理和应用
    • 字典树和前缀树的基本操作和应用
    • 线段树和树状数组的实现和应用