什麼情況下不能使用最壞情況評估演算法的複雜度?

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

前言 本篇文章收錄於專輯:http://dwz.win/HjK,點擊解鎖更多數據結構與演算法的知識。 你好,我是彤哥,一個每天爬二十六層樓還不忘讀源碼的硬核男人。 上一節,我們從最壞、平均、最好三種情況分析了演算法的複雜度,得出結論,通常來說,使用最壞情況來評估演算法的複雜度完全夠用了。 但是,有些演算法是 ...


file

前言

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

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

上一節,我們從最壞、平均、最好三種情況分析了演算法的複雜度,得出結論,通常來說,使用最壞情況來評估演算法的複雜度完全夠用了。

但是,有些演算法是不能使用最壞情況來評估演算法的複雜度的。

那麼,有哪些演算法呢?

本節,我們將從動態數組以及快速排序這兩個個例入手來分析不能使用最壞情況評估複雜度的情形。

動態數組

動態數組,對應於Java中的ArrayList,在插入元素時,分成兩種情況:

  1. 數組未滿,元素放在size下標的位置即可;
  2. 數組滿了,需要擴容,一般擴容為N倍大小,Java裡面是1.5倍,擴容時需要創建一個新的數組,並把原來的元素一個一個地拷貝到新的數組中,再插入新的元素;

我簡單地寫一段代碼,你可以感受下:

public class DynamicArray {
    private int[] array;
    private int size;

    public DynamicArray(int capacity) {
        this.array = new int[capacity];
        this.size = 0;
    }

    // 插入元素,時間複雜度為多少呢?
    public void add(int element) {
        // 判斷是否需要擴容
        if (size >= array.length) {
            int newCapacity = array.length + (array.length >> 1);
            int[] newArray = new int[newCapacity];
            for (int i = 0; i < array.length; i++) {
                newArray[i] = array[i];
            }
            this.array = newArray;
        }
        array[size++] = element;
    }

    public int[] getArray() {
        return array;
    }

    public static void main(String[] args) {
        DynamicArray dynamicArray = new DynamicArray(4);
        dynamicArray.add(1);
        dynamicArray.add(2);
        dynamicArray.add(3);
        dynamicArray.add(4);
        dynamicArray.add(5);
        dynamicArray.add(6);

        for (int element : dynamicArray.getArray()) {
            System.out.println(element);
        }
    }
}

那麼,對於動態數組,它的插入元素方法的時間複雜度是多少呢?

按照上一節的說法,按照最壞情況來評估,最壞情況是插入元素時正好數組滿了需要擴容的時候,此時,需要創建一個額外的數組,同時有一個遍歷原數組的過程。

所以,在最壞情況下,動態數組插入元素的時間複雜度為O(n)。

但是,這樣合理嗎?

顯然是不合理的,我插入前面(n-1)個元素的時候,它的時間複雜度都是O(1),就只有插入第n個元素的時候它的時間複雜度才是O(n),所以,這樣來評估動態數組插入元素的時間複雜度明顯不合理。

那麼,如果我把第n個元素插入所需要的時間均攤到所有元素上會怎麼樣呢?

這樣的話,前面每個元素的插入時間只需要加1,變成O(2),忽略常數項,就還是O(1),這樣明顯是要合理一些。

這種方式跟計算平均時間複雜度有點類似,但是,它不是平均時間複雜度,它有一個專門的名稱叫做均攤時間複雜度

均攤時間複雜度,即對一批樣本中出現的個例情況,將它們耗費的時間均攤到所有樣本上,算出來的一個時間複雜度。

你可以把它和平均時間複雜度對比一下:

  1. 平均時間複雜度的計算中沒有個例,所有樣本是同等看待的,想一下線性查找的過程;
  2. 均攤時間複雜度的計算中有個例,這種個例往往就是最壞的情況,想一下動態數組插入元素的過程;
  3. 線性查找第n個元素不是個例,不能把它的時間均攤到所有元素上;

這兩個概念嚴格來說是有區別的,如果無法理解,當成一樣的也問題不大,比如,這裡如果按平均時間複雜度計算的話,結果為 (1+1+1+...+n)/n = (n-1+n)/n = (2n-1)/n=2-1/n,忽略常數項和低階項,最終的結果也是O(1)。

好了,那麼,我們再來看一下動態數組插入元素時的額外空間複雜度。

是不是一樣的道理?數組未滿時額外空間複雜度為O(1),數組滿時額外空間複雜度為O(n),均攤一下變成O(1)。

所以,對於動態數組插入元素的過程,它的均攤時間複雜度和均攤額外空間複雜度都是O(1)。

快速排序

大家都知道經典的快速排序的時間複雜度是O(nlogn),那麼,它的最壞時間複雜度是不是也是O(nlogn)呢?

