複雜度分析的套路及常見的複雜度

2020-09-19 彤哥讀源碼

前言

你好，我是彤哥，一個每天爬二十六層樓還不忘讀源碼的硬核男人。

上一節，我們一起學習了表示複雜度的幾個符號，我們說，通常使用大O來表示算法的複雜度，不僅合理，而且書寫方便。

那麼，使用大O表示法評估算法的複雜度有沒有什麼套路呢？以及常見的複雜度有哪些呢？

本節，我們就來解決這兩個問題。

前情回顧

在正式講解套路之前，我們先回憶一下前面幾節講到的內容。

在第2節，我們學習了漸近分析法，將算法的複雜度與輸入規模掛鈎，隨著輸入規模的增大，算法執行的時間將呈現一種什麼樣的趨勢，將這個趨勢用函數表示，再去除低階項和常數項，就得到了算法的時間複雜度。

在第3節，我們分別從最壞、平均、最好三種情況來分析了算法的複雜度，得出結論，一般使用最壞情況來評估算法的複雜度。

在第4節，我們通過動態數組的插入元素及經典快速排序的時間複雜度，解釋了有的時候不能使用最壞情況來評估算法的複雜度。

在第5節，我們從讀音、數學、通俗理解三個方面分析了各種表示算法複雜度的符號，得出結論還是使用大O比較香，大O代表了算法的上界，它與前面講到的最壞情況往往是對應的。

所以，這裡所說的套路也是針對大部分情況，也就是最壞情況，對於一些個例，比如經典快排，我們雖然也是使用大O表示他們的複雜度，但是，其實是一種均攤的複雜度。

好了，讓我們看看計算算法複雜度的套路到底是什麼吧。

套路

我將計算算法複雜度的套路歸納為以下五步：

  1. 明確輸入規模n；
  2. 考慮最壞情況或均攤情況，如果最壞情況為個例，那就是均攤；
  3. 計算算法執行的次數與n的關係，並用函數表示出來；
  4. 去除低階項；
  5. 去除常數項；

比如，對於在數組中查找指定元素的操作：

  1. 輸入規模為數組的長度n；
  2. 考慮最壞情況為目標元素不在數組中；
  3. 算法的執行次數為遍歷所有數組元素，也就是n次，用函數表示f(n) = n；
  4. 去除低階項，沒有低階項，還是n；
  5. 去除常數項，沒有常數項，還是n；

所以，在數組中查找指定元素的時間複雜度為O(n)。

OK，使用這種方式可以很快的計算出算法的複雜度，也不需要進行額外的計算，非常快捷高效。

常見的複雜度

上面我們說了，複雜度的計算就是計算與輸入規模n的關係，所以，我們想想數學中關於n的函數就能得出常見的複雜度了，我繪製了一張表格：

與n的關係英文釋義複雜度示例常數（不相關）ConstantO(1)數組按索引查找元素對數相關LogarithmicO(logn)二分查找線性相關LinearO(n)遍歷數組的元素超線性相關SuperlinearO(nlogn)歸併排序、堆排序多項式相關PolynomialO(n^c)冒泡排序、插入排序、選擇排序指數相關ExponentialO(c^n)漢諾塔階乘相關FactorialO(n!)行列式展開n的n次方無O(n^n)不知道有沒有這種算法

在這張表中，複雜度是依次增加的，可以看到常數複雜度O(1)無疑是最好的，讓我們用一張圖來直觀感受下：

後記

本節，我們一起學習了複雜度分析的套路以及常見的複雜度，到目前為止，我們不管是舉例還是講解基本上都在說時間複雜度。

那麼，空間複雜度又是什麼呢？空間與時間之間如何權衡呢？

下一節，我們接著聊。

關注公號主「彤哥讀源碼」，解鎖更多源碼、基礎、架構知識！

