chaoz的杂货铺

生命有息、学无止境、折腾不止

0%

数据结构与算法之美

笔记整理

1.学习技巧–王争

    1. 边学边练,适度刷题
    1. 多问、多思考、多互动
    1. 打怪升级学习法
      比如,针对这个专栏,你就可以设立这样一个目标:每节课后的思考…
    1. 知识需要沉淀,不要想试图一下子掌握所有
      学习知识的过程是反复迭代、不断沉淀的过程,书读百遍其义自见。

2.时间复杂度思考

3.空间复杂度思考

总结

一、什么是复杂度分析?

1.数据结构和算法解决是“如何让计算机更快时间、更省空间的解决问题”。
2.因此需从执行时间和占用空间两个维度来评估数据结构和算法的性能。
3.分别用时间复杂度和空间复杂度两个概念来描述性能问题,二者统称为复杂度。
4.复杂度描述的是算法执行时间(或占用空间)与数据规模的增长关系。

二、为什么要进行复杂度分析?

1.和性能测试相比,复杂度分析有不依赖执行环境、成本低、效率高、易操作、指导性强的特点。
2.掌握复杂度分析,将能编写出性能更优的代码,有利于降低系统开发和维护成本。

三、如何进行复杂度分析?

1.大O表示法

1)来源
算法的执行时间与每行代码的执行次数成正比,用T(n) = O(f(n))表示,其中T(n)表示算法执行总时间,f(n)表示每行代码执行总次数,而n往往表示数据的规模。
2)特点
以时间复杂度为例,由于时间复杂度描述的是算法执行时间与数据规模的增长变化趋势,所以常量阶、低阶以及系数实际上对这种增长趋势不产决定性影响,所以在做时间复杂度分析时忽略这些项。

2.复杂度分析法则

1)单段代码看高频:比如循环。
2)多段代码取最大:比如一段代码中有单循环和多重循环,那么取多重循环的复杂度。
3)嵌套代码求乘积:比如递归、多重循环等
4)多个规模求加法:比如方法有两个参数控制两个循环的次数,那么这时就取二者复杂度相加。

四、常用的复杂度级别?

多项式阶:随着数据规模的增长,算法的执行时间和空间占用,按照多项式的比例增长。包括,
O(1)(常数阶)、O(logn)(对数阶)、O(n)(线性阶)、O(nlogn)(线性对数阶)、O(n^2)(平方阶)、O(n^3)(立方阶)
非多项式阶:随着数据规模的增长,算法的执行时间和空间占用暴增,这类算法性能极差。包括,
O(2^n)(指数阶)、O(n!)(阶乘阶)

五、如何掌握好复杂度分析方法?

复杂度分析关键在于多练,所谓孰能生巧。

4.数据结构与算法思考

算法就是操作数据的一组方法。
数据结构就是一组数据的存储结构。
二者关系:数据结构是为算法服务的,算法要作用于特定的数据结构之上。数据结构是静态的,必须基于它操作和构建算法,数据结构才有意义。

数据结构三要素:数据逻辑结构、数据存储结构和数据的运算。

从广义和狭义两个层面理解数据结构与算法

  • 1.广义:数据结构是指一组数据的存储结构。算法是操作数据的一组方法

    • 图书馆找书的例子
  • 2.狭义:指出专栏主要讲解著名的数据结构和算法,队列,栈,二分查找,动态规划等。经典的算法可以高效的帮我们解决实际开发问题

  • 3.为什么数据结构和算法会放到一起?

数据结构是为算法服务的,算法要作用在特定的数据结构之上。
数据结构是静态的,它只是组指数据的一种方式。如果不在它的基础上操作,构建算法,孤立存在的数据结构就没有用。

复杂度就是用来分析算法执行效率与数据规模之间增长关系。

性能测试与复杂度分析不冲突,原因如下:

1、性能测试是依附于具体的环境,如SIT、UAT机器配置及实例数量不一致结果也有差别。
2、复杂度分析是独立于环境的,可以大致估算出程序所执行的效率。
3、将复杂度熟记于心,能够写出更高效率、更好性能的代码。若某接口通过性能测试,达不到预期,还可以用复杂度分析接口代码,找出最影响性能的代码,进行优化。

每段代码都分析一下时间复杂度、空间复杂度,是不是很浪费时间呢?

