如何判断时间复杂度和空间复杂度

如何判断时间复杂度和空间复杂度

我也在学习中，有不足的地方大家请指出。

我认为下面的文章不错，我也是学习以下大佬的。

https://blog.csdn.net/weixin_45329397/article/details/121308688

https://blog.csdn.net/a308601801/article/details/89667446

1.什么是复杂度

在设计满足问题需求的算法的时候，复杂度的估算是非常重要的。我们不可能把每一个算法去实现一遍去看看是否足够快。所以应当通过估算算法的复杂度来判断所想的算法是否足够高效。

2.时间复杂度

我们经常用到 o (1), o (n), o (logn), o (nlogn) 来表示对应算法的时间复杂度。

时间复杂度的排序是O(1) < O(logn) < O(n) < O(nlogn) < O(n^2) < O(2^n) < O(n!) < O(n^n)。

（1）时间复杂度为 O (1)，代码只被执行一次。

（2）时间复杂度为 O (n)，比如常见的遍历算法。 也就是一个for循环的时间复杂度。

（3）O(n^2)就是嵌套for循环，就是两个for循环，是不是相当于运行了n*n次。比如冒泡和选择排序。

（4）再比如 O (logn)，（ log 是以 2 为底）。二分搜索就是 O (logn) 的算法，每找一次排除一半的可能。

（5）O (nlogn) 同理，就是 n 乘以 logn，归并排序就是 典型的例子。 

3.空间复杂度

可以类比于时间复杂度

（1）O(1)单个变量所占的空间永远为1

（2）O(n)数组里面有n个值，占用了n个内存单元

（3）O(n^2)可以想象为一个正方形，边长为n，存储了n的二次方个变量