如何進行演算法的複雜度分析?

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

前言 本篇文章收錄於專輯:http://dwz.win/HjK 你好,我是彤哥,一個每天爬二十六層樓還不忘讀源碼的硬核男人。 大家都知道,數據結構與演算法解決的主要問題就是“快”和“省”的問題,即如何讓代碼運行得更快, 如何讓代碼更節省存儲空間。 所以,“快”和“省”是衡量一個演算法非常重要的兩項指標, ...


file

前言

本篇文章收錄於專輯:http://dwz.win/HjK

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

大家都知道,數據結構與演算法解決的主要問題就是“快”和“省”的問題,即如何讓代碼運行得更快, 如何讓代碼更節省存儲空間。

所以,“快”和“省”是衡量一個演算法非常重要的兩項指標,也就是我們經常聽到的時間複雜度和空間複雜度分析。

那麼,為什麼需要複雜度分析呢?複雜度分析的方法論是什麼呢?

這就是我們本節要解決的問題。

好了,進入今天的學習吧。

為什麼需要複雜度分析?

首先,我們來思考一個問題:對於兩個演算法,我們如何評判誰運行得更快,誰運行時更節省記憶體?

你可能會說,這還不簡單,把這兩個演算法運行一遍,統計下運行時間和占用記憶體不就可以了嗎?

沒錯,這確實是一種不錯的方法,而且它還有個非常形象的名字:事後統計法

但是,這種統計方法具有非常明顯的問題:

  1. 不同的輸入對結果影響很大

    對於一些輸入,可能演算法A執行得更快;對於另外一些輸入,可能演算法B執行得更快。比如,我們後面要學習的排序演算法,輸入的有序性對於不同的排序演算法的影響是完全不同的。

  2. 不同的機器對結果影響很大

    對於同樣的輸入,可能在一臺機器上演算法A更快,而在另外一臺機器上演算法B更快。比如,演算法A可以利用多核而演算法B不能,那麼CPU的核數對這兩個演算法的影響將截然不同。

  3. 數據規模對結果影響很大

    當數據規模小時,可能演算法A更快,而數據規模變大時,可能演算法B更快。比如,我們後面要學習的排序演算法,當數據規模比較小時,插入排序反而比歸併排序更快。

所以,我們需要一種可以不用實際運行演算法,就可以估計演算法執行效率的方法。

這也就是我們所說的複雜度分析。

那麼,怎麼進行複雜度分析呢?有沒有什麼方法論呢?

還真有,這個方法論叫作漸近分析法

什麼是漸近分析法?

漸近分析法,是指將演算法執行的效率與輸入的規模進行掛鉤,隨著輸入規模的增大,演算法執行所需要的時間(或空間)將呈現一種什麼樣的趨勢,這種趨勢就叫作漸近,而這種方法就叫作漸近分析法

概念可能比較拗口,我舉個簡單的例子,對於給定的一個有序數組,我要查找其中某個值所在的位置,比如,查找8這個元素,有哪些方法呢?

file

簡單暴力點的方法,從頭遍歷,查找到該元素即返回。

file

更友好一點的方法,採用二分法,每次定位到數據的中間位置,看其值與目標值的大小,判斷是在左邊還是右邊繼續以二分的方式查找。

file

上面我們舉的例子的輸入規模是8個元素的有序數組,目標值為8,使用第二種方法明顯比第一種方法要快很多。

但是,如果查找的目標是1呢?

對於第一種方法,查找一次足矣。

對於第二種方法,需要查找3次。

此時,第二種方法又次於第一種方法了。

所以,比較兩個演算法的執行效率,不能只考慮到個別元素,而應該顧及到所有元素的感受。

我們以數學的方法來統計兩種方法的平均執行效率,假設輸入規模擴展到n。

對於第一種方法,1號元素查找一次,2號元素查找兩次,3號元素查找三次……,而查找每個元素的概率都是1/n。

