到底什麼才是真正的空間複雜度?

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

前言 本篇文章收錄於專輯:http://dwz.win/HjK,點擊解鎖更多數據結構與演算法的知識。 你好,我是彤哥,一個每天爬二十六層樓還不忘讀源碼的硬核男人。 上一節,我們一起學習了複雜度分析的套路和常見的複雜度。 但是,我們的案例基本都是以時間複雜度為主,很少接觸到空間複雜度。 那麼,到底什麼才 ...


file

前言

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

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

上一節,我們一起學習了複雜度分析的套路和常見的複雜度。

但是,我們的案例基本都是以時間複雜度為主,很少接觸到空間複雜度。

那麼,到底什麼才是真正的空間複雜度呢?在空間與時間發生衝突時又該如何權衡呢?

本節,我們就來解決這兩個問題。

來個例子

現在有一個演算法是這樣的,給定一個數組,將數組中每個元素都乘以2返回,我實現了下麵兩種形式:

private static int[] multi1(int[] array) {
    int[] newArray = new int[array.length];
    for (int i = 0; i < array.length; i++) {
        newArray[i] = array[i] * 2;
    }
    return newArray;
}

private static int[] multi2(int[] array) {
    for (int i = 0; i < array.length; i++) {
        array[i] = array[i] * 2;
    }
    return array;
}

暫且不論這兩個演算法孰好孰壞,你來猜猜他們的空間複雜度各是多少?

你可能會說第一個演算法的空間複雜度為O(n),第二個演算法的空間複雜度為O(1)。

錯!兩個演算法的空間複雜度都是O(n)。

也不能說你完全錯了,因為大部分書籍或者資料都弄錯了。

是時候瞭解真正的空間複雜度了。

空間複雜度與額外空間複雜度

空間複雜度,是指一個演算法運行的過程占用的空間,這個空間包括輸入參數的占用空間和額外申請的空間。

所以,針對上面兩個演算法:

  • 第一個演算法,輸入參數n,額外空間n,兩者相加為2n,去除常數項,空間複雜度為O(n);
  • 第二個演算法,輸入參數n,額外空間0,兩者相加為n,空間複雜度為O(n)。

可以看到,使用空間複雜度很難判斷這兩個演算法的好壞,所以,誕生了另一個概念——額外空間複雜度。

額外空間複雜度,是指一個演算法運行過程中額外申請的空間。

使用額外空間複雜度,針對上面兩個演算法:

  • 第一個演算法,額外空間為n,額外空間複雜度為O(n);
  • 第二個演算法,額外空間為0,額外空間複雜度為O(1);

似乎沒見過有O(0)這種寫法。

可以看到,使用額外空間複雜度能夠很輕易地判斷兩個演算法的好壞(從空間占用的角度)。

所以,是時候糾正錯誤的概念了,以後與人交流的時候請使用“額外空間複雜度”這個概念。

時間與空間的權衡

時間與空間往往是一組糾纏在一起的概念,就像很多小說中寫的一樣,主角最終領悟了時空法則,成為了最強者,小說結束。

在數據結構與演算法中也是一樣,時間與空間往往同時出現,而且經常朝著相反的方向運動。

比如,對於排序演算法:

  • 冒泡排序,時間複雜度O(n^2),空間複雜度O(1)
  • 歸併排序,時間複雜度O(nlogn),空間複雜度O(n)

所以,有兩種思想:以時間換空間,以空間換時間。

那麼,哪種演算法更好呢?

我認為,如果有時間、空間同時比較小的為最好,退而求其次,我選擇以空間換時間,畢竟,隨著電腦硬體技術地不斷發展,空間越來越不值錢,而時間卻越來越值錢,所以,以空間換時間也是一種常用的思想,在我們後續的課程中會出現大量以空間換時間的案例。

想知道冒泡排序和歸併排序演算法的複雜度如何計算嗎?來呀,關註我吧。

後記

本節,我們從一個小例子入手,分析了兩種演算法的空間複雜度,並引出空間複雜度的真身——額外空間複雜度,最後,通過對比冒泡排序和歸併排序的時間複雜度和空間複雜度,得出了以空間換時間的思想。

到這裡,關於複雜度相關的章節就寫完了,從下一節開始,我們將進入常用數據結構與演算法的學習中,敬請期待。

P.S. 下周將進行晉升答辯,會停更幾天,敬請諒解。

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


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

