算法效率分析可以分为时间和空间两个方面，分别为时间复杂度与空间复杂度。

时间复杂度

进行算法分析时，算法的基本语句(关键语句)的执行次数与问题规模n的关系表示为T(n)。

T(n)由于同一问题本身的差异，如排序中输入数据序列的有序性不确定，T(n)会有最好情况Tmin(n)、平均情况Tavg(n)与最坏情况Tmax(n)，实践表明，最坏情况是最有实际价值的。

实际问题中，n趋于极限时，我们关心的是T(n)的变化趋势或者说其量级（Order）。

应用数学中的渐近分析可以用来描述函数的渐近行为（变化趋势）。

算法的渐近分析就是估计当求解问题的规模 n 逐步增大时，时间开销 T(n) 的增长趋势。

相关的渐近符号有Θ、O、Ω、o、ω。分别读作：Theta，Omicron，Omega，omicron，omega。

下面是数学上的定义

O记号

image.png

设 f(n) 和 g(n) 是定义域 n 为自然数集合的函数，如果存在正的常数c和自然数n0，使得当n≥n0 时有f(n)≤cg(n)，则称函数f(n)当n充分大时上有界，且g(n)是它的一个上界，记为f(n) = O(g(n))

f(n)=O（g（n））并不是数学上严格的等于的概念，也可以为fn ∈ O（g（n）），O表示一个函数的集合。

Ω记号

image.png

如果存在正的常数c和自然数n0，使得当n≥n0时有f(n)≥cg(n), 则称函数fn当n充分大时下有界，且gn是fn的一个下界，记为fn=Ω(g(n))

Θ记号

image.png

存在正的常数c1和c2和自然数n0，使得当n≥n0时有c2g(n)≤f(n)≤c1g(n)，则当n充分大时，gn的常数倍既是上界也是下界，记为fn=Θ(g(n))。

o与ω

另外两个渐进符号 ο 和 ω 一般很少使用，指不那么紧密的上下界。

记号 含义 通俗理解
Θ 紧确界 相当于”=”
O 上界 相当于”<=”
ο 非紧的上界 相当于”<”
Ω 下界 相当于”>=”
ω 非紧的下界 相当于”>”
我们一般用 O 渐进上界来评估一个算法的时间复杂度，表示逼近的最坏情况。其他渐进符合基本不怎么使用。

通过例子理解

假设算法 A 的运行时间表达式：
T(n)= 5 * n^3 + 4 * n^2
求渐近上界：

f(n) = O(n^3)，g(n) = n^3
f(n) = O(n^4)，g(n) = n^4

两个 g(n) 都是上界，因为令 c = 5 时都存在：0 <= f(n) <= c * g(n))。

我们会取乘方更小的那个，因为这个界更逼近 f(n) 本身，所以我们一般说 f(n) = O(n^3)，算法的复杂度为大欧 n 的三次方，表示最坏情况。

求渐近下界：
同理，渐近下界 Ω 刚好与渐近上界相反，表示最好情况。

f(n) = Ω(n^3)，g(n) = n^3
f(n) = Ω(n^2)，g(n) = n^2

我们准确评估的时候，要取乘方更大的那个，因为这个界更逼近 f(n) 本身，所以我们一般说 f(n) = Ω(n^3)，算法的复杂度为大欧米伽 n 的三次方，表示最好情况。

我们发现当 f(n) = Ω(n^3) = O(n^3) 时，其实 f(n) = Θ(n^3)。

求o与ω

评估的时候，不那么准确去评估，在评估最坏情况的时候使劲地往坏了评估，评估最好情况则使劲往好的评估，但是它不能刚刚好，比如上面的结果：

f(n) = O(n^3)，g(n) = n^3
f(n) = O(n^4)，g(n) = n^4
f(n) = Ω(n^3)，g(n) = n^3
f(n) = Ω(n^2)，g(n) = n^2

// 我们可以说：
f(n) = ο(n^4)，g(n) = n^4  往高阶的评估，不能同阶
f(n) = ω(n^2)，g(n) = n^2  往低阶的评估，不能同阶

常见时间复杂度量级 & 排序算法的时间复杂度

常见时间复杂度量级

image.png

从高阶到低阶

image.png

排序算法的时间复杂度

排序算法 平均时间复杂度 最坏时间复杂度 最好时间复杂度 空间复杂度 稳定性
冒泡排序 O(n²) O(n²) O(n) O(1) 稳定
直接选择排序 O(n²) O(n²) O(n) O(1) 不稳定
直接插入排序 O(n²) O(n²) O(n) O(1) 稳定
快速排序 O(nlogn) O(n²) O(nlogn) O(nlogn) 不稳定
堆排序 O(nlogn) O(nlogn) O(nlogn) O(1) 不稳定
希尔排序 O(nlogn) O(ns) O(n) O(1) 不稳定
归并排序 O(nlogn) O(nlogn) O(nlogn) O(n) 稳定
计数排序 O(n+k) O(n+k) O(n+k) O(n+k) 稳定
基数排序 O(NM) O(NM) O(N*M) O(M) 稳定

空间复杂度
空间复杂度和时间复杂度的情况其实类似，但是它更加的简单。用最简单的方式来分析即可。主要有两个原则：

如果你的代码中开了数组，那么数组的长度基本上就是你的空间复杂度。比如你开了一个一维的数组，那么你的空间复杂度就是O(n)，如果开了一个二维的数组，数组长度是n^{2，那么空间复杂度基本上就是n}2

如果是有递归的话，那么它递归最深的深度，就是你空间复杂度的最大值。如果你的程序里边递归中又开了数组，那么空间复杂度就是两者的最大值

O(1)
function  f1(){
    const test =10;
    console.log(test);
    console.log(1);
    console.log(2);
    console.log(3)
}

O(n)
function f1(n) {
    let arr = [];
    for (let i = 0; i < n; i++) {
        console.log(4 * i);
        arr.push(i);
    }
    return arr;
}