最近在面试时遇到了关于复杂度的问题，才发现自己也未曾涉及过这方面的知识。对于代码的质量，很多时候凭借感觉，或者是能跑就行，感觉这个态度并不能让自己精益求精。
对于同一个问题，我们可能有很多种解决方法，现实世界中我们无法精准的预估这些方法的“代价”，但其实 “所有命运赠送的礼物，早已在暗中标好了价格”。在代码的世界中我们可以衡量这种“价格”。
在 leetcode 中，算法执行后会得出本次执行的 时间 和 消耗内存，这就是我们需要关注的两个维度：时间 和 空间。我们在书写的时候可能无法得知准确的执行时间和需要的内存空间，另外这两个值也受运行环境的影响，那我们就需要一个相对的标准，来衡量我们的代码是否能有又好又快的未来。
时间复杂度
时间复杂度表示当前算法所消耗的时间，我们采用 渐进时间复杂度
T(n) = O(f(n))来表示 ，其中 f(n) 表示每行代码执行次数之和，O表示一个正比例关系。假设每一行代码的执行时间都是一致的，那么每一行代码的执行时间看作一个单位 1。对于上面的代码，这个表达式为
T(n) = O(2n+1) ，第一行的代码只执行一次，我们看作 1。循环中的代码有两行执行 n 次，我们看作 2n。当 n 足够大时，我们可以忽略这个 1 ，即 T(n) = O(2n)。那么这段代码的耗时就是和 n 的变化成正比的。那么我们可以将这个表达简化为 T(n) = O(n)。常见复杂度
常见的时间复杂度量级有：
常数阶 O(1)
无论代码有多少行，只要代码内无循环结构，那么复杂度就是
O(1) 。对数阶 O(logN)
对于上面的代码，我们每一次执行后都将 i 进行加倍，那么 i 就不断地向 n 逼近。如果代码执行 x 次后循环结束，即
2^x = n，那么 x = log2^n。线性阶 O(n)
代码执行 n 次后结束，消耗的时间随着 n 的变化而变化，可简单看作一次循环。
线性对数阶 O(nlogN)
将复杂度为对数阶的代码执行 N 次，可以看作将对数阶的代码放在循环中。
平方阶 O(n²)，立方阶 O(n³)，K次方阶 O(n^k)
看简单看作 2，3，K 层循环嵌套。
指数阶 O(2^n)
随着数据规模的增长，算法的执行时间暴增。
上面从上至下依次的时间复杂度越来越大，执行的效率越来越低。
最好时间复杂度和最坏时间复杂度
最好时间复杂度 是指代码在最理想的情况下执行的时间复杂度，最坏时间复杂度 是指代码在最糟糕的情况下执行的时间复杂度。
比如数组的
find() 方法，在最理想的情况下第一项就匹配结束循环，这时的时间复杂度为 O(1)，但在最糟糕的情况下，在最后一项才找到，这时的时间复杂度为 O(n)。空间复杂度
空间复杂度用来衡量代码在运行的过程中占用的临时空间，反应代码分配空间随数据量变化的趋势，我们用
S(n) = O（f(n)) 表示。
常见的空间复杂度量级有：O(1)
算法执行的临时空间不随某个变量 n 的大小而变化。不新建数组和循环体内没有变量命名的情况，可以表示为
S(n) = O(1)，简写为 O(1)。O(n)
算法执行的临时空间和某个变量 n 的大小的大小而变化。
创建的数组分配空间和 n 的大小有关，
S(n) = O(n)，简写为 O(n)。数组常见操作的时间复杂度
pop()和push()等在数组尾部的操作的时间复杂度为O(1)。
forEach()，map()，shift()，unshift()，ervery()等需要遍历或者在数组头部操作的方法的时间复杂度为O(n)。
splice()，concat()，find()，findeIndex()，indexOf()，some()，every()等方法的时间时间复杂度为O(n)，最优复杂度为O(1)，例如splice()操作数组尾部，find()第一项就找到。
sort()的时间复杂度为O(nlogn)。