动态数组9
| 方法 |
最好 |
最坏 |
平均 |
add(int index,E element) |
O(1) |
O(n) |
O(n) |
remove(int index) |
O(1) |
O(n) |
O(n) |
set(int index,E element) |
O(1) |
O(1) |
O(1) |
get(int index) |
O(1) |
O(1) |
O(1) |
链表
| 方法 |
最好 |
最坏 |
平均 |
add(int index,E element) |
O(1) |
O(n) |
O(n) |
remove(int index) |
O(1) |
O(n) |
O(n) |
set(int index,E element) |
O(1) |
O(n) |
O( n) |
get(int index) |
O(1) |
O(n) |
O(n) |
动态数组add(E element)复杂度分析
- 均摊复杂度
经过连续的多次复杂度比较低的情况后,出现个别复杂度比较高的情况.
|
复杂度 |
| 最好 |
O(1) |
| 最坏 |
O(n) |
| 均摊 |
O(1) |
动态数组的缩容
- 如果内存使用比较紧张,动态数组又有比较多的剩余空间,可以考虑进行缩容操作.
- 比如剩余空间占总容量的一半时,就进行缩容.
- 如果扩容倍数,缩容时机设计不得当,有可能会导致复杂度震荡.
private void trim() {
// 30
int oldCapacity = elements.length;
// 15
int newCapacity = oldCapacity >> 1;
if (size > (newCapacity) || oldCapacity <= DEFAULT_CAPACITY) return;
// 剩余空间还很多
E[] newElements = (E[]) new Object[newCapacity];
for (int i = 0; i < size; i++) {
newElements[i] = elements[i];
}
elements = newElements;
System.out.println(oldCapacity + "缩容为" + newCapacity);
}
