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

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

前言 本篇文章收錄於專輯: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來表示演算法的複雜度,但是,在其它書籍中,你可能還見過Θ、Ω等表示法,它們又是什麼意思呢?

下一節,我們接著聊。

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


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

-Advertisement-
Play Games
更多相關文章
  • 最近工作中用到了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 ...
一周排行
    -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版本說明 機器同時安裝了 ...