时间复杂度和空间复杂度的计算

1. 这俩货是干嘛的？

1. 时间维度：是指执行当前算法所消耗的时间，我们通常用「时间复杂度」来描述。（就我个人而言，我觉得时间复杂度是评估代码在计算机cpu中的运行总行数，注意是评估，并不是量化的数据）
   空间维度：是指执行当前算法需要占用多少内存空间，我们通常用「空间复杂度」来描述。（评估代码在计算集内存中声明单元变量的总个数）
2. 对于同样的编程问题，使用不同的算法最终的结果是一样的，但计算机计算过程是消耗的时间和空间却不一样，但是我们又不能去计算每个算法用的时间和空间，我们只能通过数学的方法来估算这个算法，这就是时间复杂度和空间复杂度产生的原由。时间复杂度和空间复杂度也是判断算法效率的重要指标；

2. 先看时间复杂度

1. 有的同学说，计算时间哪有这么复杂，我就在旁边盯着程序运行，掐表计算不可以吗？当然可以！！！凡是有个蛋是，同学你觉得合适么？

鉴于这位同学靠谱的想法，所以 O符号表示法 就应运而生，即 T(n) = O(f(n))；单位秒呢？大O表示法指的并非以秒为单位的速度。大O表示法让你的程序能够比较操作数，它指出了算法运行时间的增速。大O表示法说的是最糟的情形。

2. 先来个例子吧

image.png
对于这个while循环时间复杂度为 O(n)，what?? 懵逼脸
在 大O符号表示法中，时间复杂度的公式是： T(n) = O( f(n) )，其中f(n) 表示每行代码执行次数之和，而 O 表示正比例关系，这个公式的全称是：算法的渐进时间复杂度。
接下来可以瞪大眼睛来一场微积分了：
我们现在假设每段代码的运行时间是相等的，都为t.
那么这段代码中的总时间就是: 1 * t + 1 * t + n * t + n * t + n * t ； 分别代表了5行代码的执行时间；
那么合起来就是 O(（ 2 + 3n ) t ）。
**，程序运行时间和n的变化密切相关；
由于大O计算法计算的是程序运行时间的增速的角度度量的，所以： O(（ n ) t ）。当然每行代码的运行是按 “t” 是我们为了解释假象出来，所以最终的结果就是 O(n)。P.S 这段解释有点绕，欢迎留言。

3. 常见的时间复杂度量级有:

• 常数阶O(1)

• 线性阶O(n)

  
  image.png

• 对数阶O(logN)

  
  image.png

• 线性对数阶O(nlogN)

  
  O(nlogN)
• 平方阶O(n²)：常见的双重for循环
• 立方阶O(n³) ： 三重for循环
• K次方阶O(n^k) ： 这个和O(n²)又什么区别吗 image.png
• 指数阶O(2^n) ：和O(logN)相对
• 指数阶O(n！) ：著名的旅行商问题就是这个算法，非常优秀的人都说没有优化的空间。YOU CAN YOU UP!

2. 再看空间复杂度

空间复杂度是对一个算法在运行过程中临时占用存储空间大小的一个量度，同样反映的是一个趋势，我们用 S(n) 来定义：S(n)=O(f(n))。上面我也说了，这个就相对简单很多，常见的有 O(1)、O(n)、O(n²)。

• 0(1)

  
  image.png

• 0(n) : 例如声明一个一维数组

  
  image.png

• 0(n^2) : 例如声明一个二维数组

  
  image.png