欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

Java均攤復(fù)雜度和防止復(fù)雜度的震蕩原理分析

 更新時(shí)間:2020年03月11日 10:28:51   作者:WFaceBoss  
這篇文章主要介紹了Java均攤復(fù)雜度和防止復(fù)雜度的震蕩,結(jié)合實(shí)例形式分析了Java均攤復(fù)雜度和防止復(fù)雜度的震蕩相關(guān)概念、原理、實(shí)現(xiàn)方法與注意事項(xiàng),需要的朋友可以參考下

本文實(shí)例講述了Java均攤復(fù)雜度和防止復(fù)雜度的震蕩。分享給大家供大家參考,具體如下:

關(guān)于上一節(jié)封裝數(shù)組的簡(jiǎn)單復(fù)雜度分析方法中我們對(duì)添加操作的時(shí)間復(fù)雜度歸結(jié)為O(n)是考慮了擴(kuò)容操作(resize)在內(nèi)的。就addLast(e)操作而言,時(shí)間復(fù)雜度為O(1),在考慮最壞情況下,每次添加均會(huì)觸發(fā)擴(kuò)容操作,需要移動(dòng)n個(gè)元素,因此此時(shí)addLast操作的時(shí)間復(fù)雜度為O(n)。

(1)addLast(e)均攤時(shí)間復(fù)雜度分析

resize(n)   O(n)

 假設(shè)當(dāng)前capacity=8,并且每一次添加操作都使用addLast方法

17次基本操作包括:9次添加操作,8次轉(zhuǎn)移操作。均攤每次addLast操作進(jìn)行大約兩次基本操作:

平均值為:17/9≈ 2。

  假設(shè)capacity=n,n+1次addLast操作,觸發(fā)resize,總共進(jìn)行了2n+1=(n+1)+ n次基本操作;

  均攤每次addLast操作進(jìn)行大約兩次基本操作:

平均值為: 2n+1 / n+1 ≈ 2

結(jié)論:因此addLast均攤時(shí)間復(fù)雜度為O(1),均攤時(shí)間復(fù)雜度會(huì)比最壞情況有意義,因?yàn)?/strong>一般情況下resize不會(huì)每一次都會(huì)觸發(fā),因此可以分?jǐn)偟狡渌厦妗?/strong>
同理,removeLast操作均攤時(shí)間復(fù)雜度也是O(1)

 (1)addLast(e)和removeLast(e)復(fù)雜度震蕩分析

設(shè)數(shù)組的容量為n,此時(shí)數(shù)組中的個(gè)數(shù)為n個(gè),此時(shí)我們向數(shù)組中添加一個(gè)元素,則會(huì)觸發(fā)擴(kuò)容操作;然后在從數(shù)組中刪除一個(gè)元素時(shí)又會(huì)重新觸發(fā)縮容操作,這樣反復(fù)執(zhí)行都會(huì)耗費(fèi)O(n)的復(fù)雜度,導(dǎo)致復(fù)雜度震蕩。

演示如下:

  第一次執(zhí)行addLast(e)時(shí)間復(fù)雜度:O(n)

   第二次執(zhí)行removeLast(e)時(shí)間復(fù)雜度:O(n)

  第三次執(zhí)行addLast(e)時(shí)間復(fù)雜度:O(n)

   第四次執(zhí)行removeLast(e)時(shí)間復(fù)雜度:O(n)

產(chǎn)生復(fù)雜度震蕩的原因?yàn)椋簉emoveLast時(shí)resize過(guò)于著急(Eager)。

解決辦法為:Lazy(remove延遲執(zhí)行resize)

  容量2n,size=n+1時(shí):

 

 容量2n,size=n時(shí),進(jìn)行縮容1/2:

 容量2n,size=1/4*2n,進(jìn)行縮容1/2  :

當(dāng)size==capacity/4時(shí),才將capacity減半。

現(xiàn)在我們來(lái)進(jìn)一步改進(jìn)我們的程序代碼:

  //從數(shù)組中刪除index位置的元素,返回刪除的元素
  public E remove(int index) {
    //1.判斷索引的選擇是否合法
    if (index < 0 || index > size)
      throw new IllegalArgumentException("您選擇的位置不合法");

    //2.先存儲(chǔ)需要?jiǎng)h除的索引對(duì)應(yīng)的值
    E ret = data[index];

    //將索引為index之后(index)的元素依次向前移動(dòng)
    for (int i = index + 1; i < size; i++) {
      //3.執(zhí)行刪除--實(shí)質(zhì)為索引為index之后(index)的元素依次向前移動(dòng),將元素覆蓋
      data[i - 1] = data[i];
    }
    //4.維護(hù)size變量
    size--;
    // loitering objects != memory leak 手動(dòng)釋放內(nèi)存空間
    data[size] = null;

    //縮容操作
    if (size == data.length / 4 && data.length != 0) {
      resize(data.length / 2);
    }
    //5.返回被刪除的元素
    return ret;
  }

 到此我們完成了一個(gè)比較完善的動(dòng)態(tài)數(shù)組的封裝。

