匀称环境时间复杂度与均派复杂度一样,也是在思量极度环境大概出现的概率不具有代表性,为了从差别角度阐明而引出地概念。
public boolean contains(E element) { // 最好:O(1) // 最坏:O(n) // 匀称:O(n) return indexOf(element) != ELEMENT_NOT_FOUND;}public int indexOf(E element) { if (element == null) { // 1 for (int i = 0; i < size; i++) { if (elements == null) return i; } } else { for (int i = 0; i < size; i++) { if (element.equals(elements)) return i; // n } } return ELEMENT_NOT_FOUND; }假如有链表的contains(E element)方法,要查找的元素element分为n+1种环境,在链表上面(0~n)和不在链表上面(0~n)。把每种环境下,查找须要遍历元素的个数累加起来,然后再除以n+1,就可以得到须要遍历元素个数的匀称值,即:
省略系数、低阶、常量后得O(n)
复杂度振荡须要先相识缩容机制
缩容
当数组剩余的存储空间较多时为了节流掉部分内存,可以思量举行缩容。
public E remove(int index){ rangeCheck(index); E old=elements[index]; for (int i=index+1;i<size;i++ ) { elements[i-1]=elements; } elements[size--]=null; trim(); return old;}private void trim() { int oldCapacity = elements.length; int newCapacity = oldCapacity*1/3; //小于默认数组容量或现实拥有元素数量大于缩容后容量则返回 if(size >= newCapacity || oldCapacity <= DEFAULT_CAPACITY) return; E[] newElements = (E[]) new Object[newCapacity]; for(int i = 0;i < size;i++) { newElements = elements; } elements = newElements;}
复杂度震荡
将上面的newCapacity稍作改动,可以或许方便我们更好地观察复杂度振荡
int newCapacity = oldCapacity>>1/2;以是复杂度振荡 是指在装满元素的环境下举行添加操纵将会立即触发扩容,之后若举行删除操纵将会立即触发缩容,扩容和缩容的时间复杂度都是O(n)
出现振荡的缘故起因是由于扩容和缩容之间的关系为:扩容2倍 x 缩容1/2倍=1
调解缩容倍数为1/3大概1/4... 复杂度振荡将消失