数据结构与算法:重新掌握的旅程

发表时间: 2021-10-30 16:19

一、代码效率优化方法论

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 指针依然有意义。避免成为野指针

总结

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

数据结构:线性表(栈、队列)、数组