學數據結構和算法的目的 =>?實現程序的高速運行，那么必然要了解復雜度。

復雜度分為兩個維度：時間、空間。在開發過程中，我們希望時間和內存消耗都越少越好，但很多時候無法做到兼顧，需要在時間和空間之間做出取舍已達到最佳狀態。

對復雜度的計算一般采用事前分析估算的方法，即大O表示法。

接下來讓我們進入復雜度的學習！

大O表示法——概念

---

由保羅·巴赫曼在《解析數論》中首先引入。它描述的是一個函數數量級的漸進上界，即算法最壞的情況。

某個算法的復雜度達到了這個問題復雜度的下界，即為最佳算法。

比如：從大小為100的存放數字的數組中找到10，我們需要從頭到尾遍歷，那么這個是時間復雜度就為?Ο(n)，（這里n=100，下面講解為何為Ο(n)）。若10不是數組最后一項，我們在<100次的時候就找到 ，可跳出循環，所以，大O表示法描述的是最壞的情況。

說明：1. 決定算法復雜度的，是執行次數最多的語句；

? ? ? ? ? ?2. 復雜度的得出，忽略了常量，低次冪和最高次冪的系數；

? ? ? ? ? ?3. 加法法則：總復雜度量級最大的那段代碼的時間復雜度；

? ? ? ? ? ?3. 乘法法則：嵌套代碼的復雜度等于內外代碼復雜度的乘積。

大O表示法——四種常用的時間復雜度

---

度量一個程序片段的執行時間?

度量一個程序的執行時間通常有兩種方法

• 事后統計的方法

• 事前分析估算的方法? =>?O?

Ο(1)＜Ο(log2(n))＜Ο(n)＜Ο(n^2)＜Ο(n^3)＜…＜Ο(2^n)?

我們可以用 console.time(''mark)? console.timeEnd(''mark) 來查看執行時間

1. Ο(1)：（常數階）如果算法的執行時間不隨著問題規模n的增加而增長，即使算法中有上千條語句，其執行時間也不過是一個較大的常數；

let a = 1; let b = 2; let temp = a;a = b; b = temp;

?2. Ο(logn)：（對數階）（以2為底n的對數）當數據增大 n 倍時，耗時增大 logn 倍（比如，當數據增大 256 倍時，耗時只增大 8 倍）；

例子：二分查找就是 O(logn)的算法，每找一次排除一半的可能。

let i = 1;while(i <= n) {i *= 2; // 每次循環，i變大2倍，即排除一半可能 }

3. Ο(n)：（線性階）數據量的增大幾倍，耗時也增大幾倍；

for(i = 1; i <= n; i++) {... }

4.? Ο(n^2)：（平方階）數據量增大 n 倍時，耗時增大 n 的平方倍；

for(i = 1; i <= n; i++) {for(j = 1; j <= n; j++) {...} }

?

本文章持續完善中......

總結

以上是生活随笔為你收集整理的大O表示法和时间复杂度的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。