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

本文實例講述了Java均攤復雜度和防止復雜度的震蕩。分享給大家供大家參考，具體如下：

關于上一節封裝數組的簡單復雜度分析方法中我們對添加操作的時間復雜度歸結為O(n)是考慮了擴容操作(resize)在內的。就addLast(e)操作而言，時間復雜度為O(1)，在考慮最壞情況下，每次添加均會觸發擴容操作，需要移動n個元素，因此此時addLast操作的時間復雜度為O(n)。

（1）addLast(e)均攤時間復雜度分析

resize(n)   O(n)

 假設當前capacity=8，并且每一次添加操作都使用addLast方法

17次基本操作包括：9次添加操作，8次轉移操作。均攤每次addLast操作進行大約兩次基本操作:

平均值為：17/9≈ 2。

  假設capacity=n，n+1次addLast操作，觸發resize，總共進行了2n+1=（n+1）+ n次基本操作；

  均攤每次addLast操作進行大約兩次基本操作：

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

結論：因此addLast均攤時間復雜度為O(1)，均攤時間復雜度會比最壞情況有意義，因為一般情況下resize不會每一次都會觸發，因此可以分攤到其他上面。
同理，removeLast操作均攤時間復雜度也是O(1)

 （1）addLast(e)和removeLast(e)復雜度震蕩分析

設數組的容量為n，此時數組中的個數為n個，此時我們向數組中添加一個元素，則會觸發擴容操作；然后在從數組中刪除一個元素時又會重新觸發縮容操作，這樣反復執行都會耗費O(n)的復雜度，導致復雜度震蕩。

演示如下：

  第一次執行addLast(e)時間復雜度：O(n)

   第二次執行removeLast(e)時間復雜度：O(n)

  第三次執行addLast(e)時間復雜度：O(n)

   第四次執行removeLast(e)時間復雜度：O(n)

產生復雜度震蕩的原因為：removeLast時resize過于著急（Eager）。

解決辦法為：Lazy（remove延遲執行resize）

  容量2n，size=n+1時：

 容量2n，size=n時，進行縮容1/2：

 容量2n，size=1/4*2n，進行縮容1/2  ：

當size==capacity/4時，才將capacity減半。

現在我們來進一步改進我們的程序代碼：

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

    //2.先存儲需要刪除的索引對應的值
    E ret = data[index];

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

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

 到此我們完成了一個比較完善的動態數組的封裝。

更多關于java相關內容感興趣的讀者可查看本站專題：《Java數組操作技巧總結》、《Java字符與字符串操作技巧總結》、《Java數學運算技巧總結》、《Java數據結構與算法教程》及《Java操作DOM節點技巧總結》

希望本文所述對大家java程序設計有所幫助。