更多關(guān)于java相關(guān)內(nèi)容感興趣的讀者可查看本站專題:《Java數(shù)組操作技巧總結(jié)》、《Java字符與字符串操作技巧總結(jié)》、《Java數(shù)學(xué)運(yùn)算技巧總結(jié)》、《Java數(shù)據(jù)結(jié)構(gòu)與算法教程》及《Java操作DOM節(jié)點(diǎn)技巧總結(jié)

希望本文所述對(duì)大家java程序設(shè)計(jì)有所幫助。

相關(guān)文章

  • SpringBoot和前端Vue的跨域問(wèn)題及解決方案

    SpringBoot和前端Vue的跨域問(wèn)題及解決方案

    所謂跨域就是從 A 向 B 發(fā)請(qǐng)求,如若他們的地址協(xié)議、域名、端口都不相同,直接訪問(wèn)就會(huì)造成跨域問(wèn)題,跨域是非常常見(jiàn)的現(xiàn)象,這篇文章主要介紹了解決SpringBoot和前端Vue的跨域問(wèn)題,需要的朋友可以參考下
    2023-11-11
  • Springboot中@Async異步,實(shí)現(xiàn)異步結(jié)果合并統(tǒng)一返回方式

    Springboot中@Async異步,實(shí)現(xiàn)異步結(jié)果合并統(tǒng)一返回方式

    這篇文章主要介紹了Springboot中@Async異步,實(shí)現(xiàn)異步結(jié)果合并統(tǒng)一返回方式,具有很好的參考價(jià)值,希望對(duì)大家有所幫助,如有錯(cuò)誤或未考慮完全的地方,望不吝賜教
    2023-09-09
  • Spring事務(wù)管理原理及方法詳解

    Spring事務(wù)管理原理及方法詳解

    這篇文章主要介紹了Spring事務(wù)管理原理及方法詳解,文中通過(guò)示例代碼介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友可以參考下
    2020-01-01
  • Windows下 IDEA編譯調(diào)試 hive2.3.9的過(guò)程解析

    Windows下 IDEA編譯調(diào)試 hive2.3.9的過(guò)程解析

    這篇文章主要介紹了Windows下 IDEA編譯調(diào)試 hive2.3.9的過(guò)程,本文給大家介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值,需要的朋友可以參考下
    2023-07-07
  • idea重新下載已刪除的maven依賴包操作

    idea重新下載已刪除的maven依賴包操作

    這篇文章主要介紹了idea重新下載已刪除的maven依賴包操作,具有很好的參考價(jià)值,希望對(duì)大家有所幫助。一起跟隨小編過(guò)來(lái)看看吧
    2021-01-01
  • 如何用Java將數(shù)據(jù)庫(kù)的數(shù)據(jù)生成pdf返回給前端用戶下載

    如何用Java將數(shù)據(jù)庫(kù)的數(shù)據(jù)生成pdf返回給前端用戶下載

    本文詳細(xì)介紹了使用SpringBoot、iText庫(kù)、MyBatis等技術(shù)從數(shù)據(jù)庫(kù)中選取數(shù)據(jù)并生成PDF文件的后端處理流程,文中通過(guò)代碼介紹的非常詳細(xì),需要的朋友可以參考下
    2024-09-09
  • javafx tableview鼠標(biāo)觸發(fā)更新屬性詳解

    javafx tableview鼠標(biāo)觸發(fā)更新屬性詳解

    這篇文章主要為大家詳細(xì)介紹了javafx tableview鼠標(biāo)觸發(fā)更新屬性的相關(guān)資料,具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下
    2017-08-08
  • springboot+redis分布式鎖實(shí)現(xiàn)模擬搶單

    springboot+redis分布式鎖實(shí)現(xiàn)模擬搶單

    這篇文章主要介紹了springboot+redis分布式鎖實(shí)現(xiàn)模擬搶單,小編覺(jué)得挺不錯(cuò)的,現(xiàn)在分享給大家,也給大家做個(gè)參考。一起跟隨小編過(guò)來(lái)看看吧
    2019-03-03
  • Java NIO中的零拷貝原理

    Java NIO中的零拷貝原理

    這篇文章主要介紹了Java NIO中的零拷貝原理,零拷貝即Zero-Copy,顧名思義,零拷貝是指的一種非拷貝的方式來(lái)減少IO次數(shù)的工作方式,零拷貝的作用就是減少IO,提高IO效率,需要的朋友可以參考下
    2023-11-11
  • HttpClient HttpRoutePlanner接口確定請(qǐng)求目標(biāo)路由

    HttpClient HttpRoutePlanner接口確定請(qǐng)求目標(biāo)路由

    這篇文章主要為大家介紹了使用HttpClient HttpRoutePlanner接口確定請(qǐng)求目標(biāo)路由,有需要的朋友可以借鑒參考下,希望能夠有所幫助,祝大家多多進(jìn)步,早日升職加薪
    2023-10-10

最新評(píng)論