算法效率分析可以分為時間和空間兩個方面恶迈，分別為時間復(fù)雜度與空間復(fù)雜度款票。

時間復(fù)雜度

進行算法分析時踏幻，算法的基本語句(關(guān)鍵語句)的執(zhí)行次數(shù)與問題規(guī)模n的關(guān)系表示為T(n)枷颊。

T(n)由于同一問題本身的差異，如排序中輸入數(shù)據(jù)序列的有序性不確定该面，T(n)會有最好情況Tmin(n)偷卧、平均情況Tavg(n)與最壞情況Tmax(n)，實踐表明吆倦，最壞情況是最有實際價值的。

實際問題中坐求，n趨于極限時蚕泽，我們關(guān)心的是T(n)的變化趨勢或者說其量級（Order）。

應(yīng)用數(shù)學中的漸近分析可以用來描述函數(shù)的漸近行為（變化趨勢）桥嗤。

算法的漸近分析就是估計當求解問題的規(guī)模 n 逐步增大時须妻，時間開銷 T(n) 的增長趨勢。

相關(guān)的漸近符號有Θ泛领、O荒吏、Ω、o渊鞋、ω绰更。分別讀作：Theta瞧挤，Omicron，Omega儡湾，omicron特恬，omega。

下面是數(shù)學上的定義

O記號

image.png

設(shè) f(n) 和 g(n) 是定義域 n 為自然數(shù)集合的函數(shù)徐钠，如果存在正的常數(shù)c和自然數(shù)n0癌刽，使得當n≥n0 時有f(n)≤cg(n)，則稱函數(shù)f(n)當n充分大時上有界尝丐，且g(n)是它的一個上界显拜，記為f(n) = O(g(n))

f(n)=O（g（n））并不是數(shù)學上嚴格的等于的概念，也可以為fn ∈ O（g（n））爹袁，O表示一個函數(shù)的集合远荠。

Ω記號

image.png

如果存在正的常數(shù)c和自然數(shù)n0，使得當n≥n0時有f(n)≥cg(n), 則稱函數(shù)fn當n充分大時下有界呢簸，且gn是fn的一個下界矮台，記為fn=Ω(g(n))

Θ記號

image.png

存在正的常數(shù)c1和c2和自然數(shù)n0，使得當n≥n0時有c2g(n)≤f(n)≤c1g(n)根时，則當n充分大時瘦赫，gn的常數(shù)倍既是上界也是下界，記為fn=Θ(g(n))蛤迎。

o與ω

另外兩個漸進符號 ο 和 ω 一般很少使用确虱，指不那么緊密的上下界。

記號 含義 通俗理解
Θ 緊確界 相當于”=”
O 上界 相當于”<=”
ο 非緊的上界 相當于”<”
Ω 下界 相當于”>=”
ω 非緊的下界 相當于”>”
我們一般用 O 漸進上界來評估一個算法的時間復(fù)雜度替裆，表示逼近的最壞情況校辩。其他漸進符合基本不怎么使用。

通過例子理解

假設(shè)算法 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)庭砍，算法的復(fù)雜度為大歐 n 的三次方场晶，表示最壞情況。

求漸近下界：
同理怠缸，漸近下界 Ω 剛好與漸近上界相反诗轻，表示最好情況。

f(n) = Ω(n^3)揭北，g(n) = n^3
f(n) = Ω(n^2)扳炬，g(n) = n^2

我們準確評估的時候吏颖，要取乘方更大的那個，因為這個界更逼近 f(n) 本身鞠柄，所以我們一般說 f(n) = Ω(n^3)侦高，算法的復(fù)雜度為大歐米伽 n 的三次方，表示最好情況厌杜。

我們發(fā)現(xiàn)當 f(n) = Ω(n^3) = O(n^3) 時奉呛，其實 f(n) = Θ(n^3)。

求o與ω

評估的時候夯尽，不那么準確去評估瞧壮，在評估最壞情況的時候使勁地往壞了評估，評估最好情況則使勁往好的評估匙握，但是它不能剛剛好咆槽，比如上面的結(jié)果：

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  往低階的評估蛔琅，不能同階

常見時間復(fù)雜度量級 & 排序算法的時間復(fù)雜度

常見時間復(fù)雜度量級

image.png

從高階到低階

image.png

排序算法的時間復(fù)雜度

排序算法 平均時間復(fù)雜度 最壞時間復(fù)雜度 最好時間復(fù)雜度 空間復(fù)雜度 穩(wěn)定性
冒泡排序 O(n2) O(n2) O(n) O(1) 穩(wěn)定
直接選擇排序 O(n2) O(n2) O(n) O(1) 不穩(wěn)定
直接插入排序 O(n2) O(n2) O(n) O(1) 穩(wěn)定
快速排序 O(nlogn) O(n2) O(nlogn) O(nlogn) 不穩(wěn)定
堆排序 O(nlogn) O(nlogn) O(nlogn) O(1) 不穩(wěn)定
希爾排序 O(nlogn) O(ns) O(n) O(1) 不穩(wěn)定
歸并排序 O(nlogn) O(nlogn) O(nlogn) O(n) 穩(wěn)定
計數(shù)排序 O(n+k) O(n+k) O(n+k) O(n+k) 穩(wěn)定
基數(shù)排序 O(NM) O(NM) O(N*M) O(M) 穩(wěn)定

空間復(fù)雜度
空間復(fù)雜度和時間復(fù)雜度的情況其實類似胎许，但是它更加的簡單。用最簡單的方式來分析即可罗售。主要有兩個原則：

如果你的代碼中開了數(shù)組辜窑，那么數(shù)組的長度基本上就是你的空間復(fù)雜度。比如你開了一個一維的數(shù)組寨躁，那么你的空間復(fù)雜度就是O(n)穆碎，如果開了一個二維的數(shù)組，數(shù)組長度是n^{2职恳，那么空間復(fù)雜度基本上就是n}2

如果是有遞歸的話惨远，那么它遞歸最深的深度，就是你空間復(fù)雜度的最大值话肖。如果你的程序里邊遞歸中又開了數(shù)組，那么空間復(fù)雜度就是兩者的最大值

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;
}