这个问题分两种情况讨论
1、开发过程中,码代码的过程中就能得出其复杂度,这并不会太多的浪费时间,同时只有分析了每段代码的复杂度,才能估算出它们的执行效率。
2、优化代码时,只有在分析每段代码的复杂度后,才能定位问题代码,才能做相应优化

05、为什么数组要从 0 开始编号,而不是从 1 开始呢?

1、数组(Array):

是一种线性表数据结构。它用一组连续的内存空间,来存储一组具有相同类型的数据。

2、线性表(Linear List):

顾名思义,线性表就是数据排成像一条线一样的结构。每个线性表上的数据最多只有前和后两个方向。其实除了数组,链表、队列、栈等也是线性表结构。

3、非线性表:

比如二叉树、堆、图等。之所以叫非线性,是因为,在非线性表中,数据之间并不是简单的前后关系。

4、连续的内存空间和相同类型的数据:

这两个限制也让数组的很多操作变得非常低效,比如要想在数组中删除、插入一个数据,为了保证连续性,就需要做大量的数据搬移工作。
当计算机需要随机访问数组中的某个元素时,它会首先通过下面的寻址公式,计算出该元素存储的内存地址:a[i]_address = base_address + i * data_type_size

5、删除操作:

记录下已经被删除的数据,每次的删除操作并不是搬移数据,只是记录数据已经被删除,当数组没有更多的存储空间时,再触发一次真正的删除操作。即JVM标记清除垃圾回收算法。

6、警惕数组的访问越界问题:

关于数组越界访问导致死循环的问题,我也动手实践了一下,发现结果和编译器的实现有关,gcc有一个编译选项(-fno-stack-protector)用于关闭堆栈保护功能。默认情况下启动了堆栈保护,不管i声明在前还是在后,i都会在数组之后压栈,只会循环4次;如果关闭堆栈保护功能,则会出现死循环。请参考:https://www.ibm.com/developerworks/cn/linux/l-cn-gccstack/index.html

7、容器能否完全替代数组?

相比于数组,Java中的ArrayList封装了数组的很多操作,并支持动态扩容。扩容时比较消耗内存,因为涉及到内存申请和数据搬移。
数组适合的场景:
Java ArrayList的使用涉及装箱拆箱,有一定的性能损耗,关注性能,或者希望使用基本类型,就可以选用数组;
数据大小事先已知,并且涉及的数据操作非常简单,使用数组;
表示多维数组时,数组往往更加直观;
业务开发容器即可,底层开发,如网络框架,性能优化。选择数组。

8、标记清除垃圾回收算法:

大多数主流虚拟机采用可达性分析算法来判断对象是否存活,在标记阶段,会遍历所有 GC ROOTS,将所有 GC ROOTS 可达的对象标记为存活。只有当标记工作完成后,清理工作才会开始。
不足:1.效率问题。标记和清理效率都不高,但是当知道只有少量垃圾产生时会很高效。2.空间问题。会产生不连续的内存空间碎片。

9、二维数组的内存寻址公式是怎样的呢?

对于 m n 的二维数组,a [ i ][ j ] (i < m,j < n) 的地址为:
address = base_address + ( i
n + j) * type_size

10、三维数组:

三维数组假设是 mnq, a[i][j][k]_address=base_address + (inq + jq + k)type_size

06 链表

1、学习链表有什么用?

一、基于链表实现 LRU 缓存淘汰算法:

我们维护一个有序单链表,越靠近链表尾部的结点是越早之前访问的。当有一个新的数据被访问时,我们从链表头开始顺序遍历链表。

1、如果此数据之前已经被缓存在链表中了,我们遍历得到这个数据对应的结点,并将其从原来的位置删除,然后再插入到链表的头部。

2、如果此数据没有在缓存链表中,又可以分为两种情况:

  • 如果此时缓存未满,则将此结点直接插入到链表的头部;

  • 如果此时缓存已满,则链表尾结点删除,将新的数据结点插入链表的头部。

二、2.如何通过单链表实现“判断某个字符串是否为水仙花字符串”?

1)前提:字符串以单个字符的形式存储在单链表中。
2)遍历链表,判断字符个数是否为奇数,若为偶数,则不是。
3)将链表中的字符倒序存储一份在另一个链表中。
4)同步遍历2个链表,比较对应的字符是否相等,若相等,则是水仙花字串,否则,不是。

2、什么是链表

