时间复杂度
1、概念引入
先说结论：时间复杂度是用来估计算法运行时间的一个式子（单位）。
例如：这四组代码，哪组运行时间最短？
q：我们该用什么方式来体现算法运行的快慢？
a：我们利用时间复杂度来估计算法运行时间，时间复杂度是一个大致时间，而不是精确时间。
那么，以上四组代码可以分别用时间复杂度 O(1)、O(n) 、 O(n²) 、 O(n³)来表示。
2、O()括号中填的内容是单位
按照上述的估算方法，感觉上，下面这组代码的时间复杂度好像是O(3)
下面这组代码的时间复杂度好像是O(n²+n)
但是并非这样，因为O(1)、O(n)之中，1和n都是一个单位，描述的是大致的时间；
单位是计量事物的标准量的名称，厘米是单位，米是单位，1和n还有n平方之类的也是单位，但是在时间复杂度的规定中，1被规定为一个单位，3不是一个单位，打印3条语句和打印1条语句花费的时间对于计算机来说几乎一致，它们都是同一个规模的程序，所以时间复杂度都是O(1)。
3、时间复杂度O(logn)
当程序出现循环减半时，会有程序时间复杂度为O(logn)的情况。
看下面这个程序：
n=64时：
如何规定这种程序的时间复杂度呢？
4、关于时间复杂度我们需要知道的
- 时间复杂度是用来估计算法运行时间的一个式子（单位）。
- 一般来说，时间复杂度高的算法比复杂度低的算法慢。
- 常见的时间复杂度（按效率排序）：O(1) < O(logn) < O(n) < O(nlogn) < O(n²) < O(n²logn) < O(n³)
- 复杂问题的时间复杂度：O(n!)O(2^n)O(n^n)
5、如何简单快速地判断算法复杂度
空间复杂度
1、概念
空间复杂度是用来评估算法内存占用大小的式子
2、空间复杂度的表示方式
与时间复杂度完全一样
- 算法使用了几个变量：O(1)
- 算法使用了长度为n的一位列表：O(n)
- 算法使用了m行n列的二维列表：O(mn)
3、空间换时间
比如我写程序的时候，优先考虑让它运行速度更快，即使多占用一些内存。
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
文章由极客之音整理，本文链接：https://www.bmabk.com/index.php/post/122879.html
