Java均攤復(fù)雜度和防止復(fù)雜度的震蕩原理分析
本文實(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)文章
Java之關(guān)于基本數(shù)據(jù)類型和引用數(shù)據(jù)類型的存放位置
這篇文章主要介紹了Java之關(guān)于基本數(shù)據(jù)類型和引用數(shù)據(jù)類型的存放位置,具有很好的參考價(jià)值,希望對(duì)大家有所幫助,如有錯(cuò)誤或未考慮完全的地方,望不吝賜教2023-07-07
Spring Boot部署到Tomcat過(guò)程中遇到的問題匯總
這篇文章主要給大家分享了關(guān)于Spring Boot部署到Tomcat過(guò)程中遇到的一些問題，文中將解決的方法介紹非常詳細(xì)，對(duì)同樣遇到這個(gè)問題的朋友具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來(lái)一起學(xué)習(xí)學(xué)習(xí)吧。2018-03-03
基于JavaMail實(shí)現(xiàn)簡(jiǎn)單郵件發(fā)送
這篇文章主要為大家詳細(xì)介紹了基于JavaMail實(shí)現(xiàn)簡(jiǎn)單郵件發(fā)送，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2022-08-08
IntelliJ IDEA中如何構(gòu)建Spring Boot的項(xiàng)目
這篇文章主要介紹了IntelliJ IDEA中如何構(gòu)建Spring Boot的項(xiàng)目問題，具有很好的參考價(jià)值，希望對(duì)大家有所幫助。如有錯(cuò)誤或未考慮完全的地方，望不吝賜教2023-07-07
java:無(wú)法訪問org.springframework.boot.SpringApplication問題
這篇文章主要介紹了java:無(wú)法訪問org.springframework.boot.SpringApplication問題,具有很好的參考價(jià)值,希望對(duì)大家有所幫助,如有錯(cuò)誤或未考慮完全的地方,望不吝賜教2024-08-08
最近工作中有用到工作流的開發(fā)，引入了flowable工作流框架，在此記錄一下springboot整合flowable工作流框架的過(guò)程，感興趣的朋友一起看看吧2022-04-04
這篇文章主要給大家分享的是SpringBoot攔截器的使用，攔截器通常通過(guò)動(dòng)態(tài)代理的方式來(lái)執(zhí)行。攔截器的生命周期由IoC容器管理，可以通過(guò)注入等方式來(lái)獲取其他Bean的實(shí)例，使用更方便，下面文章的詳細(xì)內(nèi)容,需要的朋友可以參考一下2021-11-11
簡(jiǎn)單介紹一下什么是microservice微服務(wù)
這篇文章主要介紹了一下什么是microservice微服務(wù)微服務(wù)的定義,微服務(wù)到底是什么意思？什么樣的架構(gòu)可以叫做微服務(wù)？這篇文章可以給你答案2023-03-03
Java在java.util包中添加了一個(gè)新的最終類StringJoiner。可以用于構(gòu)造由定界符分隔的字符序列。本文將通過(guò)示例和大家分享一下StringJoiner類的使用，需要的可以參考一下2022-10-10
SpringBoot優(yōu)化啟動(dòng)速度的方法實(shí)現(xiàn)
本篇文章主要介紹了SpringBoot優(yōu)化啟動(dòng)速度的方法實(shí)現(xiàn)，小編覺得挺不錯(cuò)的，現(xiàn)在分享給大家，也給大家做個(gè)參考。一起跟隨小編過(guò)來(lái)看看吧2018-01-01