数据结构的时间复杂度和空间复杂度
目录
时间复杂度
空间复杂度
时间复杂度
基本操作的执行次数，为时间复杂度。
我们使用大O的渐进表示法来表示时间复杂度。
怎么使用？
先看例子：
在这个例子中， 基本操作为变量 count 的 加加 操作，并且，执行次数与 参数 N 有关，操作次数为 N^2+2*N +10
实际中我们计算时间复杂度时，我们其实并不⼀定要计算精确的执行次数，而只需要大概执行次数，也就是我们使用的大O的渐进表示法。
所以现在我们应该怎么使用大O的渐进表示法表示呢？
大O的渐进表示法：
1.用 O(1) 表示固定的操作次数。
2.在修改最后的运行次数的函数中，只保留最高次项，并且除去最高次项前面的系数，则为结果。
显然，上面的示例代码就是第二种情况。表示成O(N^2)
再来一个例子：
这是一个二分查找的代码，代码结束可能有这几种情况：
最好情况：运行一次找到。
较好情况：运行一半次数找到。
最坏情况：运行最后一次才找到。
那么，在实际中我们⼀般情况关注的是最坏运行情况，这里的代码执行次数与元素个数有关，用 N 表示元素个数。则：
由图分析得到：
2^（循环次数 - 1）= N -----> 循环次数 = 
时间复杂度为也就是上图。
对数以2为底的情况下，可以简写成O(logN)
空间复杂度
空间复杂度是对代码在运行过程中临时占用存储空间大小的量度。
空间复杂度也使用大O渐进表示法。
例子1：
使用了常数个额外空间，所以空间复杂度为O(1)
例子2：
临时创建的空间大小与n有关，所以是动态开辟了n个空间，空间复杂度为O(n)
例子3：
这里每次递归都会调用函数add，调用就会开辟内存空间，调用了N次，开辟了N个栈帧，每个栈帧使用了常数个空间。空间复杂度为O(N)