JS版数据结构之 算法复杂度(时间复杂度、空间复杂度)_js算法时间复杂度

一、算法复杂度

算法是指解决问题的方案准确而完整的描述，是一系列解决问题的清晰指令，算法代表着：用系统的方法解决问题的策略机制。
算法研究的是如何花最少的时间、最少的内存空间完成相同的需求。

1. 时间维度

时间维度：执行当前算法所消耗的时间，时间越短，算法越好。
时间复杂度：一个代码执行的时间趋势，执行次数与执行参数息息相关，如果一个问题的规模是n，解决这个问题的某一算法需要时间T(n)。

T(n) = O(f(n)) //大O表示法
O：某个算法耗时与数据增长量之间的关系。
T：代表算法需要执行的总时间
n：输入的数据量
大O表示法：代码执行时间随数据规模增长的变化趋势，时间复杂度表示的是变化趋势，并不是真正的执行时间。

常见的时间复杂度：

1. 常数阶：O(1)
2. 线性阶：O(n)，数据量增大n倍时，耗时也增大n的n倍
3. 平方阶：O(n^2)
4. 立方阶：O(n^3)
5. 对数阶：O(logn)。如二分查找，n以对数的规模进行递减 n->n/2->n/4
6. 线性对数阶：O(nlogn)
7. 指数阶：O(2^n)

优劣对比：O(1)<O(logn)<O(n)<O(nlogn)<O(n^ 2)< O(n^ 3)<O(2^ n)

2. 空间维度

空间维度：执行当前代码所消耗的内存空间。
S(n) = T(f(n))
空间复杂度：是对一个算法在运行中临时占用空间大小的度量。表示的是：算法存储空间与输入值之间的关系。
通常来讲，只要我们的算法不涉及到动态的空间，如递归、栈，空间的复杂度通常为常数O(1)
算法的空间复杂度，并不是指实际占用的空间，而是计算整个算法的辅助空间单元(变量)的个数，与问题的规模没有关系，空间复杂度主要看新开辟的变量个数。

【注】不要再循环体里面不停的申明变量。只改变值的话是不会加深空间复杂度的。

对内存的管理机制：
标记计数：进入环境是标记，退出后会标记为离开环境
引用计数
js垃圾回收机制
v8：新生代、老生代