讓我們來看下麵這個數組:

file

這是一個有序數組,如果此時用經典快速排序來對其進行排序會怎樣呢?

我們取最右邊的元素為軸(Pivot),也就是12,將小於12的放在它的左邊,大於12的放在它的右邊,發現沒有比12大的,所以,右邊沒有元素,經過此步,12的位置固定不變了。

接著,將12左右兩邊的元素再各取最右邊的元素為軸,12的右邊沒有元素,所以,只需要處理左邊就可以了,以10為軸,比10小的放在它的左邊,比10大的放在它的右邊,發現10的右邊也沒有元素(12已經固定了),經過此步,10的位置固定了。

同樣地,最後一步到1這裡,排序完成。

讓我們來分析一下整個過程的複雜度:

第一步,需要遍歷(n-1)個元素;

第二步,需要遍歷(n-2)個元素;

...

最後一步,需要遍歷0個元素;

這種情況下的時間複雜度為:(n-1) + (n-2) + ... + 1 + 0 = (n-1)n/2 = n^2/2 - n/2,忽略常數項和低階項,它的時間複雜度為O(n^2)。

所以,對於有序數組,使用經典快速排序,它的時間複雜度為O(n^2),這也是最壞的情況。

但是,似乎從來沒有人告訴你,經典快速排序的時間複雜度為O(n^2),而是O(nlog2),這是為什麼呢?

那是因為有序數組相對於經典快速排序,也是屬於個例,窮舉無限多的樣本之後,有序數組的可能性實在是太小,所以,我們一般說經典快速排序的時間複雜度為O(nlogn),而不是以最壞情況來評估它的時間複雜度。

我們這裡說的是經典快速排序,為什麼要加“經典”兩個字呢?

後記

好了,本節,我們通過兩個案例來說明瞭並不是所有的演算法都使用最壞情況來評估它的複雜度。

到現在為止,我們都是使用的大O來表示演算法的複雜度,但是,在其它書籍中,你可能還見過Θ、Ω等表示法,它們又是什麼意思呢?

下一節,我們接著聊。

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


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

更多相關文章
  • 最近工作中用到了jQuery UI中排序和拖拽功能,花了大概一天的時間,搞清楚了大概的參數配置,以及遇到的一些問題,總結如下。 sortable 簡單的配置如下: $('#subs-box').sortable({ axis: 'y', cursor: 'ns-resize', placeholde ...
  • 室內地圖製作經過易景空間地圖團隊的持續優化迭代,新版本地圖編輯器中的畫圓柱體、模型庫、快速畫道路、房間直接換紋理貼圖等功能終於上線了,目前市面上一款無需安裝軟體就能直接使用瀏覽器訪問的線上室內地圖製作編輯器。 ...
  • 摘要 重裝電腦系統後,使用npm install初始化項目依賴失敗了,錯誤提示:'proxy' config is set properly..........,具體的錯誤提示如下圖所示: 解決方案 經過報錯信息查詢解決辦法,最終找到了兩個比較好的方案,在此總結一下,以便下次再遇到此類問題。 方案一 ...
  • 引入Javascript的發展史 JavaScript的基本語法篇 1.與HTML結合的方式 2.0 註釋與數據類型 3.0 變數 4.0 運算符 (1)一元運算符 (2)比較運算符 (3)邏輯運算符 (4)三元運算符 5.流程式控制制語句 6.JS特殊語法 練習:在頁面上列印一個99乘法表 <!DOC ...
  • 隨著我國經濟的飛速發展,三維地下管網、地下管線系統直觀高效的參考,結合GIS、資料庫和三維技術,直觀顯示地下管線的空間層次和位置信息,資源的統籌利用審批工作提供準確,易景空間地圖專業致力於三維管網、管網建模、bim管線、三維管網檢測提供專業的技術服務,數據驅動快速生成三維管網矢量模型。 ...
  • 一,效果圖。 二,代碼。 <!DOCTYPE html> <html> <head> <meta charset="utf-8"> <title>CSS 偽類</title> <style> a:link { color: #FF0000; } /* unvisited link */ a:visi ...
  • 前言 本篇文章收錄於專輯:http://dwz.win/HjK,點擊解鎖更多數據結構與演算法的知識。 你好,我是彤哥,一個每天爬二十六層樓還不忘讀源碼的硬核男人。 前面幾節,我們一起學習了演算法的複雜度如何分析,並從最壞、平均、最好以及不能使用最壞情況全方位無死角的剖析了演算法的複雜度,在我們表示覆雜度的 ...
  • //記錄滑鼠按下 public static bool MouseBtnIsDown = false; //截圖起始坐標 public static Point StartPoint; //截圖的長寬 double width = 0; double height = 0; //滑鼠按下事件 pub ...
一周排行
  • 比如要拆分“呵呵呵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. ...