时间复杂度&&空间复杂度
2022-02-06 00:05 作者:hey_just_do_it | 我要投稿
时间复杂度
常见的时间复杂度
时间复杂度是用来评估算法运行效率的单位,一般来说,时间复杂度高的算法比复杂度低的算法慢。之所以说一般来说符合情况是由于算法的数据规模一定程度上也影响着算法运行的快慢。常见的时间复杂度如下:


按效率对时间复杂度进行排序:O(1)<O(logn)<O(n)<O(nlogn)<O(n2)<O(n2logn)<O(n2logn)<O(n^3)...
快速判断时间复杂度方法
在绝大多数简单情况下,快速判断复杂度的方法有:
确定数据规模n
如果循环在不断减半,复杂度为lognlognlogn(如常见时间复杂度中的最后一个例子)
如果是k层n的循环,复杂度为n^k
空间复杂度
空间复杂度是用来评估算法内存占用大小的单位。空间复杂度的表达方式与时间复杂度是完全一样的,不过时间复杂度是根据算法语句的运行次数进行就计算的,而空间复杂度是根据算法运行过程中所占用的内存空间进行计算的。以下为算法中几个常见的简单的空间复杂度:
如果算法只使用的几个变量,则复杂度为O(1)
如果算法使用了长度为n的一维列表,则复杂度为O(n)
如果算法使用了m行n列的二维列表,则复杂度为O(m∗n)
一般情况下,我们可以使算法占用更多的内存空间,以此来减小时间复杂度,即“空间换时间”。目前绝大多数公司更加关注算法的时间复杂度,因为它们一般都不缺内存空间,愿意让算法尽可能的占用更多内存来减少算法的时间复杂度,从而提高用户体验感。