跑分安卓第一！Redmi K60至尊版8月發布！盧偉冰：目標年度性能之王
8月5日消息，Redmi K60至尊版將于8月發布，在此前舉行的戰略發布會上，官方該機將搭載搭載天璣9200+處理器，安兔兔V10跑分超177萬分，是目前安卓陣營最高的分數
有網友評論，我也發明了一種排序算法，時間復制度為O(1)，稱為OD排序，基本思想如下：
今天我們就開始學習如何分析、統計算法的執行效率和資源消耗呢？請看本文一一道來。
數據結構和算法本生解決的就是「快」和「省」的問題，那就是如何讓代碼跑得快，還能節省存儲空間。
打造一臺法拉利，不僅跑得快還省油，擁有好的算法與數據結構，程序跑得快，還省內存并且長時間運行也不會出故障，就像跑車長時間運行車子也不會出現異常「車震」，同時還快。
所以趕緊上車，一起學習數據結構與算法，趕緊上車「穩穩」的學會如何檢測跑車到底快不快，省油不省油。
這里就要用到我們今天要講的內容：時間、空間復雜度分析。只要講到數據結構與算法，就一定離不開時間、空間復雜度分析。
復雜度分析是整個算法學習的精髓，只要掌握了它，數據結構和算法的內容基本上就掌握了一半。這就就像內功心法，上乘武功還需搭配牛逼心法。
只有學會了檢測標準才能在設計的時候心中按照標準來編寫打造我們的「法拉利」代碼。
可能會有些疑惑，我把代碼跑一遍，通過統計、監控，就能得到算法執行的時間和占用的內存大小。為什么還要做時間、空間復雜度分析呢？這種分析方法能比我實實在在跑一遍得到的數據更準確嗎？
這種屬于非要自己去嘗試，沒有根據合理方法預測我們要的就是像算命大師一樣預先知道。很多數據結構和算法書籍還給這種方法起了一個名字，叫事后統計法。但是，這種統計方法有非常大的局限性。
測試環境中硬件的不同會對測試結果有很大的影響。比如，我們拿同樣一段代碼，分別用 Intel Core i7 處理器和 Intel Core i3 處理器來運行，不用說，i7 處理器要比 i3 處理器執行的速度快很多。
就好像同一輛車放在深圳北環大道與我家農村小山溝跑是不一樣的。
后面我們會講排序算法，我們先拿它舉個例子。對同一個排序算法，待排序數據的有序度不一樣，排序的執行時間就會有很大的差別。
極端情況下，如果數據已經是有序的，那排序算法不需要做任何操作，執行時間就會非常短。除此之外，如果測試數據規模太小，測試結果可能無法真實地反應算法的性能。
比如，對于小規模的數據排序，插入排序可能反倒會比快速排序要快！
所以，我們需要一個不用具體的測試數據來測試，就可以粗略地估計算法的執行效率的方法。這就是我們今天要講的時間、空間復雜度分析方法。
算法的執行效率，粗略地講，就是算法代碼執行的時間。但是，如何在不運行代碼的情況下，用“肉眼”得到一段代碼的執行時間呢？就像檢測車子馬力與油耗似的。
求 1,2,3…n 的累加和。現在，一起估算一下這段代碼的執行時間。
int cal(int n) { int sum = 0; int i = 1; for (; i <= n; ++i) { sum = sum + i; } return sum; }從 CPU 的角度來看，這段代碼的每一行都執行著類似的操作：讀數據-運算-寫數據。盡管每行代碼對應的 CPU 執行的個數、執行的時間都不一樣，但是，我們這里只是粗略估計，所以可以假設每行代碼執行的時間都一樣，為 unit_time單位時間。
在這個假設的基礎之上，這段代碼的總執行時間是多少呢？
第 2、3 行代碼分別需要 1 個 unit_time 的執行時間，第 4、5 行都運行了 n 遍，所以需要 2n*unit_time 的執行時間，所以這段代碼總的執行時間就是 (2n+2)*unit_time。可以看出來，所有代碼的執行時間 T(n) 與每行代碼的執行次數成正比。
我們繼續分析下面這段代碼：
int cal(int n) { int sum = 0; int i = 1; int j = 1; for (; i <= n; ++i) { j = 1; for (; j <= n; ++j) { sum = sum + i * j; } } }我們依舊假設每個語句的執行時間是 unit_time。那這段代碼的總執行時間 T(n) 是多少呢？
第 2、3、4 行代碼，每行都需要 1 個 unit_time 的執行時間，第 5、6 行代碼循環執行了 n 遍，需要 2n * unit_time 的執行時間，第 7、8 行代碼循環執行了 n^2^遍，所以需要 2n^2^ * unit_time 的執行時間。所以，整段代碼總的執行時間 T(n) = (2n^2^+ 2n + 3)*unit_time。
盡管我們不知道 unit_time 的具體值，但是通過這兩段代碼執行時間的推導過程，我們可以得到一個非常重要的規律，那就是，==所有代碼的執行時間 T(n) 與每行代碼的執行次數 n 成正比==。
我們可以把這個規律總結成一個公式。注意，大 O 就要登場了！
其中
，我們已經講過了，它表示代碼執行的時間；n 表示數據規模的大小；
表示每行代碼執行的次數總和。因為這是一個公式，所以用
來表示。公式中的 O，表示代碼的執行時間 T(n) 與 f(n) 表達式成正比。
所以，第一個例子中的
，第二個例子中的 T(n) = O(2n^2^+2n+3)。這就是大 O 時間復雜度表示法。
大 O 時間復雜度實際上并不具體表示代碼真正的執行時間，而是表示代碼執行時間隨數據規模增長的變化趨勢，所以，也叫作漸進時間復雜度（asymptotic time complexity），簡稱時間復雜度。敲黑板了，表達的是變化趨勢，并不是真正的執行時間。
當 n 很大時，你可以把它想象成 100000、1000000。而公式中的==低階、常量、系數==三部分并不左右增長趨勢，所以都可以忽略。我們只需要記錄一個最大量級就可以了，如果用大 O 表示法表示剛講的那兩段代碼的時間復雜度，就可以記為：
前面介紹了大 O 時間復雜度的由來和表示方法。現在我們來看下，如何分析一段代碼的時間復雜度？有三個比較實用的方法可以分享。
大 O 這種復雜度表示方法只是表示一種變化趨勢。我們通常會忽略掉公式中的常量、低階、系數，只需要記錄一個最大階的量級就可以了。所以，我們在分析一個算法、一段代碼的時間復雜度的時候，也只關注循環執行次數最多的那一段代碼就可以了。擒賊先擒王就是這么回事。
這段核心代碼執行次數的 n 的量級，就是整段要分析代碼的時間復雜度。
int cal(int n) { int sum = 0; int i = 1; for (; i <= n; ++i) { sum = sum + i; } return sum; }其中第 2、3 行代碼都是常量級的執行時間，與 n 的大小無關，所以對于復雜度并沒有影響。
循環執行次數最多的是第 4、5 行代碼，所以這塊代碼要重點分析。前面我們也講過，這兩行代碼被執行了 n 次，所以總的時間復雜度就是 O(n)。
看如下代碼可以先試著分析一下，然后再往下看跟我的分析思路是否一樣。
int cal(int n) { int sum_1 = 0; int p = 1; for (; p < 100; ++p) { sum_1 = sum_1 + p; } int sum_2 = 0; int q = 1; for (; q < n; ++q) { sum_2 = sum_2 + q; } int sum_3 = 0; int i = 1; int j = 1; for (; i <= n; ++i) { j = 1; for (; j <= n; ++j) { sum_3 = sum_3 + i * j; } } return sum_1 + sum_2 + sum_3; }這個代碼分為三部分，分別是求 sum_1、sum_2、sum_3。我們可以分別分析每一部分的時間復雜度，然后把它們放到一塊兒，再取一個量級最大的作為整段代碼的復雜度。
綜合這三段代碼的時間復雜度，我們取其中最大的量級。所以，整段代碼的時間復雜度就為 O(n^2^)。也就是說：總的時間復雜度就等于量級最大的那段代碼的時間復雜度。那我們將這個規律抽象成公式就是：
如果 T1(n)=O(f(n))，T2(n)=O(g(n))；那么 T(n)=T1(n)+T2(n)=max(O(f(n)), O(g(n))) =O(max(f(n), g(n)))剛剛說了一個加法原則，這里說的乘法原則，以此類推，你也應該能「猜到」公式。這個是效率最差的
如果 T1(n)=O(f(n))，T2(n)=O(g(n))；那么 T(n)=T1(n)*T2(n)=O(f(n))*O(g(n))=O(f(n)*g(n))。
也就是說，假設 T1(n) = O(n)，T2(n) = O(n2)，則
。落實到具體的代碼上，我們可以把乘法法則看成是嵌套循環。
int cal(int n) { int ret = 0; int i = 1; for(x=1; i <= n; x++){ for(i = 1; i <= n; i++) { j = i; j++; } } }我們單獨看 cal() 函數。假設 5-8 行的 只是一個普通的操作，那第 4 行的時間復雜度就是，T1(n) = O(n)。但 5-8 函數本身不是一個簡單的操作，它的時間復雜度是 T2(n) = O(n)，所以，整個 cal() 函數的時間復雜度就是，
雖然代碼千差萬別，但是常見的復雜度量級并不多。老弟稍微總結了一下，這些復雜度量級幾乎涵蓋了今后可以接觸的所有代碼的復雜度量級。
劃重點了同學們。
對于剛羅列的復雜度量級，我們可以粗略地分為兩類，多項式量級和非多項式量級。其中，非多項式量級只有兩個：
和 O(n!)。
當數據規模 n 越來越大時，非多項式量級算法的執行時間會急劇增加，求解問題的執行時間會無限增長。所以，非多項式時間復雜度的算法其實是非常低效的算法。因此，關于 NP 時間復雜度我就不展開講了。
我們主要來看幾種常見的多項式時間復雜度。
首先我們必須明確一個概念，O(1) 只是常量級時間復雜度的一種表示方法，并不是指只執行了一行代碼。比如這段代碼，即便有 3 行，它的時間復雜度也是 O(1），而不是 O(3)。
int a = 1;int b = 2;int c = 3;我們的 HashMap get()、put() 其實就是 O(1) 時間復雜度。
只要代碼的執行時間不隨 n 的增大而增長，這樣代碼的時間復雜度我們都記作 O(1)。或者說，**一般情況下，只要算法中不存在循環語句、遞歸語句，即使有成千上萬行的代碼，其時間復雜度也是 Ο(1)**。
對數階時間復雜度非常常見，同時也是最難分析的一種時間復雜度。
i=1; while (i <= n) { i = i * 2; }根據我們前面講的復雜度分析方法，第三行代碼是循環執行次數最多的。所以，我們只要能計算出這行代碼被執行了多少次，就能知道整段代碼的時間復雜度。
從代碼中可以看出，變量 i 的值從 1 開始取，每循環一次就乘以 2。當大于 n 時，循環結束。還記得我們高中學過的等比數列嗎？實際上，變量 i 的取值就是一個等比數列。如果我把它一個一個列出來，就應該是這個樣子的：
所以，我們只要知道 x 值是多少，就知道這行代碼執行的次數了。通過 2^x^=n 求解 x 這個問題我們想高中應該就學過了，我就不多說了。x=log~2~n，所以，這段代碼的時間復雜度就是 O(log~2~n)。
我把代碼稍微改下，這段代碼的時間復雜度是多少？
i=1; while (i <= n) { i = i * 3; }很簡單就能看出來，這段代碼的時間復雜度為 O(log~3~n)。
實際上，不管是以 2 為底、以 3 為底，還是以 10 為底，我們可以把所有對數階的時間復雜度都記為 O(logn)。
為什么呢？
我們知道，對數之間是可以互相轉換的，log3n 就等于 log~3~2 _ log~2~n，所以 O(log~3~n) = O(C _ log~2~n)，其中 C=log~3~2 是一個常量。
基于我們前面的一個理論：**在采用大 O 標記復雜度的時候，可以忽略系數，即 O(Cf(n)) = O(f(n))**。
所以，O(log~2~n) 就等于 O(log~3~n)。因此，在對數階時間復雜度的表示方法里，我們忽略對數的“底”，統一表示為 O(logn)。
如果你理解了我前面講的 O(logn)，那 O(nlogn) 就很容易理解了。
還記得我們剛講的乘法法則嗎？如果一段代碼的時間復雜度是 O(logn)，我們循環執行 n 遍，時間復雜度就是 O(nlogn) 了。
而且，O(nlogn) 也是一種非常常見的算法時間復雜度。比如，歸并排序、快速排序的時間復雜度都是 O(nlogn)。
如下所示就是
, 內部 while 循環是 O(logn) ,被外層 for 循環包起來。所以 就是 O(nlogn)
for(m = 1; m < n; m++) { i = 1; while(i < n) { i = i * 2; }}我們再來講一種跟前面都不一樣的時間復雜度，代碼的復雜度由兩個數據的規模來決定。
int cal(int m, int n) { int sum_1 = 0; int i = 1; for (; i < m; ++i) { sum_1 = sum_1 + i; } int sum_2 = 0; int j = 1; for (; j < n; ++j) { sum_2 = sum_2 + j; } return sum_1 + sum_2;}從代碼中可以看出，m 和 n 是表示兩個數據規模。我們無法事先評估 m 和 n 誰的量級大，所以我們在表示復雜度的時候，就不能簡單地利用加法法則，省略掉其中一個。所以，上面代碼的時間復雜度就是 O(m+n)。
針對這種情況，原來的加法法則就不正確了，我們需要將加法規則改為：T1(m) + T2(n) = O(f(m) + g(n))。但是乘法法則繼續有效：T1(m)_T2(n) = O(f(m) _ f(n))。
**4.線性階 O(n) **
看這段代碼會執行多少次呢？
for(i=1; i<=n; i++) { j = i; j++;}第 1 行會執行 n 次，第 2 行和第 3 行會分別執行 n 次，總的執行時間也就是 3n + 1 次，那它的時間復雜度表示是 O(3n + 1) 嗎？No !
還是那句話：“大 O 符號表示法并不是用于來真實代表算法的執行時間的，它是用來表示代碼執行時間的增長變化趨勢的”。
所以它的時間復雜度其實是 O(n);
for(x=1; i <= n; x++){ for(i = 1; i <= n; i++) { j = i; j++; }}把 O(n) 的代碼再嵌套循環一遍，它的時間復雜度就是 O(n2) 了。
參考上面的 O(n2) 去理解就好了，O(n3)相當于三層 n 循環，其它的類似。
理解了前面講的內容，空間復雜度分析方法學起來就非常簡單了。
時間復雜度的全稱是漸進時間復雜度，表示算法的執行時間與數據規模之間的增長關系。類比一下，空間復雜度全稱就是漸進空間復雜度，表示算法的存儲空間與數據規模之間的增長關系。
void print(int n) { int i = 0; int[] a = new int[n]; for (i; i <n; ++i) { a[i] = i * i; }}跟時間復雜度分析一樣，我們可以看到，第 2 行代碼中，我們申請了一個空間存儲變量 i，但是它是常量階的，跟數據規模 n 沒有關系，所以我們可以忽略。
第 3 行申請了一個大小為 n 的 int 類型數組，除此之外，剩下的代碼都沒有占用更多的空間，所以整段代碼的空間復雜度就是 O(n)。
打個不恰當的比喻，就像我們的手機現在工藝越來越好，手機也越來越薄。占用體積越來越小。也就是用更好的模具設計放置零件，而模具就像是空間復雜度更小的體積容納更多的原件。
我們常見的空間復雜度就是 O(1)、O(n)、O(n2 )，像 O(logn)、O(nlogn) 這樣的對數階復雜度平時都用不到。而且，空間復雜度分析比時間復雜度分析要簡單很多。所以，對于空間復雜度，掌握剛我說的這些內容已經足夠了。
如果算法執行所需要的臨時空間不隨著某個變量 n 的大小而變化，即此算法空間復雜度為一個常量，可表示為 O(1)。
int i = 1;int j = 2;++i;j++;int m = i + j;代碼中的 i、j、m 所分配的空間都不隨著處理數據量變化，因此它的空間復雜度 S(n) = O(1)。
int[] m = new int[n]for(i=1; i <= n; ++i) { j = i; j++;}這段代碼中，第一行 new 了一個數組出來，這個數據占用的大小為 n，后面雖然有循環，但沒有再分配新的空間，因此，這段代碼的空間復雜度主要看第一行即可，即 S(n) = O(n)。
基礎復雜度分析的知識到此就講完了，我們來總結一下。
復雜度也叫漸進復雜度，包括時間復雜度和空間復雜度，用來分析算法執行效率與數據規模之間的增長關系，可以粗略地表示，越高階復雜度的算法，執行效率越低。
常見的復雜度并不多，從低階到高階有：O(1)、O(logn)、O(n)、O(nlogn)、O(n^2^ )。等學完整個專欄之后，就會發現幾乎所有的數據結構和算法的復雜度都跑不出這幾個。
有人說，我們項目之前都會進行性能測試，再做代碼的時間復雜度、空間復雜度分析，是不是多此一舉呢？而且，每段代碼都分析一下時間復雜度、空間復雜度，是不是很浪費時間呢？你怎么看待這個問題呢？
本文鏈接：http://www.tebozhan.com/showinfo-26-85371-0.html算法必備知識：時間復雜度與空間復雜度的計算
聲明：本網頁內容旨在傳播知識，若有侵權等問題請及時與本網聯系，我們將在第一時間刪除處理。郵件：2376512515@qq.com
上一篇： 英特爾與美國國防部深化合作，采用 18A 工藝生產芯片
下一篇： C#中編寫系統操作日志的實踐
Copyright ? 2016-2023 天津谷騏科技有限公司 版權所有 sitemap.xml
違法及侵權請聯系：2376512515@qq.com 津ICP備18001702號
津公網安備 12010102000574號