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.广义:数据结构是指一组数据的存储结构。算法是操作数据的一组方法
    i. 引入图书馆找书的例子
  • 2.狭义:指出专栏主要讲解著名的数据结构和算法,队列,栈,二分查找,动态规划等。经典的算法可以高效的帮我们解决实际开发问题
  • 3.引入,为什么数据结构和算法会放到一起
    数据结构是为算法服务的,算法要作用在特定的数据结构之上。
    数据结构是静态的,它只是组指数据的一种方式。如果不在它的基础上操作,构建算法,孤立存在的数据结构就没有用。

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

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

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

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

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

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

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