引入
我们结束了时间复杂度的学习,了解了常见的时间复杂度的计算以及不同时间复杂度之间的关系,今天我们看看最坏情况和平均情况,以及空间复杂度。
最坏情况和平均情况
比如有一个数列,我们想找数字 1
- 最好情况:数列是从1~10排列,找第一个就找到1了,O(1)就搞定。
- 最坏情况:最坏的就是数列是从10~1排列,找到最后一个 n 才找到10,那复杂度就是O( n )。
- 平均情况:我们期望运行的时间,比如我希望3分钟搞定。
- 最坏运行时间:这是一种保证,也就是说,我的算法在最坏情况也,需要多少时间搞定,
通常情况下,我们说的运行时间,都是最坏运行时间。
算法的空间复杂度
在写代码的时候,我们可以用空间换取时间
,当然也可以用时间换取空间
。
1 |
|
这是一个很简单的计算闰年的算法,根据输入的值进行计算,然后判断。我们换一种方式
1 |
|
第二种算法,我们提前准备了哪一年是不是闰年的数据库,存储在内存中,然后直接调用即可,不用计算。
- 时间复杂度: 结果靠计算,每一次都要计算,花费的时间长,但不占用内存空间。
- 空间复杂度: 结果不用计算,所有结果都存储在内存中,不需要每次都计算。花费时间短,但需要占用内存空间,这就是空间复杂度。
那么究竟哪一种比较好呢?这就要根据实际情况了,如果内存很大,算力很小,那算法就多占用空间复杂度,反之,则多占用时间复杂度。
算法的时间复杂度
通过计算算法所需的存储空间实现,算法的空间复杂度的计算公式记作S( n )=O(f(n))
,感觉和时间复杂度差不多。
n 表示问题的规模
f( n )表示 n 所占用的空间函数
通常情况下:
- 时间复杂度表示:运行时间的需求
- 空间复杂度表示:空间需求
- 如果让我们求一个算法的复杂度,往往指的是
时间复杂度。
尾巴
这是我的个人学习笔记,主要是应付考研复习使用,充斥着一些吐槽和个人观点,并不严谨,欢迎大家参考、指正。