均摊时间复杂度（amortized time complexity）: 在代码执行的所有复杂度情况中绝大部分是低级别的复杂度，个别情况是高级别复杂度且发生具有时序关系时，可以将个别高级别复杂度均摊到低级别复杂度上。基本上均摊结果就等于低级别复杂度。
举例说明：
// n 表示数组 array 的长度 function find(array, n, x) { let i = 0; let pos = -1; for (; i < n; ++i) { if (array[i] == x) { pos = i; break; } } return pos; }find 函数实现的功能是在一个数组中找到值等于 x 的项，并返回索引值，如果没找到就返回 -1 。
最好情况时间复杂度，最坏情况时间复杂度
如果数组中第一个值就等于 x，那么时间复杂度为 O(1)，如果数组中不存在变量 x，那我们就需要把整个数组都遍历一遍，时间复杂度就成了 O(n)。所以，不同的情况下，这段代码的时间复杂度是不一样的。
所以上面代码的 最好情况时间复杂度为 O(1)，最坏情况时间复杂度为 O(n)。
平均情况时间复杂度
如何分析平均时间复杂度 ？代码在不同情况下复杂度出现量级差别，则用代码所有可能情况下执行次数的加权平均值表示。
要查找的变量 x 在数组中的位置，有 n+1 种情况：在数组的 0～n-1 位置中和不在数组中。我们把每种情况下，查找需要遍历的元素个数累加起来，然后再除以 n+1，就可以得到需要遍历的元素个数的平均值，即：
省略掉系数、低阶、常量，所以，这个公式简化之后，得到的平均时间复杂度就是 O(n)。
我们知道，要查找的变量 x，要么在数组里，要么就不在数组里。这两种情况对应的概率统计起来很麻烦，我们假设在数组中与不在数组中的概率都为 1/2。另外，要查找的数据出现在 0～n-1 这 n 个位置的概率也是一样的，为 1/n。所以，根据概率乘法法则，要查找的数据出现在 0～n-1 中任意位置的概率就是 1/(2n)。
因此，前面的推导过程中存在的最大问题就是，没有将各种情况发生的概率考虑进去。如果我们把每种情况发生的概率也考虑进去，那平均时间复杂度的计算过程就变成了这样：
这个值就是概率论中的 加权平均值，也叫 期望值，所以平均时间复杂度的全称应该叫 加权平均时间复杂度 或者 期望时间复杂度。
所以，根据上面结论推导出，得到的 平均时间复杂度 仍然是 O(n)。
均摊时间复杂度
均摊时间复杂度就是一种特殊的平均时间复杂度 (应用场景非常特殊，非常有限，这里不说)。
3.6 时间复杂度总结常用的时间复杂度所耗费的时间从小到大依次是：
O(1) < O(logn) < (n) < O(nlogn) < O(n2) < O(n3) < O(2n) < O(n!) < O(nn)
常见的时间复杂度：
时间复杂度的全称是 渐进时间复杂度，表示 算法的执行时间与数据规模之间的增长关系 。
类比一下，空间复杂度全称就是 渐进空间复杂度（asymptotic space complexity），表示 算法的存储空间与数据规模之间的增长关系 。
定义：算法的空间复杂度通过计算算法所需的存储空间实现，算法的空间复杂度的计算公式记作：S(n) = O(f(n))，其中，n 为问题的规模，f(n) 为语句关于 n 所占存储空间的函数。
function print(n) { const newArr = []; // 第 2 行 newArr.length = n; // 第 3 行 for (let i = 0; i <n; ++i) { newArr[i] = i * i; } for (let j = n-1; j >= 0; --j) { console.log(newArr[i]) } }