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

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

前言 本篇文章收錄於專輯: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

後記

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

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

下一節,我們接著聊。

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


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

更多相關文章
  • 添加文檔 語法: 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軟體名稱以及版本號等信息),增加惡意用戶攻擊伺服器的難度,從而 ...
一周排行
  • 比如要拆分“呵呵呵90909086676喝喝999”,下麵當type=0返回的是中文字元串“呵呵呵,喝喝”,type=1返回的是數字字元串“90909086676,999”, private string GetStrings(string str,int type=0) { IList<strin ...
  • Swagger一個優秀的Api介面文檔生成工具。Swagger可以可以動態生成Api介面文檔,有效的降低前後端人員關於Api介面的溝通成本,促進項目高效開發。 1、使用NuGet安裝最新的包:Swashbuckle.AspNetCore。 2、編輯項目文件(NetCoreTemplate.Web.c ...
  • 2020 年 7 月 30 日, 由.NET基金會和微軟 將舉辦一個線上和為期一天的活動,包括 微軟 .NET 團隊的演講者以及社區的演講者。本次線上大會 專註.NET框架構建微服務,演講者分享構建和部署雲原生應用程式的最佳實踐、模式、提示和技巧。有關更多信息和隨時瞭解情況:https://focu... ...
  • #abp框架Excel導出——基於vue #1.技術棧 ##1.1 前端採用vue,官方提供 UI套件用的是iview ##1.2 後臺是abp——aspnetboilerplate 即abp v1,https://github.com/aspnetboilerplate/aspnetboilerp ...
  • 前言 本文的文字及圖片來源於網路,僅供學習、交流使用,不具有任何商業用途,版權歸原作者所有,如有問題請及時聯繫我們以作處理。 作者:碧茂大數據 PS:如有需要Python學習資料的小伙伴可以加下方的群去找免費管理員領取 input()輸入 Python提供了 input() 內置函數從標準輸入讀入一 ...
  • 從12年到20年,python以肉眼可見的趨勢超過了java,成為了當今It界人人皆知的編程語言。 python為什麼這麼火? 網路編程語言搜索指數 適合初學者 Python具有語法簡單、語句清晰的特點,這就讓初學者在學習階段可以把精力集中在編程對象和思維方法上。 大佬都在用 Google,YouT ...
  • 在社會上存在一種普遍的對培訓機構的學生一種歧視的現象,具體表現在,比如:當你去公司面試的時候,一旦你說了你是培訓機構出來的,那麼基本上你就涼了,那麼你瞞著不說,然後又通過了面試成功入職,但是以後一旦在公司被髮現有培訓經歷,可能會面臨被降薪,甚至被辭退,培訓機構出來的學生,在用人單位眼裡就是能力低下的 ...
  • from typing import List# 這道題看了大佬寫的代碼,經過自己的理解寫出來了。# 從最外圍的四周找有沒有為O的,如果有的話就進入深搜函數,然後深搜遍歷# 判斷上下左右的位置是否為Oclass Solution: def solve(self, board: List[List[s ...
  • import requests; import re; import os; # 1.請求網頁 header = { "user-agent":'Mozilla/5.0 (Macintosh; Intel Mac OS X 10_15_5) AppleWebKit/537.36 (KHTML, li ...
  • import requests; import re; import os; import parsel; 1.請求網頁 header = { "user-agent":'Mozilla/5.0 (Macintosh; Intel Mac OS X 10_15_5) AppleWebKit/537. ...