本文實(shí)例講述了Java針對(duì)封裝數(shù)組的簡(jiǎn)單復(fù)雜度分析方法。分享給大家供大家參考，具體如下：

完成了數(shù)組的封裝之后我們還需對(duì)其進(jìn)行復(fù)雜度分析：

此處的復(fù)雜度分析主要是指時(shí)間復(fù)雜度分析，算法的時(shí)間復(fù)雜度反映了程序執(zhí)行時(shí)間隨輸入規(guī)模增長(zhǎng)而增長(zhǎng)的量級(jí)，在很大程度上能很好反映出算法的優(yōu)劣與否。

1.簡(jiǎn)單概念

在各種不同算法中，若算法中語(yǔ)句執(zhí)行次數(shù)為一個(gè)常數(shù)，則時(shí)間復(fù)雜度為O(1),另外，在時(shí)間頻度不相同時(shí)，時(shí)間復(fù)雜度有可能相同，如T(n)=n2+3n+4與T(n)=4n2+2n+1它們的頻度不同，但時(shí)間復(fù)雜度相同，都為O(n2)。 按數(shù)量級(jí)遞增排列，常見(jiàn)的時(shí)間復(fù)雜度有：常數(shù)階O(1),對(duì)數(shù)階O(log2n),線性階O(n), 線性對(duì)數(shù)階O(nlog2n),平方階O(n2)，立方階O(n3),...， k次方階O(nk),指數(shù)階O(2n)。隨著問(wèn)題規(guī)模n的不斷增大，上述時(shí)間復(fù)雜度不斷增大，算法的執(zhí)行效率越低。相關(guān)圖如下：

從圖中可見(jiàn)，我們應(yīng)該盡可能選用多項(xiàng)式階O(nk)的算法，而不希望用指數(shù)階的算法。

見(jiàn)的算法時(shí)間復(fù)雜度由小到大依次為：Ο(1)＜Ο(log2n)＜Ο(n)＜Ο(nlog2n)＜Ο(n2)＜Ο(n3)＜…＜Ο(2n)＜Ο(n!)

2.大O簡(jiǎn)單定義（非數(shù)學(xué)領(lǐng)域）

大O描述的是算法運(yùn)行時(shí)間和輸入數(shù)據(jù)之間的關(guān)系

3.簡(jiǎn)單程序時(shí)間復(fù)雜度分析

在上述中算法和n呈線性關(guān)系，那為什么要使用大O呢？稱作O(n)?

其實(shí)上述的程序中，實(shí)際的實(shí)際時(shí)間復(fù)雜度：T = c1*n + c2，在這里忽略了常數(shù)c1和c2。

因此：算法和N呈線性相關(guān)，取n的高階項(xiàng)，因?yàn)楫?dāng)n趨于無(wú)窮大的時(shí)候，低階項(xiàng)起的作用很小。

4.對(duì)動(dòng)態(tài)數(shù)組的時(shí)間復(fù)雜度進(jìn)行分析

（1）動(dòng)態(tài)數(shù)組添加操作時(shí)間復(fù)雜度分析

(1)addLast(e)方法 :只需在最后位置添加 時(shí)間復(fù)雜度 為O(1)

(2)addFirst(e)方法，數(shù)組中均需向后移動(dòng)一位 時(shí)間復(fù)雜度 為O(n)

(3)add(index,e)方法，在index位置插入e,時(shí)間復(fù)雜度與選擇的位置有關(guān)，選擇最后時(shí)間復(fù)雜度 為O(1)；選擇第一個(gè)位置時(shí)間復(fù)雜度 為O(n)；對(duì)于其他情況與概率有關(guān)，在平均情況下只需要移動(dòng)n/2個(gè)位置 時(shí)間復(fù)雜度 為O(n/2)=O(n)

總的來(lái)說(shuō)：數(shù)組添加的時(shí)間復(fù)雜度為O(n)（最壞情況考慮）

在添加的時(shí)候可能會(huì)觸發(fā)resize方法，需要移動(dòng)n個(gè)元素到新數(shù)組中 時(shí)間復(fù)雜度 為O(n)

（2）動(dòng)態(tài)數(shù)組刪除操作時(shí)間復(fù)雜度分析

相同的分析方法，可以得出刪除操作的時(shí)間復(fù)雜度

（3）動(dòng)態(tài)數(shù)組修改操作時(shí)間復(fù)雜度分析

對(duì)于修改，只要通過(guò)索引找到即可進(jìn)行修改，時(shí)間復(fù)雜度為O(1)

（4）動(dòng)態(tài)數(shù)組查找操作時(shí)間復(fù)雜度分析

關(guān)于resize方法，我們完全使用最壞情況分析是不合理的，其分析情況我們將在下一節(jié)進(jìn)行學(xué)習(xí)~

更多關(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ì)有所幫助。