测试基础 1. 时间复杂度和空间复杂度 (7 天掌握算法面试必考知识点)

zailushang · June 28, 2020 · Last by magicyang replied at June 29, 2020 · 1115 hits

全文内容主要源于极客大学的算法课,仅作为笔记使用。

学习计划

由于每天都需要写学习心得和作业,所以写此贴作为笔记。也希望可以帮助到有需要的同学。

1、时间复杂度

(1)时间复杂度的统计维度

  • O(1): Constant Complexity 常数复杂度
  • O(log n): Logarithmic Complexity 对数复杂度
  • O(n): Linear Complexity 线性时间复杂度
  • O(n2): N Square Complexity 平方
  • O(n3): N CubicComplexity 立方
  • O(2n): Exponential Growth 指数
  • O(n!): Factorial 阶乘

(2)各时间复杂度的耗时曲线


从图中可以看出,当n小于5时,不同的时间复杂度耗时差不多。
当n增大时,不同时间复杂度算法耗时差距非常大。所以也就不难理解,大型公司对算法的要求越来越高,是因为当遇到大数据量处理时,不同的算法能力,需要的服务器成本和代码性能是有天壤之别的。

(3)算法面试题的四个套件

  • 算法题的内容确认无误;
  • 思考所有可能解决的办法;
  • 比较这些方法的时间和空间复杂度;
  • 找出最优的解决方案(时间复杂度最低,兼顾内容使用更少的)

(4)递归的时间复杂度分析

  • 将递归的执行顺序画出树形结构,称为递归状态的递归树;
  • 主定理计算时间复杂度

比如:斐波那契数列
Fib: 1, 1, 2, 3, 5, 8, 13, 21, 34...
方法定义:F(1)=1,F(2)=1, F(n)=F(n - 1)+F(n - 2)(n ≥ 3,n ∈ N*)

def fib(n: int):
if n < 2: return n
return fib(n-1) + fib(n-2)

绘制递归图,以n=6为例:

常用算法应用主定理:(记住如下算法对应公式,并尝试理解)

2、空间复杂度

空间复杂度和时间复杂度的情况类似,但是更加简单。

数组的长度

如果代码中开了数组,则数组的长度基本就是空间复杂度。
比如:

  • 一维数组,数组长度等于元素个数,则空间复杂度就是O(n)
  • 二维数组,数组长度为n2,则空间复杂度为O(n2)

递归深度

如果代码中有递归,那么递归最大深度,就是空间复杂度的最大值。如果递归里面又开了数组,那么两者中的最大值就是空间复杂度。

实战分析

详见leetcode的爬楼梯示例:爬楼梯题解

3、小结

  • 常用工具配置
  • 基本功和编程指法
  • 常见的时间、空间复杂度分析 对于开发来说,掌握熟悉的工具和TOP用法,能节省开发中的工具使用效率。 对于顶级工程师来说,对自己代码的时间复杂度和空间复杂度了解,是必备技能。

总结

时间复杂度:假设入参为n,程序运行的次数与n的关系,即为时间复杂度。
时间复杂度优化顺序:O(1) > O(log n) > O(n) > O(n2) > O(n3) > O(2n) > O(n!)

空间复杂度:代码中数组的大小或递归深度的最大值。
空间复杂度优化顺序:O(1) > O(log n) > O(n) > O(n2) > O(n3) > O(2n) > O(n!)

为什么复杂度对于代码来说如此重要?
从互联网公司成本来看:

  • 硬件成本:时间复杂度低的代码,可以降低CPU压力,减少服务器的CPU成本;空间复杂度低的代码,可以降低内存占用,减少服务器的内存成本;
  • 产品成本:时间复杂度和空间复杂度越低,程序执行时间越低和遇到的性能故障越少,产品的性能就会越好,越容易获取用户喜欢。
  • 质量评估成本:对设计的算法性能有两种评测方法,一是运行耗时评估,成本高、不稳定、强依赖硬件,而就是时间复杂度和空间复杂度评估,成本低、准确性高。

参考资料:

如果觉得我的文章对您有用,请随意打赏。您的支持将鼓励我继续创作!
共收到 3 条回复 时间 点赞

开始刷题了么?😂

simple 回复

哈哈,没有,从来不刷题,只是补补算法知识,以前没重视

入门级:不用递归手写个快排吧。
中级:写个桶排序吧。
高级:来个红黑树吧。
PS:我可能脉脉看多了,看到太多黑头条的。。。O(∩_∩)O

需要 Sign In 后方可回复, 如果你还没有账号请点击这里 Sign Up