所以,它的執行效率為:1x1/n + 2x1/n + 3x1/n + ... nx1/n = nx(n+1)/2/n = (n+1)/2。

對於第二種方法,中間的元素有一個,查找一次,次中間的元素有兩個,查找兩次,次次中間的元素有四個,查找三次...,每次查找的規模都縮小一半,而查找每個元素的概率都是1/n。

所以,它的執行效率為:1x1x1/n + 2x2x1/n + 4x3x1/n + ... + 2^(log2(n)-2) x (log2(n)-1) x 1/n+ 2^(log2(n)-1) x log2(n) x 1/n = ?

我了個去,這個結果等於多少?

是時候展現真正的實力了:

file

你可能要罵娘了,對於我一個小學畢業的,難道我沒辦法學習數據結構與演算法了?

No,No,No,肯定不能這麼玩,那麼,應該怎麼玩呢?我們下一節接著講。

後記

本節,我們從演算法執行效率方面闡述了為什麼需要複雜度分析,並介紹了複雜度分析的方法,即漸近分析法,如果嚴格地遵循漸近分析法,需要大量的數學知識,這無疑增加了我們分析演算法的難度,那麼,有沒有什麼更省心地計算複雜度的方法呢?

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


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

更多相關文章
  • 最近在重新學習JavaScript,手寫了一個tabs標簽頁。 話不多說,直接開始。 首先,是前端頁面。 圖1 tabs 先來把tabs分解一下:圖2 tabs分解 首先,一個大的框div,上面紅色的框是導航欄nav,導航欄里是一個無序列表ul,裡面三個li標簽(黃色的框),li標簽里兩個綠色標簽是 ...
  • 本文將介紹如何從零搭建一個集成vue的electron項目,以及搭建過程中可能會出現的問題及其解決方法 ...
  • 開發過程中經常有意無意地刻意避開數學相關的知識,你也知道解數學題非常枯燥無趣。平時寫動畫也儘量使用 css3 來實現,timer-function 隨意選用,最多也就調一下 cubic-bezier,找到看著舒服的就行。但是怎樣讓動畫更順滑,寫出更貼近自然的動畫,說實話以前我沒怎麼考慮過。 每次當動 ...
  • 一、定義 當客戶不方便直接訪問一個對象或者不滿足需要的時候,提供一個對象來控制堆這個對象的訪問。 二、舉例 惰性單例模式的實現依靠緩存代理 三、結構 代理模式需要一個本體對象和一個代理對象。在代理模式下,對於本體對象的特定的操作通過代理對象進行。如圖所示 這種模式的關鍵點在於:本體對象和代理對象介面 ...
  • setTimeout(一次) setInterval(定時一次) HTML: <!DOCTYPE html> <html> <head> <meta chartset="utf-8"> <title></title> <link rel ="stylesheet" href= "./style.cs ...
  • 加了y滾動條後表格就錯位,需要給所有列加上寬度百分比,如果有單選這種特殊列,要在表格列拿出2%給它,其餘列相加之和為98%即可。 然後還加了一個全局樣式 .ant-table-tbody > tr > td { white-space: break-spaces; } ...
  • 瀏覽器記住密碼的機制 首先理解瀏覽器保存密碼和自動填充是兩個機制,記住密碼機制需要遵循同源策略 測試瀏覽器(mac) 瀏覽器 版本 google 56.0.2924.87 (64-bit) firefox 51.0.1 (64 位) safari 10.0 (12602.1.50.0.10) ie( ...
  • 前言 最近在學習 Angular,一些基礎的語法也學習的差不多了,就在 github 上新建了一個代碼倉庫,準備用 ng-zorro 搭個後臺應用的模板,方便自己以後寫些小東西時可以直接使用。前端項目,最主要的還是能夠實際看到,因此考慮找個地方部署,因為自己的博客是部署到 github page 上 ...
一周排行
  • 比如要拆分“呵呵呵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. ...