小白入门必学——时间复杂度

目录

1.时间复杂度的概念

1.1什么是大O

1.2 如何描述时间复杂度

1.3 时间复杂度的简化

2.空间复杂度分析

---

1.时间复杂度的概念

时间复杂度：方便开发者估算出程序的运行时间。通常估计算法的操作单元数量，来代表程序消耗的时间， 默认CPU的每个单元运行消耗的时间都是相同的。

假设：算法的问题规模为n，那么操作单元数量用函数f(n)来表示

算法的渐近时间复杂度（时间复杂度, O(f(n))）：随着数据规模n的增大，算法执行时间的增长率和  操作单元数量f(n)的增长率相同。

1.1什么是大O

算法导论给出的解释：大O用来表示上界的，算法的最坏情况运行时间的上界，就是对任意数据输入的运行时间的上界。如：插入排序，插入排序的时间复杂度O(n^2)，但是在数据本来有序的情况下时间复杂度是O(n)，也就对于所有输入情况来说，最坏是O(n^2) 的时间复杂度

快速排序：时间复杂度O(nlogn)，但是当数据已经有序情况下，快速排序的时间复杂度是O(n^2) 的，严格从大O的定义来讲，快速排序的时间复杂度应该是O(n^2)；

但是快速排序是O(nlogn)的时间复杂度，这是业内的一个默认规定，我们这里说的O 代表的就是一般情况，不是严格的上界

同一个算法的时间复杂度不是一成不变的，和输入的数据形式有关系

1.2 如何描述时间复杂度

不同算法的时间复杂度，在不同数据输入规模下的差异。不是时间复杂越低的越好，要考虑数据规模，如果数据规模很小，O(n^2)的算法比 O(n)更合适

 计算时间复杂度时，忽略常数项系数：大O是数据量级突破一个点且数据量级非常大的情况下所表现出的时间复杂度，这个点的 常数项系数不起决定性作用。

算法时间复杂：

O(1)常数阶 < O(logn)对数阶 < O(n)线性阶 < O(n^2)平方阶 < O(n^3)(立方阶) < O(2^n) (指数阶)

注意！！！

logn： 是忽略底数的描述

log2(10)为常数，而在时间复杂度里常数项可以忽略，所以log里对于底数取什么值是不影响的

1.3 时间复杂度的简化

如：O(2*n^2 + 10*n + 1000)

1. 去掉运行时间中的加法常数项：O(2*n^2 + 10*n)
2. 去掉常数系数 ：O(n^2 + n)
3. 只保留保留最高项 ：O(n^2)

2.空间复杂度分析

空间复杂度是对一个算法在运行过程中占用内存空间大小的量度，记做S(n)=O(f(n)。利用程序的空间复杂度，对程序运行中需要多少内存有个预先估计。

空间复杂度是考虑程序运行时占用内存的大小，而不是可执行文件的大小。

当消耗空间和输入参数n保持线性增长，这样的空间复杂度为O(n)

递归的时候，空间复杂度为logn