数据结构-时间复杂度？空间复杂度？
一、为什么引入复杂度
好的数据结构和算法能够大大的缩短代码的执行时间和存储空间，那么我们怎样去衡量呢？ 判断一段代码执行的效率最简单、最直接的办法就是放在机器上执行一遍，但是机器会有很大的局限性，比如：
统计结果容易受测试环境的影响：不同系统、处理器的机器测试结果可能出现很大的不同。
统计结果易受数据本身、数据规模影响：不同的数据、不同长度的数据都可能对测试结果产生巨大的影响。
所以我们需要不受外界环境影响的、大致的估算算法执行效率的方法。也就是我们引入复杂度的原因。
二、如何表示复杂度
如何表示算法的复杂度：具体来讲就是代码执行的时间、执行消耗的内存空间。
function fn(n) { let sum = 0; //1 unit-time let i = 0; //1 unit-time for (; i <= n; i++) { // n unit-time sum += i // n unit-time } return sum } 复制代码这些代码从CPU的角度来看，每段代码都是在读取和执行数据，尽管每次操作CPU的执行个数、执行时间都不同，我们粗略的将每次的执行时间都称为unit-time。 所以上述代码的执行时间就为(2n+2) * unit-time，用函数表达就是T(n) = (2n+2) * unit-time
我们也可以写成
T(n) = O(f(n))
其中：
n：表示数据规模的大小
f(n)：表示代码执行的次数总和
O：表示代码的执行时间T(n)与f(n)表达式成正比
当n很大时，比如n= 1000000，甚至更大，T(n) = O(f(n))就可以表示为T(n) = O(n)
这就是大O时间复杂度表示法。大O时间复杂度实际上并不具体表示代码真正的执行时间，而是表示代码执行时间随数据规模增长的变化趋势，所以，也叫作渐进时间复杂度（asymptotic time complexity），简称时间复杂度。
三、时间复杂度
当n越是趋于无限大的时候，T(n)受n的最高数量级的影响就越大，受其他常量、低阶、系数的关系就不那么大了。所以我们每次分析代码的时间复杂度的时候，仅仅关注代码的执行次数最多的的那段即可。
案例一
function fun1(n) { let sum = 0; for(i = 0; i <= n; i++) { sum += i; } return sum } 复制代码这里的时间复杂度主要看第三行的循环，时间复杂度为O(n)。
案例二
function fun2(n) { let sum = 0； for(i= 0; i <= n; i++) { // 循环1 sum += i; } for(i = 0; i <= n; i++) { // 循环2 for(j = 0; j <= n; j++) { sum += i * j; } } return sum } 复制代码这里循环1 的时间复杂度时O(n)，循环2的时间复杂度是O(n²)
案例三
function fun3(n) { let sum = 0; for(i = 0; i <= n; i++) { sum += fun(i); } return sum } 复制代码这里的时间复杂度是O(n * T(fun)) = O(n²)
案例四
let i = 1; while(i < n){ i *= 2; } 复制代码这里每次循环 i 都乘2，直至 i > n，那么执行过程就是2⁰，2¹，2²，2³ ······n；假设总共执行了x次，那么就是2x = n，时间复杂度就是O(log₂n)。
当算法中不存在循环语句、递归语句、即使有成千上万行的代码，其时间复杂度也是O(1)
四、空间复杂度
时间复杂度表示算法的执行时间与数据规模之间的增长关系，空间复杂度表示算法的存储空间与数据规模之间的增长关系。
function fun(n) { let a = []; for (let i = 0; i < n; i++) { a.push(i); } return a; } 复制代码这段代码我们能看出代码的执行空间为O(1 + n) = O(n)，也就是i及数组a占用的储存空间。
作者：小铃铛
链接：https://juejin.cn/post/7028176282521174029