如何從最壞、平均、最好的情況分析複雜度?

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

本篇文章收錄於專輯:http://dwz.win/HjK 前言 你好,我是彤哥,一個每天爬二十六層樓還不忘讀源碼的硬核男人。 上一節,我們從事後統計法過渡到漸近分析法,詳細講解瞭如何進行演算法的複雜度分析。 但是,如果遵循嚴格的漸近分析法,需要掌握大量數學知識,這無疑給我們評估演算法的優劣帶來了很大的挑 ...


file

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

前言

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

上一節,我們從事後統計法過渡到漸近分析法,詳細講解瞭如何進行演算法的複雜度分析。

但是,如果遵循嚴格的漸近分析法,需要掌握大量數學知識,這無疑給我們評估演算法的優劣帶來了很大的挑戰。

那麼,有沒有更好地評估演算法的方法呢?

答案是必然的,本節,我們就從最壞、平均、最好三種情況來分析分析複雜度。

案例

為了便於講解,我寫了一個小例子:

public class LinearSearch {
    public static void main(String[] args) {
        int[] array = new int[]{1, 8, 9, 3, 5, 6, 10, 13};
        int index = search(array, 10);
        System.out.println("index=" + index);
    }

    private static int search(int[] array, int value) {
        for (int i = 0; i < array.length; i++) {
            if (array[i] == value) {
                return i;
            }
        }
        return -1;
    }
}

這個例子使用線性搜索從一個數組中查找一個元素,這個元素有可能存在,也有可能不存在於數組中。

最壞情況

在最壞情況下,要查找的元素不存在於數組中,此時,它的時間複雜度是多少呢?

很簡單,必然需要遍歷完所有元素才會發現要查找的元素不存在於數組中。

所以,最壞情況下,使用線性查找的時間複雜度為O(n)。

平均情況

在平均情況下,我們要照顧到每一個元素,此時,它的時間複雜度如何計算呢?

在上一節,我們已經講過計算方式了,不過,這裡考慮到有元素不存在於數組中,所以,是(n+1)種可能:

1*1/(n+1) + 2*/(n+1) + ... + n*1/(n+1) + (n+1)/(n+1) = 1/(n+1) * (n+1)(n+2)/2 = (n+2)/2

所以,在平均情況下,忽略掉常數項,使用線性查找的時間複雜度也是O(n)。

為什麼要忽略掉常數項?

當n趨向於無窮大的時候,常數項的意義不是很大,所以,可以忽略,比如(n+2)/2=n/2 + 1,n本身已經趨向於無窮大,加不加1有什麼意義呢,n的倍數是2還是1/2並不會有明顯的差別。

同樣地,低階項一般也會抹掉,比如2n^2 + 3n + 1,當n趨向於無窮大的時候,n^2的值是遠遠大於3n的,所以,不需要保留3n。

所以,計算複雜度時通常都會把常數項和低階項抹掉,只保留高階項。

最好情況

最好情況是什麼呢?

如果我們要查找的元素正好是數組的第一個元素,查找一次就找到了,這無疑是最好的情況。

所以,在最好情況下,使用線性查找的時間複雜度是O(1)。

小結

通過上面的分析,可以看到,最壞情況和最好情況是比較好評估的,而平均情況則比較難以計算。

但是,最好情況又不能代表大多數樣本,且平均情況與最壞情況在省略常數項的情況下往往是比較接近的。

所以,通常,我們使用最壞情況來評估演算法的時間複雜度,這也是比較簡單的一種評估方法,且往往也是比較準確的。

後記

本節,我們從最壞、平均、最好三種情況分析了線性查找的時間複雜度,經過詳細地分析,我們得出結論,通常使用最壞情況來評估演算法的時間複雜度。

請註意,我們這裡使用了“通常”,說明有些情況是不能使用最壞情況來評估演算法的時間複雜度的。

那麼,你知道什麼情況下不能使用最壞情況來評估演算法的時間複雜度嗎?

下一節,我們接著聊。

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


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

更多相關文章
  • 在不少電影電視劇中,主角的身邊都有這麼一位電腦高手:他們分分鐘可以黑進反派的網路,攻破安全防線,破解口令密碼,拿到重要文件。他們的電腦屏幕上都是一些看不懂的圖形和數字,你能看懂的就只有那個進度條,伴隨著緊張的BGM,慢慢的向100%靠近······ 上面的場景和套路是不是很眼熟? 影視作品中的黑客當 ...
  • 讓這兩個select相互綁定,讓roleOptions選取值後,worklist彈出得是roleOptions值 <el-select v-model="postForm.projectName" placeholder="請選擇" @change="getList(postForm)"> <el- ...
  • 前言 JS是前端的核心,但有些使用技巧你還不一定知道;本文梳理了JS的41個技巧,幫助大家提高JS的使用技巧;文章有點長,可以clone下源碼,直接擼,源碼地址請戳全部源碼,原創不易,歡迎star;序列文章:Vue 開發必須知道的 36 個技巧React 開發必須知道的 34 個技巧 Array 1 ...
  • 學Web前端要熟練哪些技能?怎樣才能順利求職?Web前端是公認的入門簡單、就業廣闊的行業之一,但隨著越來越多的人加入到前端行業,企業對相關人才的招聘門檻也在無形中被抬高。很多人想知道Web前端開發人才掌握什麼技術才能通過企業面試?接下來小編就給大家一一列舉。 分析各大招聘網站對Web前端人才的技能需 ...
  • 前面介紹了很多ABP系列的文章《ABP框架使用》,一步一步的把我們日常開發中涉及到的Web API服務構建、登錄日誌和操作審計日誌、字典管理模塊、省份城市的信息維護、許可權管理模塊中的組織機構、用戶、角色、許可權、菜單等內容,以及配置管理模塊,界面的高級查詢處理等內容,並根據我們在Winform領域多年... ...
  • 語義化 (1)優點: 使標簽有含義,結構更清晰 增強文檔可讀性,以便代碼維護 瀏覽器和網路爬蟲更好地解析內容 很好地進行搜索引擎優化 (2)新增常用結構標簽如下: header、nav、main、section、aside、article、footer、time、process、figure 表單控 ...
  • 移動端重置樣式 1、禁止用戶選中文字,安卓無效 ­webkit­user­select: none; 2、禁止長按彈出系統菜單。 ­webkit­touch­callout: none; 3、去除android下a/button/input標簽被點擊時產生的邊框 & 去除ios下a標簽被點擊時產生的 ...
  • 1. number, string, boolean(聲明方式加不加new的區別) var a = number( 1 ) 返回數字 1 var b = string( false ) 返回字元串 'false' var c = boolean( 1) 返回布爾值 true (5個false值: 0 ...
一周排行
  • 比如要拆分“呵呵呵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. ...