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

来源:https://www.cnblogs.com/tong-yuan/archive/2020/07/25/13376223.html
-Advertisement-
Play Games

前言 本篇文章收錄於專輯:http://dwz.win/HjK,點擊解鎖更多數據結構與演算法的知識。 你好,我是彤哥,一個每天爬二十六層樓還不忘讀源碼的硬核男人。 上一節,我們一起學習了表示覆雜度的幾個符號,我們說,通常使用大O來表示演算法的複雜度,不僅合理,而且書寫方便。 那麼,使用大O表示法評估演算法 ...


file

前言

本篇文章收錄於專輯:http://dwz.win/HjK,點擊解鎖更多數據結構與演算法的知識。

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

上一節,我們一起學習了表示覆雜度的幾個符號,我們說,通常使用大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的關係 英文釋義 複雜度 示例
常數(不相關) Constant O(1) 數組按索引查找元素
對數相關 Logarithmic O(logn) 二分查找
線性相關 Linear O(n) 遍曆數組的元素
超線性相關 Superlinear O(nlogn) 歸併排序、堆排序
多項式相關 Polynomial O(n^c) 冒泡排序、插入排序、選擇排序
指數相關 Exponential O(c^n) 漢諾塔
階乘相關 Factorial O(n!) 行列式展開
n的n次方 O(n^n) 不知道有沒有這種演算法

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

file

後記

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

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

下一節,我們接著聊。

關註公號主“彤哥讀源碼”,解鎖更多源碼、基礎、架構知識。


您的分享是我們最大的動力!

