一、代码效率优化方法论

1.复杂度：如何衡量程序运行的效率？

要去开发某个复杂系统，如何才能围绕系统的复杂性去选择最合适的解决方案呢？一方面是对所用算法的选型，另一方面是对所用数据结构的选型

一直在追语言，学框架，而忽视了数据结构与算法的学习和落地训练，基础知识储备不足，很难顺利做出最优的技术选择，从而导致开发的系统性能、稳定性都存在很多缺陷。

基本功扎实的人潜力会非常大，取得业绩结果只不过是时间问题。

刷题只是形式，更重要的是掌握算法思维和原理，并用以解决实际的编码问题。

总结来说，这门课会从方法论、基础知识、真题演练、面试技巧这四个方面

3 用算法思考问题的逻辑和程序设计的重要思想。它们不会改变数据的组织方式，但可以通过巧妙的计算方式降低代码复杂度。常见的方法，如递归、二分法、排序算法、动态规划等，会在这一部分介绍。

4 面试题并非单纯考核人才的工具，更是实际业务问题高度提炼后的缩影，它能反映一个开发者的知识储备和问题解决能力。

成为核心骨干的一个先决条件，就是准确的技术选型和扎实的代码基础，而这最基本的条件是要掌握算法思维和数据结构原理，这是代码开发和优化的方法论，是用以解决实际编码问题的精髓所在，也是这门课核心要传达的内容。

复杂度计算：

复杂度通常包括时间复杂度和空间复杂度。时间复杂度与代码的结构设计高度相关；空间复杂度与代码中数据结构的选择高度相关。

1. 它与具体的常系数无关，O(n) 和 O(2n) 表示的是同样的复杂度。
2. 复杂度相加的时候，选择高者作为结果，也就是说 O(n²)+O(n) 和 O(n²) 表示的是同样的复杂度。
3. O(1) 也是表示一个特殊复杂度，即任务与算例个数 n 无关。

一些经验性的结论：

1. 一个顺序结构的代码，时间复杂度是 O(1)。
2. 二分查找，或者更通用地说是采用分而治之的二分策略，时间复杂度都是 O(logn)。这个我们会在后续课程讲到。
3. 一个简单的 for 循环，时间复杂度是 O(n)。
4. 两个顺序执行的 for 循环，时间复杂度是 O(n)+O(n)=O(2n)，其实也是 O(n)。
5. 两个嵌套的 for 循环，时间复杂度是 O(n²)。
6. 有了这些基本的结论，再去分析代码的时间复杂度将会轻而易举。

降低时间复杂度的必要性

但在当今的大数据环境下，时间复杂度的优化将会带来巨大的系统收益。而这是优秀工程师必须具备的工程开发基本意识。

2.数据结构：将“昂贵”的时间复杂度转换成“廉价”的空间复杂度

通常面试官会追问：“这段代码的时间复杂度或者空间复杂度，是否还有降低的可能性？”

时间昂贵、空间廉价

暴力解法（最原始）

为了降低复杂度，一个直观的思路是：梳理程序，看其流程中是否有无效的计算或者无效的存储。

常用的降低时间复杂度的方法有递归、二分法、排序算法、动态规划等，

而降低空间复杂度的方法，就要围绕数据结构做文章了。

更进一步讲，降低空间复杂度的核心思路就是，能用低复杂度的数据结构能解决问题，就千万不要用高复杂度的数据结构。

数据结构：数据组织方式

以上就是程序优化的最核心的思路，也是这个专栏的整体框架。我们简单梳理如下：

1. 第一步，暴力解法。在没有任何时间、空间约束下，完成代码任务的开发。
2. 第二步，无效操作处理。将代码中的无效计算、无效存储剔除，降低时间或空间复杂度。（递归、二分法、排序算法、动态规划等）
3. 第三步，时空转换。设计合理数据结构，完成时间复杂度向空间复杂度的转移。

二、数据结构基础

03 | 增删查：掌握数据处理的基本操作,以不变应万变

数据操作动作：

1. 找到要处理的数据。这就是按照某些条件进行查找。
2. 把结果存到一个新的内存空间中。这就是在现有数据上进行新增。
3. 把结果存到一个已使用的内存空间中。这需要先删除内存空间中的已有数据，再新增新的数据。

常用的分析方法可以参考下面的 3 个步骤：

1. 首先，这段代码对数据进行了哪些操作？
2. 其次，这些操作中，哪个操作最影响效率，对时间复杂度的损耗最大？
3. 最后，哪种数据结构最能帮助你提高数据操作的使用效率？

总结：

1. 数据处理的基本操作只有 3 个，分别是增、删、查。
2. 增和删又可以细分为在数据结构中间的增和删，以及在数据结构最后的增和删。区别就在于原数据的位置是否发生改变。
3. 查找又可以细分为按照位置条件的查找和按照数据数值特征的查找。

04 | 如何完成线性表结构下的增删查？

什么是线性表？

线性表是 n 个数据元素的有限序列，最常用的是链式表达，通常也叫作线性链表或者链表。在链表中存储的数据元素也叫作结点，一个结点存储的就是一条数据记录。每个结点的结构包括两个部分：

1. 第一是具体的数据值；
2. 第二是指向下一个结点的指针。
3. 通常会有个头指针用来指向第一个结点
4. 链表的最后一个结点，指针是空指针。

有时候为了弥补单向链表的不足，我们可以对结点的结构进行改造：

1. 循环链表：对于一个单向链表，让最后一个元素的指针指向第一个元素，就得到了循环链表；
2. 双向链表：或者把结点的结构进行改造，除了有指向下一个结点的指针以外，再增加一个指向上一个结点的指针。这样就得到了双向链表。

链表数据操作：增、删、查

新增：把待插入结点的指针指向原指针的目标，把原来的指针指向待插入的结点。 s.next = p.next; p.next = s;

线性表的价值在于，它对数据的存储方式是按照顺序的存储。当数据的元素个数不确定，且需要经常进行数据的新增和删除时，那么链表会比较合适。链表的翻转、快慢指针的方法，是你必须掌握的内容。

05 | 栈：后进先出的线性表，如何实现增删查？

栈是什么？

栈的基本操作

顺序栈

链栈

栈的案例

06 | 队列：先进先出的线性表，如何实现增删查？

队列是什么

加了限制的特殊线性表

队列对于数据的增删查处理

循环队列的数据操作

移动指针 but 数组越界 标识判断数组是否为满，指针像时针一样循环。 两种情况指针重叠：数组为满和空

链式队列的数据操作

有了头结点后，哪怕队列为空，头结点依然存在，能让 front 指针和 rear 指针依然有意义。避免成为野指针

总结

循环队列必须有一个固定的长度，因此存在存储元素数量和空间的浪费问题，而链式队列不存在这种问题，所以在空间上，链式队列更为灵活一些。 可以确定队列长度最大值时，建议使用循环队列。无法确定队列长度时，应考虑使用链式队列。 面对数据处理顺序非常敏感的问题时，队列一定是个不错的技术选型。

数据结构：线性表（栈、队列）、数组