### addLast均攤時間復雜度
平均每次addLast操作,進行2次基本操作 . 這樣均攤計算,時間復雜度是O(1)的 ! 在這個例子里,這樣均攤計算,比計算最壞情況有意義 .因為那個最壞的情況不會每次都出現. 這樣計算復雜度就叫均攤復雜度(amortized time complexity) . 同理,我們看removeLast操作,均攤復雜度也為O(1)
### 復雜度震蕩
當我們用均攤復雜度來看addLast和removeLast的操作都是O(1)時間復雜度. 但是當我們同時思考這兩個操作的時候,出現了一個問題,這個問題通常稱為"復雜度振蕩".
### 出現問題的原因
在removeLast時resize過于著急(Eager) ,也就是我們采用了一種過于激進的行為.
解決方案 : Lazy
當size == capacity /4 時,才將capacity減半. 也就是說不是當size == capacity / 2的時候就將容積減半. 這樣就不會產生復雜度震蕩 . 也就是當我們的算法更懶的時候,反而算法整體的性能會更好.
### 修改代碼
~~~
//刪除指定index的元素,并且返回刪除的元素
public E remove(int index)
{
if(index < 0 || index >= size)
throw new IllegalArgumentException("del failed. Index is illegal .");
E element = data[index];
for(int i = index + 1; i < size; i++) {
data[i - 1] = data[i];
}
size--;
data[size] = null;
if(size == data.length / 4 && data.length / 2 != 0)
resize(data.length / 2);
return element;
}
~~~
