数据结构的时间复杂度和空间复杂度

        

目录

        

时间复杂度

        空间复杂度

---

时间复杂度

         基本操作的执行次数，为时间复杂度。

        我们使用大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)