聊聊数据结构和算法

0 目录

1 为什么要懂数据结构和算法

2 什么是数据结构和算法

3 什么是时间复杂度分析

4 什么是空间复杂度分析

5 总结

一般我们学习算法都是这样的经历:

• 是不是从学校开始，你就觉得数据结构难学，然后一直没认真学？
• 工作中，一遇到数据结构这个坑，你又发自本能地迅速避让，因为你觉得自己不懂，所以也不想深究，反正看起来无关大局？
• 当你想换工作面试，或者研究某个开源项目源码，亦或者和团队讨论某个非框架层面的高可用难题的时候，你又发现，自己的基础跟不上别人的节奏？

其实笔者也是一样的，因为算法这个东西，平常真的实操的并不多，但是它又是面试必须问的知识点。因为它是程序员的基础知识。

基础知识就像是一座大楼的地基，它决定了我们的技术高度。而要想快速做出点事情，前提条件一定是基础能力过硬，“内功”要到位。

那技术人究竟都需要修炼哪些“内功”呢？我觉得，无外乎就是大学里的那些基础课程，操作系统、计算机网络、编译原理等等，当然还有数据结构和算法。

1 为什么要懂数据结构和算法

想要通关大厂面试，千万别让数据结构和算法拖了后腿。

很多大公司，比如 BAT、Google、Facebook，面试的时候都喜欢考算法、让人现场写代码。有些人虽然技术不错，但每次去面试都会“跪”在算法上，很是可惜。那你有没有想过，为什么这些大公司都喜欢考算法呢？

校招的时候，参加面试的学生通常没有实际项目经验，公司只能考察他们的基础知识是否牢固。社招就更不用说了，越是厉害的公司，越是注重考察数据结构与算法这类基础知识。相比短期能力，他们更看中你的长期潜力。

咱们程序员可能也要说了，我不懂数据结构与算法，照样找到了好工作啊。那我是不是就不用学数据结构和算法呢？当然不是，你别忘了，我们学任何知识都是为了“用”的，是为了解决实际工作问题的，学习数据结构和算法自然也不例外。

想作为业务开发工程师，一直写 CRUD的代码吗？NO！！！

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

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

目标是做基础架构，YES

好吧，我们可以自己写RPC框架，自己玩，但是咱们想让自己的RPC框架被别人来用，通常是非常难的。为什么呢？其实最主要的问题还是担心性能问题。

不同的公司、不同的人做出的 RPC 框架，架构设计思路都差不多，最后实现的功能也都差不多。但是有的人做出来的框架，Bug 很多、性能一般、扩展性也不好，只能在自己公司仅有的几个项目里面用一下。

高手之间的竞争其实就在细节。这些细节包括：你用的算法是不是够优化，数据存取的效率是不是够高，内存是不是够节省等等。这些累积起来，决定了一个框架是不是优秀。所以，如果咱们还不懂数据结构和算法。

目标是高性能的代码，YES

业界很多公众推文很都说35岁之后还在写代码的人是很low的，应该去做管理（管人和管事），但是事实真的是这样吗？

后面的低代码平台普及之后，也还是需要一大批写出高性能的代码的资深工程师的。

2 什么是数据结构和算法

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

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

比如10个最经典的数据结构：数组、链表、栈、队列、散列表、二叉树、堆、跳表、图、Trie 树。

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

3 什么是时间复杂度分析

算法的执行效率，粗略地讲，就是算法代码执行的时间。但是，如何在不运行代码的情况下，用“肉眼”得到一段代码的执行时间呢？

看到很多大牛都是用大O时间复杂度表示法，大O时间复杂度实际上并不具体表示代码真正的执行时间，而是表示代码执行时间随数据规模增长的变化趋势，所以，也叫作渐进时间复杂度，简称时间复杂度。

一般时间复杂度分析主要包括：O(1)、O(logn)、O(nlogn)、O(m+n)、O(m*n)，真的非常不想懂，光看这些符号就很烦，确实很烦，总感觉我们又回到“大学高等数学记忆数学公式的时代”。

一般情况下，只要算法中不存在循环语句、递归语句，即使有成千上万行的代码，其时间复杂度也是Ο(1)，反正我是这么理解的。

一般情况下把所有对数阶的时间复杂度都记为 O(logn)，对数之间是可以互相转换的，log3n 就等于 log32 * log2n，所以 O(log3n) = O(C * log2n)，其中 C=log32 是一个常量。基于我们前面的一个理论：在采用大 O 标记复杂度的时候，可以忽略系数，即 O(Cf(n)) = O(f(n))。所以，O(log2n) 就等于 O(log3n)。因此，在对数阶时间复杂度的表示方法里，我们忽略对数的“底”，统一表示为 O(logn)。

如果一段代码的时间复杂度是 O(logn)，我们循环执行 n 遍，时间复杂度就是 O(nlogn) 了。而且，O(nlogn) 也是一种非常常见的算法时间复杂度。比如，归并排序、快速排序的时间复杂度都是 O(nlogn)。

如果代码的时间复杂度是由两个数据来决定的，就衍生出了O(m+n)、O(m*n)。

4 什么是空间复杂度分析

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

常见的空间复杂度就是 O(1)、O(n)、O(n2 )，像 O(logn)、O(nlogn) 这样的对数阶复杂度平时都用不到。而且，空间复杂度分析比时间复杂度分析要简单很多。

5 总结

要想跨过数据结构这道门槛，必须要多想、多练、多实践以及多总结。

下面笔者会和大家一起学习数据结构和算法，谁说35岁的程序员就没有追求了呢？

知识输出是笔者的初衷，借助知识输出，能够认识更多的牛人,能够和牛人沟通，也是自己技术提升的一个机会。

下一期：开启35岁程序员数据结构和算法认知系列