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

来源: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
  • Timer是什麼 Timer 是一種用於創建定期粒度行為的機制。 與標準的 .NET System.Threading.Timer 類相似,Orleans 的 Timer 允許在一段時間後執行特定的操作,或者在特定的時間間隔內重覆執行操作。 它在分散式系統中具有重要作用,特別是在處理需要周期性執行的 ...
  • 前言 相信很多做WPF開發的小伙伴都遇到過表格類的需求,雖然現有的Grid控制項也能實現,但是使用起來的體驗感並不好,比如要實現一個Excel中的表格效果,估計你能想到的第一個方法就是套Border控制項,用這種方法你需要控制每個Border的邊框,並且在一堆Bordr中找到Grid.Row,Grid. ...
  • .NET C#程式啟動閃退,目錄導致的問題 這是第2次踩這個坑了,很小的編程細節,容易忽略,所以寫個博客,分享給大家。 1.第一次坑:是windows 系統把程式運行成服務,找不到配置文件,原因是以服務運行它的工作目錄是在C:\Windows\System32 2.本次坑:WPF桌面程式通過註冊表設 ...
  • 在分散式系統中,數據的持久化是至關重要的一環。 Orleans 7 引入了強大的持久化功能,使得在分散式環境下管理數據變得更加輕鬆和可靠。 本文將介紹什麼是 Orleans 7 的持久化,如何設置它以及相應的代碼示例。 什麼是 Orleans 7 的持久化? Orleans 7 的持久化是指將 Or ...
  • 前言 .NET Feature Management 是一個用於管理應用程式功能的庫,它可以幫助開發人員在應用程式中輕鬆地添加、移除和管理功能。使用 Feature Management,開發人員可以根據不同用戶、環境或其他條件來動態地控制應用程式中的功能。這使得開發人員可以更靈活地管理應用程式的功 ...
  • 在 WPF 應用程式中,拖放操作是實現用戶交互的重要組成部分。通過拖放操作,用戶可以輕鬆地將數據從一個位置移動到另一個位置,或者將控制項從一個容器移動到另一個容器。然而,WPF 中預設的拖放操作可能並不是那麼好用。為瞭解決這個問題,我們可以自定義一個 Panel 來實現更簡單的拖拽操作。 自定義 Pa ...
  • 在實際使用中,由於涉及到不同編程語言之間互相調用,導致C++ 中的OpenCV與C#中的OpenCvSharp 圖像數據在不同編程語言之間難以有效傳遞。在本文中我們將結合OpenCvSharp源碼實現原理,探究兩種數據之間的通信方式。 ...
  • 一、前言 這是一篇搭建許可權管理系統的系列文章。 隨著網路的發展,信息安全對應任何企業來說都越發的重要,而本系列文章將和大家一起一步一步搭建一個全新的許可權管理系統。 說明:由於搭建一個全新的項目過於繁瑣,所有作者將挑選核心代碼和核心思路進行分享。 二、技術選擇 三、開始設計 1、自主搭建vue前端和. ...
  • Csharper中的表達式樹 這節課來瞭解一下表示式樹是什麼? 在C#中,表達式樹是一種數據結構,它可以表示一些代碼塊,如Lambda表達式或查詢表達式。表達式樹使你能夠查看和操作數據,就像你可以查看和操作代碼一樣。它們通常用於創建動態查詢和解析表達式。 一、認識表達式樹 為什麼要這樣說?它和委托有 ...
  • 在使用Django等框架來操作MySQL時,實際上底層還是通過Python來操作的,首先需要安裝一個驅動程式,在Python3中,驅動程式有多種選擇,比如有pymysql以及mysqlclient等。使用pip命令安裝mysqlclient失敗應如何解決? 安裝的python版本說明 機器同時安裝了 ...