-Advertisement-
Play Games
更多相關文章
  • 添加文檔 語法: db.集合名.insert({k1:"v1", k2:"v2"....}) 註意: (1)文檔就是鍵值對,數據類型是BSON格式,支持的值更加豐富。 比如:db.集合名.insert({name:"bashlog", spc:{weight:100, address:"henan" ...
  • 創建資料庫 語法: use database_name; 註意:如果該資料庫不存在,則創建,如果該資料庫存在,則是切換,如果創建了資料庫,沒有任何操作,則會自動刪除該資料庫。 可以使用db命令查看當前所處的資料庫 查看資料庫 語法: show dbs; 創建集合 語法: db.集合名.insert( ...
  • 報錯信息 無法訪問資料庫 ReportServer。 (ObjectExplorer) 具體錯誤信息: 程式位置: 在 Microsoft.SqlServer.Management.UI.VSIntegration.ObjectExplorer.DatabaseNavigableItem.get_C ...
  • 時光在不經意間,總是過得出奇的快。小暑已過,進入中暑,太陽更加熱烈的綻放著ta的光芒,...在外面被太陽照顧的人們啊,你們都是勤勞與可愛的人啊。在房子里已各種姿勢看我這篇這章的你,既然點了進來,那就由我繼續帶你回顧MySql的知識吧! 回顧練習資料girls庫以及兩張表的腳本: https://pa ...
  • Java事務解析(事務的基本操作+隔離的等級+事務的四大特性+事務的概念) 什麼是事務? 如果一個包含多個步驟的業務操作,這些操作被事務管理,那麼這些操作要麼同時成功要麼同時失敗 事務的四大特性(必須記住): 持久性:當事務回滾或者提交之後,資料庫會持久化數據 一致性:事務操作前後,數據的總量不變 ...
  • 快手,快影的App保護用的是同一套代碼,反調試也很容易,下麵請看過程。 >作為一個開發者,有一個學習的氛圍跟一個交流圈子特別重要,這是一個我的iOS交流群:761407670 進群密碼‘博客’,不管你是小白還是大牛歡迎入駐 ,分享BAT,阿裡面試題、面試經驗,討論技術, 大家一起交流學習成長! 1. ...
  • 《全棧工程師 Web 開髮指南》 [作者] (意) Dino Esposito[譯者] (中) 李永倫[出版] 人民郵電出版社[版次] 2019年03月 第1版[印次] 2019年03月 第1次 印刷[定價] 79.00元 【第02章】 【選擇支撐架構】 (P018) 領域模型模式的要點是構建一個完 ...
  • Nginx基本安全優化 隱藏Nginx軟體版本號信息 一般來說,軟體的漏洞都和版本有關,這個很像汽車的缺陷,同一批次的要有問題就都有問題,別的批次可能就都是好的。因此,我們應儘量隱藏或者消除Web服務對訪問用戶顯示各類敏感信息(例如Web軟體名稱以及版本號等信息),增加惡意用戶攻擊伺服器的難度,從而 ...
一周排行
    -Advertisement-
    Play Games
  • 一:背景 準備開個系列來聊一下 PerfView 這款工具,熟悉我的朋友都知道我喜歡用 WinDbg,這東西雖然很牛,但也不是萬能的,也有一些場景他解決不了或者很難解決,這時候藉助一些其他的工具來輔助,是一個很不錯的主意。 很多朋友喜歡在項目中以記錄日誌的方式來監控項目的流轉情況,其實 CoreCL ...
  • 什麼是工業物聯網網關 工業物聯網網關是連接工業場景本地設備(如PLC、掃碼槍、機器人、數控機床等)與遠端業務系統(如SCADA系統、MES系統等)之間的硬體設備或軟體程式。終端設備和遠端業務系統之間的所有數據通信都通過工業物聯網網關來實現。 我們為什麼需要工業物聯網網關 因為從事汽車工業行業,在我們 ...
  • 在.NET Core的依賴註入框架中,服務註冊的信息將會被封裝成ServiceDescriptor對象,而這些對象都會存儲在IServiceCollection介面類型表示的集合中,另外,IServiceCollection介面類型預設使用的實現類型為ServiceCollection。這樣來看,實 ...
  • 如果業務邏輯比較簡單的話,一條主管道就夠了,確實用不到分支管道。不過當業務邏輯比較複雜的時候,有時候我們可能希望根據情況的不同使用特殊的一組中間件來處理 HttpContext。這種情況下如果只用一條管道,處理起來會非常麻煩和混亂。此時就可以使用 Map/MapWhen/UseWhen 建立一個分支 ...
  • .NET nanoFramework 安裝教程 準備材料​ esp32單片機(支持wifi藍牙) 安卓數據線(需要支持傳輸) 註意!請先安裝esp32驅動程式​ ESP32驅動鏈接 安裝 .NET nanoFramework固件快閃記憶體​ 安裝工具 dotnet tool install -g nano ...
  • Redis是大規模互聯網應用常用的記憶體高速緩存資料庫,它的讀寫速度非常快,據官方 Bench-mark的數據,它讀的速度能到11萬次/秒,寫的速度是8.1萬次/秒。 1. 認識Spring Cache 在很多應用場景中通常是獲取前後相同或更新不頻繁的數據,比如訪問產品信息數據、網頁數據。如果沒有使用 ...
  • 1、應用場景 1.1 kafka場景 ​ Kafka最初是由LinkedIn公司採用Scala語言開發,基於ZooKeeper,現在已經捐獻給了Apache基金會。目前Kafka已經定位為一個分散式流式處理平臺,它以 高吞吐、可持久化、可水平擴展、支持流處理等多種特性而被廣泛應用。 ​ Apache ...
  • Python帶我起飛——入門、進階、商業實戰_ 免費下載地址 內容簡介 · · · · · · 《Python帶我起飛——入門、進階、商業實戰》針對Python 3.5 以上版本,採用“理論+實踐”的形式編寫,通過大量的實例(共42 個),全面而深入地講解“Python 基礎語法”和“Python ...
  • 原文連接:https://www.zhoubotong.site/post/67.html Go 標準庫的net/url包提供的兩個函可以直接檢查URL合法性,不需要手動去正則匹配校驗。 下麵可以直接使用ParseRequestURI()函數解析URL,當然這個只會驗證url格式,至於功能變數名稱是否存在或 ...
  • 多商戶商城系統,也稱為B2B2C(BBC)平臺電商模式多商家商城系統。可以快速幫助企業搭建類似拼多多/京東/天貓/淘寶的綜合商城。 多商戶商城系統支持商家入駐加盟,同時滿足平臺自營、旗艦店等多種經營方式。平臺可以通過收取商家入駐費,訂單交易服務費,提現手續費,簡訊通道費等多手段方式,實現整體盈利。 ...