1.和数组一样,链表也是一种线性表。
2.从内存结构来看,链表的内存结构是不连续的内存空间,是将一组零散的内存块串联起来,从而进行数据存储的数据结构。
3.链表中的每一个内存块被称为节点Node。节点除了存储数据外,还需记录链上下一个节点的地址,即后继指针next。

3、为什么使用链表?

1.插入、删除数据效率高O(1)级别(只需更改指针指向即可),随机访问效率低O(n)级别(需要从链头至链尾进行遍历)。
2.和数组相比,内存空间消耗更大,因为每个存储数据的节点都需要额外的空间存储后继指针。

4、常用链表

单链表、循环链表、双向链表



5、数组与链表的比较

1.插入、删除和随机访问的时间复杂度
数组:插入、删除的时间复杂度是O(n),随机访问的时间复杂度是O(1)。
链表:插入、删除的时间复杂度是O(1),随机访问的时间复杂端是O(n)。
链表增删快但是查询比较慢。
2.数组缺点
1)若申请内存空间很大,比如100M,但若内存空间没有100M的连续空间时,则会申请失败,尽管内存可用空间超过100M。
2)大小固定,若存储空间不足,需进行扩容,一旦扩容就要进行数据复制,而这时非常费时的。
3.链表缺点
1)内存空间消耗更大,因为需要额外的空间存储指针信息。
2)对链表进行频繁的插入和删除操作,会导致频繁的内存申请和释放,容易造成内存碎片,如果是Java语言,还可能会造成频繁的GC(自动垃圾回收器)操作。
4.如何选择?
数组简单易用,在实现上使用连续的内存空间,可以借助CPU的缓冲机制预读数组中的数据,所以访问效率更高,而链表在内存中并不是连续存储,所以对CPU缓存不友好,没办法预读。
如果代码对内存的使用非常苛刻,那数组就更适合。

6、缓存:

是一种提高数据读取性能的技术,在硬件设计、软件开发中都有着非常广泛的应用,比如常见的 CPU 缓存、数据库缓存、浏览器缓存等等。

7、小结

和数组相比,链表更适合插入、删除操作频繁的场景,查询的时间复杂度较高。不过,在具体软件开发中,要对数组和链表的各种性能进行对比,综合来选择使用两者中的哪一个。

8、问题:

如何判断一个字符串是否是回文字符串的问题,我想你应该听过,我们今天的思题目就是基于这个问题的改造版本。如果字符串是通过单链表来存储的,那该如何来判断是一个回文串呢?你有什么好的解决思路呢?相应的时间空间复杂度又是多少呢?

07链表

总结

这节我主要和你讲了写出正确链表代码的六个技巧。分别是理解指针或引用的含义、警惕指针丢失和内存泄漏、利用哨兵简化实现难度、重点留意边界条件处理,以及举例画图、辅助思考,还有多写多练。

练习题LeetCode对应编号:206,141,21,19,876。
参考(C#):https://www.cnblogs.com/errornull/p/9860724.html

1、指针或引用的含义

指针是一个变量,该变量中存的是其它变量的地址。将普通变量赋值给指针变量,其实是把它的地址赋值给指针变量。

2、指针丢失和内存泄漏

在插入和删除结点时,要注意先持有后面的结点再操作,否者一旦后面结点的前继指针被断开,就无法再访问,导致内存泄漏。

3、利用哨兵简化难度

链表的插入、删除操作,需要对插入第一个结点和删除最后一个节点做特殊处理。利用哨兵对象可以不用边界判断,链表的哨兵对象是只存指针不存数据的头结点。

4. 重点留意边界条件处理

操作链表时要考虑链表为空、一个结点、两个结点、头结点、尾结点的情况。学习数据结构和算法主要是掌握一系列思想,能在其它的编码中也养成考虑边界的习惯。

5. 举例画图,辅助思考

对于比较复杂的操作,可以用纸笔画一画,释放脑容量来做逻辑处理(时间换空间思想),也便于完成后的检查。

作业

  • 单链表反转

  • 链表中环的检测

  • 两个有序的链表合并

  • 删除链表倒数第 n 个结点

  • 求链表的中间结点

用哨兵来简化编码实现,你是否还能够想到其他场景,利用哨兵可以大大地简化编码难度?

喜欢这篇文章?打赏一下作者吧!

欢迎关注我的其它发布渠道