既然需要粗略地估计算法的执行效率，那么得用一种方式来表示，而这种表示方式就是大 O 表示法。那么所谓的算法执行效率是用什么来衡量？通常用资源，例如 CPU（时间）占用、内存占用、硬盘占用和网络占用。当我们用大 O 表示法的时候，一般考虑的是 CPU（时间）占用。
下面会通过例子来理解大 O 表示法的规则：
function cal(n) { let sum = 0; for (let i = 0; i < n; i++) { sum = sum + i; } return sum;}
假设每段代码执行的时间都是一样，为 unit time，在这个假设的基础之上，来分析上面这段代码总执行时间是多少。第二行代码需要一个 unit time 的执行时间。第三、四行需要 n 个 unit time 的执行时间。可以看出，所有代码的执行时间跟执行次数成正比，总时间为 
个 unit time。
以这个思路，继续分析下面这段代码：
function cal(n) {
let sum = 0;
for (let i = 0; i < n; i++) {
for (let j = 0; j < n; j++) {
sum = sum + i * j;
}
}
}
第二行代码的执行时间是 1 个 unit time。第三行执行了 n 次，执行时间为 n 个 unit time。第四、第五行执行了 
次，执行时间为 
个 unit time。代码的总执行时间为 
个 unit time。
经过上面两个例子，尽管不知道 unit time 的具体时间，但是我们知道代码的执行时间与执行次数成正比。这个规律可以总结为一个公式：
%3DO(f(n))%0A#card=math&code=T%28n%29%3DO%28f%28n%29%29%0A&id=S1Bt7)
其中 #card=math&code=T%28n%29&id=SAEZG) 表示代码的执行时间，
#card=math&code=f%28n%29&id=DDcwN) 表示代码执行的次数总和，
表示代码的执行时间 #card=math&code=T%28n%29&id=wddlL) 与 #card=math&code=f%28n%29&id=aWMvO) 表达式成正比。
因此第一个例子可以表示为 %3DO(2n%2B1)#card=math&code=T%28n%29%3DO%282n%2B1%29&id=oJt2K)，第二个例子可以表示为 %3DO(2n%5E2%2Bn%2B1)#card=math&code=T%28n%29%3DO%282n%5E2%2Bn%2B1%29&id=LM5zp)。大 O 时间复杂度实际上并不具体表示代码真正的执行时间，而是表示代码执行时间随数据规模增长的变化趋势，所以，也叫作渐进时间复杂度（asymptotic time complexity），简称时间复杂度。
当 n 很大时，你可以把它想象成 10000、100000。而公式中的低阶、常量、系数三部分并不左右增长趋势，所以都可以忽略。我们只需要记录一个最大量级就可以了，如果用大 O 表示法表示刚讲的那两段代码的时间复杂度，就可以记为：%3DO(n)#card=math&code=T%28n%29%3DO%28n%29&id=vqT5K)； %3DO(n%5E2)#card=math&code=T%28n%29%3DO%28n%5E2%29&id=Z0jfI)。
时间复杂度分析
时间复杂度表示代码执行时间随数据规模增长的变化趋势。常见的时间复杂度如下：
- 常量阶：
#card=math&code=O%281%29&id=jWZT9) - 对数阶：
#card=math&code=O%28logn%29&id=KMT2P) - 线性阶：
#card=math&code=O%28n%29&id=kSk5H) - 线性对数阶：
#card=math&code=O%28nlogn%29&id=hPvSH) - 次方阶：
#card=math&code=O%28n%5E2%29&id=bYMoh)、
#card=math&code=O%28n%5E3%29&id=UC7ul) … 
#card=math&code=O%28n%5Ek%29&id=LfZoc) - 指数阶：
#card=math&code=O%282%5En%29&id=Wus2G) - 阶乘阶：
#card=math&code=O%28n%21%29&id=nemMO)
对于刚罗列的复杂度量级，我们可以粗略地分为两类，多项式量级和非多项式量级。其中，非多项式量级只有两个：#card=math&code=O%282%5En%29&id=hQNL9) 和 #card=math&code=O%28n%21%29&id=CX2px)。我们把时间复杂度为非多项式量级的算法问题叫作 NP（Non-Deterministic Polynomial，非确定多项式）问题。当数据规模 n 越来越大时，非多项式量级算法的执行时间会急剧增加，求解问题的执行时间会无限增长。所以，非多项式时间复杂度的算法其实是非常低效的算法。因此 NP 的时间复杂度就不展开讲了。
如果想更加直观地查看不同复杂度随规模的增长运行时间的变化趋势，可以查阅 Big-O Cheat Sheet 这个网站。这个网站通过图表直观地给出不同时间复杂度运行时间随规模增长的变化趋势，并且还通过表格的方式，列出不同数据结构与排序算法的时间复杂度。
O(logn)、O(nlogn)
对数阶时间复杂度非常常见，同时也是最难分析的一种时间复杂度。下面举一个例子：
let i = 1;
while (i <= n) {
i = i * 2;
}
实际上 i 的取值就是一个等比数列，当要求执行次数 x 的时候，其实就是解 
，得到 
，因此时间复杂度为 
#card=math&code=O%28log_2%20n%29&id=vWbno)。
如果上面的例子第三行代码变为 i = i * 3，那么时间复杂度 
#card=math&code=O%28log_3%20n%29&id=bwxqn)。由于 
可以写成 
的形式，又由于在采用大 
表示复杂度的时候可以忽略系数，所以 #card=math&code=O%28log_2%20n%29&id=MCWB3) 就等于 #card=math&code=O%28log_3%20n%29&id=xrZk4)。正式因为这个原因，在使用大 
表示对数阶时间复杂度的时候，统一表示为 
#card=math&code=O%28log_n%29&id=DrDas)。
理解了 #card=math&code=O%28log_n%29&id=zMj9R)，那么 
#card=math&code=O%28nlog_n%29&id=QTMKk) 就容易理解了，其实就是 #card=math&code=O%28log_n%29&id=MCjQz) 复杂度的代码，循环执行了 n 次，因此时间复杂度就是 $O(nlog_n)。
O(m+n)、O(m*n)
这种复杂度是由两个数据的规模来决定的，举个例子：
function cal(m, n) {
let sum1 = 0;
for (let i = 0; i < m; i++) {
sum1 = sum1 + i;
}
let sum2 = 0;
for (let j = 0; j < n; j++) {
sum2 = sum2 + i;
}
}
m 和 n 表示两个数据规模，我们无法实现评估 m 和 n 谁的量级大，所以在表示复杂度的时候，就不能简单地忽略其中一个数据规模的时间复杂度，因此上面的代码的时间复杂度就是 
#card=math&code=O%28m%2Bn%29&id=lpniz)。
空间复杂度分析
时间复杂度的全称是渐进时间复杂度，表示算法的执行时间与数据规模之间的增长关系。而空间复杂度全称就是渐进空间复杂度，表示算法的存储空间与数据规模之间的增长关系。
function foo(n) {
const bar = [];
for (let i = 0; i < n; i++) {
bar.push(i);
}
}
除了第二行的代码跟数据规模 n 有关系，其它代码都与数据规模 n 没有关系，因此可以忽略。第二行的代码数据占了 n 个空间，因此整段代码的空间复杂度就是 #card=math&code=O%28n%29&id=J2ZPm)。
常见的空间复杂度就是 #card=math&code=O%281%29&id=osKc7)、#card=math&code=O%28n%29&id=QZHFf)、#card=math&code=O%28n%5E2%29&id=Yujda)，像 
#card=math&code=O%28log%20n%29&id=OCrCY)、#card=math&code=O%28nlogn%29&id=KuZN7) 这种对数阶复杂度平时都用不到。