相關焦點

  • 時間複雜度的表示、分析、計算方法……一文帶你看懂時間複雜度!
    也叫大O時間複雜度表示法。時間複雜度的分析與計算方法（1）循環次數最多原則我們上面說過了，當n變得越來越大時，公式中的低階，常量，係數三部分影響不了其增長趨勢，可以直接忽略他們，只記錄一個最大的量級就可以了。
  • 基礎知識 | 算法的時間和空間複雜度分析
    並且，一般分為兩個階段，一是算法完成前的理論分析，二是算法完成後實際分析。「理論分析」：這種算法的效率分析是通過假設所有其他因素，如處理器的速度等是恆定的，對算法的實現沒有影響。本篇文章要討論的主要是算法的理論分析，從常見的時間、空間複雜度入手，介紹各種時間、空間複雜度的特點，並總結一些通用數據結構、排序算法、搜索算法相關操作的時間和空間複雜度。最後，針對遞歸操作，使用Master Theorem來分析其複雜度。
  • 到底什麼才是真正的空間複雜度？
    上一節，我們一起學習了複雜度分析的套路和常見的複雜度。但是，我們的案例基本都是以時間複雜度為主，很少接觸到空間複雜度。那麼，到底什麼才是真正的空間複雜度呢？在空間與時間發生衝突時又該如何權衡呢？本節，我們就來解決這兩個問題。
  • 如何進行算法的複雜度分析？
    所以，「快」和「省」是衡量一個算法非常重要的兩項指標，也就是我們經常聽到的時間複雜度和空間複雜度分析。那麼，為什麼需要複雜度分析呢？複雜度分析的方法論是什麼呢？這就是我們本節要解決的問題。好了，進入今天的學習吧。為什麼需要複雜度分析？
  • 數據結構與算法系列——時間、空間複雜度
    幾種常見的時間複雜度分析下邊列舉出常見的時間複雜度量級主要來介紹幾種常見的多項式量級的時間複雜度。常數階 O(1)O(1) 只是常量級時間複雜度的表示方式，不是只有一行代碼，而是每一段代碼的執行時間不隨著 n 的數據規模的變大而變長，這樣的代碼的時間複雜度記為 O(n)。
  • 算法分析：算法的評價因素、時間複雜度及空間複雜度#知識分享
    算法的時間複雜度>算法的時間複雜度是指執行算法所需要的時間，通常用算法中基本運算的執行次數來度量。算法運算次數T(n)是問題規模n(輸入量的多少，稱之為問題規模）的某個函數f(n),記作：T(n)=O(f(n))算法的空間複雜度算法的空間複雜度指算法耗費的存儲空間
  • 如何從最壞、平均、最好的情況分析複雜度？
    上一節，我們從事後統計法過渡到漸近分析法，詳細講解了如何進行算法的複雜度分析。但是，如果遵循嚴格的漸近分析法，需要掌握大量數學知識，這無疑給我們評估算法的優劣帶來了很大的挑戰。那麼，有沒有更好地評估算法的方法呢？答案是必然的，本節，我們就從最壞、平均、最好三種情況來分析分析複雜度。
  • 時間複雜度到底怎麼算
    但有時我們想知道它變化時呈現什麼規律，為此我們引入時間複雜度的概念。算法的時間複雜度也就是算法的時間度量，記作：T(n) = O(f(n))。它表示隨問題規模n的增大，算法執行時間的增長率和f(n)的增長率相同，稱作算法的漸進時間複雜度，簡稱「時間複雜度」。
  • Web前端面試題:如何分析時間複雜度-開課吧
    問題：如何分析時間複雜度？我們用大O表示法表示下常見的時間複雜度量級： 常數階O(1) 線性階O(n) 對數階O(logn) 線性對數階O(nlogn) 平階O(n)當然還有指數階和階乘階這種常極端的複雜度量級，我們就不討論了。
  • 數據結構與算法：算法的時間複雜度
    在數學中，它一般用來刻畫被截斷的無窮級數尤其是漸近級數的剩餘項；在計算機科學中，它在分析算法複雜性的方面非常有用。O(n^2)常見的時間複雜度常數階O(1)//無論代碼執行了多少行，參數有多大，只要執行次數沒有隨著輸入參數的變化而變化，那它的時間複雜度就是 O(1)int i = 1;int
  • 經典排序方法的python實現和複雜度分析
    最優時間複雜度：O(n) （表示遍歷一次發現沒有任何可以交換的元素，排序結束。）最壞時間複雜度：O(n2)穩定性：穩定2.選擇排序選擇排序（Selection sort）是一種簡單直觀的排序算法。它的工作原理如下。
  • 複雜度的度量方法
    平方以及立方級別的複雜度幾乎已經是平貼著y軸的一條直線了，而O(n*log(n))與O(n)還保持著一定的速率進行增長，log(n)又是另一個極端，它變成了一個幾乎貼著x軸的直線1.度量時間複雜度a)O(1)
  • 可能是最可愛的一文讀懂系列:皮卡丘の複雜度分析指南
    提到算法，就不得不提到複雜度分析——這也是程序猿面試跑不了的一關。　　「複雜度分析」，說起來概念特別簡單，可真分析起來，又常常讓人手足無措。　　今天，文摘菌就引用一些神奇寶貝的例子，給大家溫故一下複雜度分析的概念，然後從易到難給大家介紹複雜度分析的常用方法。　　文章分為5個部分。　　1. 為什麼要做「複雜度分析「？
  • 阿里研究員：警惕軟體複雜度困局
    如何識別複雜度增長的因素？在代碼開發以及演進的過程中需要遵循哪些原則？本文將分享阿里研究員谷樸關於軟體複雜度的思考：什麼是複雜度、複雜度是如何產生的以及解決的思路。較長，同學們可收藏後再看。文末福利：免費下載《2020年微服務領域開源數位化報告》。
  • 項目分析的有效度與複雜度關係,以Cover舉例
    剛開始隨著複雜性上升，有效度也會上升，然後維度越來越多，單點研究越來越深，達到瓶頸，然後複雜度繼續提升，有效度反而會下降。當然，即使有了團隊，模型複雜度上來了，也請回歸第一條複雜度和有效度的理論。研究白皮書，了解經濟模型當然是初步要做的，但很重要的是對市場的感覺，對於長期炒股或者炒幣的同學來說，這個也叫作「盤感」（關於大盤的感覺，或者關於盤口的感覺）。其實，項目研究也有盤感。
  • 2020-09-18：LRU手擼，說下時間複雜度和空間複雜度
    2020-09-18：LRU手擼，說下時間複雜度和空間複雜度。福哥答案2020-09-18：方法：哈希表 + 雙向鍊表。時間複雜度：對於 put 和 get 都是 O(1)。空間複雜度：O(capacity)，因為哈希表和雙向鍊表最多存儲 capacity+1 個元素。
  • 降低代碼的圈複雜度——複雜代碼的解決之道
    簡單翻譯一下就是，圈複雜度是用來衡量代碼複雜程度的，圈複雜度的概念是由這哥們Thomas J. McCabe, Sr在1976年的時候提出的概念。1.使用圈複雜度的檢測工具，檢測提交的代碼中的圈複雜度的情況，然後根據圈複雜度檢測情況進行重構。把過長過於複雜的代碼拆成更小的、職責單一且清晰的函數，或者是用設計模式來解決代碼中大量的if else的嵌套邏輯。可能有的人會認為，降低圈複雜度對我收益不怎麼大，可能從短期上來看是這樣的，甚至你還會因為動了其他人的代碼，觸發了圈複雜度的檢測，從而還需要去重構別人寫的代碼。
  • 「算法」時間複雜度沒搞明白？怎麼刷題
    所以我們在寫程序的時候，一定要對自己編寫的程序的時間和空間複雜度有所了解，而且是養成習慣的，寫完了之後能夠下意識地分析出你這段程序的時間和空間複雜度，以及能夠用最簡潔的時間和空間複雜度完成這段程序。基本上是一個頂尖職業選手的必備的素養。
  • 什麼情況下不能使用最壞情況評估算法的複雜度？
    上一節，我們從最壞、平均、最好三種情況分析了算法的複雜度，得出結論，通常來說，使用最壞情況來評估算法的複雜度完全夠用了。但是，有些算法是不能使用最壞情況來評估算法的複雜度的。那麼，有哪些算法呢？本節，我們將從動態數組以及快速排序這兩個個例入手來分析不能使用最壞情況評估複雜度的情形。
  • 算法複雜度O(1),O(n),O(logn),O(nlogn)的含義
    相信很多開發的同伴們在研究算法、排序的時候經常會碰到O(1)，O(n)，O(logn)，O(nlogn)這些複雜度，看到這裡就會有個疑惑，這個O(N)到底代表什麼呢？帶著好奇開始今天文章。首先o(1), o(n), o(logn), o(nlogn)是用來表示對應算法的時間複雜度,這是算法的時間複雜度的表示。不僅僅用於表示時間複雜度，也用於表示空間複雜度。