-Advertisement-
Play Games
更多相關文章
  • 1.瀏覽器內核及首碼 在CSS中新的屬性標準尚未明確的情況下,各瀏覽器廠商對新屬性的支持情況也不相同,這個階段會對屬性加廠商首碼進行區分。 根據不同的瀏覽器內核,CSS首碼有所不同,最基本的瀏覽器內核有四種,其他內核都是基於此四種進行再研發的。 ① Gecko內核,首碼為“-moz-”,火狐瀏覽器 ...
  • 接下來我們來看鏈表題 206. 反轉鏈表反轉一個單鏈表。 示例: 輸入: 1->2->3->4->5->NULL 輸出: 5->4->3->2->1->NULL 解題:鏈表題需要我們設立更多的指針來保存我們當前操作的細節;1.我們需要定義3個指針 pre,cur ,next,pre為當前鏈表的前一個 ...
  • 我們今天繼續研究數組在演算法中的應用 167. 兩數之和 II - 輸入有序數組 給定一個已按照升序排列 的有序數組,找到兩個數使得它們相加之和等於目標數。 函數應該返回這兩個下標值 index1 和 index2,其中 index1 必須小於 index2。 說明: 返回的下標值(index1 和 ...
  • 前端程式員怎麼才能學好演算法呢?目前演算法優秀的視頻集中在c++,java,python,本人通過幾個月專心看c++的視頻掌握了演算法的基本思路,都翻譯成前端代碼一一寫出來,從真題到思維全面提升演算法思維面對演算法面試,不畏懼 二分查找法O(logn)尋找數組中的最大/最小值O(N)歸併排序演算法 O(nlog ...
  • (一)兩種打包表單區別 |屬性 |特點 |應用 | | | | | |get |加到url,直接可見 |書簽,歷史瀏覽 | |post |間接可見,請求發送量多 |私密,訂購,評論,反饋 | (二)三種溯源區別 |屬性 |特點 |應用 | | | | | |url(uniform resource ...
  • 自媒體的發展越來越快,今日頭條旗下的西瓜視頻,火山和抖音在網路上的地位也在發生微妙的變化。包括快手和抖音,微視小視頻平臺的競爭和衝擊也是不容小覷。但是很多用戶還是執著於今日頭條搬運,不離不棄。今天老生常談,跟大家說說,如何利用批量去水印下載西瓜視頻的短視頻。工具不僅僅是支持西瓜的,快手的、抖音的、微 ...
  • 數據類型的分類和判斷 基本(值)類型 Number 任意數值 typeof String 任意字元串 typeof Boolean true/false typeof undefined undefined typeof/ null null 對象(引用)類型 Object typeof/insta ...
  • 《應用框架的設計與實現 .NET 平臺》 [作者] (美) Xin Chen[譯者] (中) 溫昱 靳向陽[出版] 電子工業出版社[版次] 2005年07月 第1版[印次] 2005年07月 第1次 印刷[定價] 39.80元 【第01章】 【應用框架介紹】 (P004) 使用應用框架有五大優點 : ...
一周排行
    -Advertisement-
    Play Games
  • 一:背景 準備開個系列來聊一下 PerfView 這款工具,熟悉我的朋友都知道我喜歡用 WinDbg,這東西雖然很牛,但也不是萬能的,也有一些場景他解決不了或者很難解決,這時候藉助一些其他的工具來輔助,是一個很不錯的主意。 很多朋友喜歡在項目中以記錄日誌的方式來監控項目的流轉情況,其實 CoreCL ...
  • 什麼是工業物聯網網關 工業物聯網網關是連接工業場景本地設備(如PLC、掃碼槍、機器人、數控機床等)與遠端業務系統(如SCADA系統、MES系統等)之間的硬體設備或軟體程式。終端設備和遠端業務系統之間的所有數據通信都通過工業物聯網網關來實現。 我們為什麼需要工業物聯網網關 因為從事汽車工業行業,在我們 ...
  • 在.NET Core的依賴註入框架中,服務註冊的信息將會被封裝成ServiceDescriptor對象,而這些對象都會存儲在IServiceCollection介面類型表示的集合中,另外,IServiceCollection介面類型預設使用的實現類型為ServiceCollection。這樣來看,實 ...
  • 如果業務邏輯比較簡單的話,一條主管道就夠了,確實用不到分支管道。不過當業務邏輯比較複雜的時候,有時候我們可能希望根據情況的不同使用特殊的一組中間件來處理 HttpContext。這種情況下如果只用一條管道,處理起來會非常麻煩和混亂。此時就可以使用 Map/MapWhen/UseWhen 建立一個分支 ...
  • .NET nanoFramework 安裝教程 準備材料​ esp32單片機(支持wifi藍牙) 安卓數據線(需要支持傳輸) 註意!請先安裝esp32驅動程式​ ESP32驅動鏈接 安裝 .NET nanoFramework固件快閃記憶體​ 安裝工具 dotnet tool install -g nano ...
  • Redis是大規模互聯網應用常用的記憶體高速緩存資料庫,它的讀寫速度非常快,據官方 Bench-mark的數據,它讀的速度能到11萬次/秒,寫的速度是8.1萬次/秒。 1. 認識Spring Cache 在很多應用場景中通常是獲取前後相同或更新不頻繁的數據,比如訪問產品信息數據、網頁數據。如果沒有使用 ...
  • 1、應用場景 1.1 kafka場景 ​ Kafka最初是由LinkedIn公司採用Scala語言開發,基於ZooKeeper,現在已經捐獻給了Apache基金會。目前Kafka已經定位為一個分散式流式處理平臺,它以 高吞吐、可持久化、可水平擴展、支持流處理等多種特性而被廣泛應用。 ​ Apache ...
  • Python帶我起飛——入門、進階、商業實戰_ 免費下載地址 內容簡介 · · · · · · 《Python帶我起飛——入門、進階、商業實戰》針對Python 3.5 以上版本,採用“理論+實踐”的形式編寫,通過大量的實例(共42 個),全面而深入地講解“Python 基礎語法”和“Python ...
  • 原文連接:https://www.zhoubotong.site/post/67.html Go 標準庫的net/url包提供的兩個函可以直接檢查URL合法性,不需要手動去正則匹配校驗。 下麵可以直接使用ParseRequestURI()函數解析URL,當然這個只會驗證url格式,至於功能變數名稱是否存在或 ...
  • 多商戶商城系統,也稱為B2B2C(BBC)平臺電商模式多商家商城系統。可以快速幫助企業搭建類似拼多多/京東/天貓/淘寶的綜合商城。 多商戶商城系統支持商家入駐加盟,同時滿足平臺自營、旗艦店等多種經營方式。平臺可以通過收取商家入駐費,訂單交易服務費,提現手續費,簡訊通道費等多手段方式,實現整體盈利。 ...