第一天：一个视频教会你时间复杂度和空间复杂度(leetcode)

关于作者：

大家好，我是Leetcode 2020--2022,连续3年金牌获得者，和亚洲区域赛铜牌获得者，

先后在字节和大疆从事技术研发，现在是阿里达摩院的扫地僧，面试专家，CSDN博客专家。

对算法一定的见解，是一个刷题10年的算法爱好者 ，利用工作之余刷leetcode。成为leetcode官方答案贡献者之一。

时间复杂度：计算机器用的时间

总之：算法的执行效率，算法的执行时间和算法的输入值之间的关系！

每一行代码的 （执行次数*执行时间）

减去：单个次数

忽略：单次执行的时间

最终是执行次数！这种表示方法我们称为「 大O符号表示法」，又称为渐进符号，是用于描述函数渐进行为的数学符号

举例:

分析:本来是a+10b+c

然后忽略少的,变成了nb

n就是你的输入值,参数,然后就是 O(n)

常见的时间复杂度：O(1)  <  O(logn)  <  O(n)  < O(nlogn) <   O(n的二次方) 

总结：计算循环的次数！2个循环相乘

图片：

常用的时间复杂度按照耗费的时间从小到大依次是：O(1)<O(logn)<O(n)<O(nlogn)<O(n²)<O(n³)

O(1) :无论输入的值是多少,都是执行一次(执行时间和输入值基本每什么关系)

而且:没有循环,就是o(1)

O(n) :循环了多少次,就是o(n)

举例:

执行一次的时间是b,循环了n次,那么就是nb .因为是输入的关系就是o(n)

need-to-insert-img

O(logn)

循环的次数是要除以2    所以就是o(logn)

O(nlogn)

套的循环 ：循环中的语句乘于所有循环的大小。

2个循环:一个是n  一个是logn 相乘就是nlogn

O(n²)

2个循环:一个是n  一个是n 相乘就是n2

2. 空间复杂度

算法存储空间和输入值之间的关系！

说白了就是占用的内存大小

常见的举例：O(1)   O(n)   O(n的平方)

用的最多的是O(1) ,O(n) 

O(1) 

不管输入的值多大,占用的内存都是一个

 O(n) : 一般集合或者数组,是否有集合

need-to-insert-img

总结：和内存大小。集合和一个元素的空间大小

注意：递归调用不一样！也是o(n)

我们常说的：空间换时间和时间换空间！

一般都是时间>空间!  现在的手机内存比较高的!

need-to-insert-img

参考博客:

https://blog.csdn.net/zuochang_liu/article/details/106101435