您好,登錄后才能下訂單哦!
本文實(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ì)有所幫助。
免責(zé)聲明:本站發(fā)布的內(nèi)容(圖片、視頻和文字)以原創(chuàng)、轉(zhuǎn)載和分享為主,文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng),如果涉及侵權(quán)請(qǐng)聯(lián)系站長(zhǎng)郵箱:is@yisu.com進(jìn)行舉報(bào),并提供相關(guān)證據(jù),一經(jīng)查實(shí),將立刻刪除涉嫌侵權(quán)內(nèi)容。