动态数组和链表的复杂度分析

复杂度分析一般从如下4个维度进行分析

• 1、最好情况复杂度：代码在最理想情况下的复杂度。
• 2、最坏情况复杂度：代码在最坏情况下的复杂度。
• 3、平均情况复杂度：用代码所有情况下执行次数的平均值。
• 4、均摊复杂度：经过多次连续复杂度较低的情况，出现个别复杂度较高的情况，可以将个别较高的复杂度均摊到较低的复杂度上，基本上均摊复杂度就等于较低的复杂度。

1、动态数组的复杂度分析

1.1、get(int index)

public E get(int index) {
    checkIndex(index);
    return elements[index];
}

上面是数组的查询函数，数组在内存中是连续的，获取指定位置的元素的效率和index大小无关，无论index=0或者index=n都不会影响获取的效率。
这是因为获取指定位置的数组的元素是根据指定位置的内存地址来获取的，而指定index的内存地址=数组的首地址+index*（元素所占字节数）。
所以数组的获取函数的复杂度为O(1)。

1.2、动态数组的set方法

public void set(int index, E element) {
    checkIndex(index);
    elements[index] = element;
}

从对get()函数的分析来看，动态数组的set()函数的复杂度也是O(1)。

1.3、动态数组的add函数

public void add(int index, E element) {
    checkIndexForAdd(index);
    ensureCapacity(size);
    for (int i = size - 1; i >= index; i--) {
        elements[i + 1] = elements[i];
    }
    elements[index] = element;
    size++;
}

我们知道向数组中添加元素，需要移动数组中的元素。

• 1、当向数组中的末尾添加元素时，不需要移动任何元素，直接添加到末尾即可，复杂度为O(1)，这也是最好情况的复杂度。
• 2、当向数组的index=0添加元素时，需要将数组中的所有元素向后移动，此时复杂度为O(n)，这也是最坏情况的复杂度。
• 3、平均情况的复杂度=(1+2+3+...+n)/n=(n+1)/2，则复杂度为O(n)。

1.4、动态数组的另一个add函数

public void add(E element) {
    add(size, element);
}

• 1、每次向数组的末尾添加元素，复杂度为O(1)，这是最好情况复杂度。
• 2、当向数组末尾添加元素时，发生了扩容，此时复杂度为O(n)，这是最坏情况的复杂度。
  该方法每次在添加时，复杂度都为O(1)，但是当数组中元素的个数等于数组容量时再添加就会进行扩容，此时的复杂度为O(n)，在连续多次低级别复杂度的情况下，出现个别高级别的复杂度，此时就可以使用均摊复杂度来表示复杂度。均摊复杂度=(1+1...+n)/n=2-1/n，所以均摊复杂度为O(1)，基本上均摊复杂度就等于低级别的复杂度。

1.5、动态数组的删除remove()

public E remove(int index) {
    checkIndex(index);
    E oldE = elements[index];
    for (int i = index + 1; i < size; i++) {
        elements[i - 1] = elements[i];
    }
    elements[size - 1] = null;
    size--;
    return oldE;
}

数组中元素的删除也需要移动数组中的元素。

• 1、当删除的是末尾的元素时不需要移动数组中的元素，也是最好情况下的复杂度，复杂度为O(1)。
• 2、当删除的是数组的首元素，则需要将后面的所有元素前移，也是最坏情况下的复杂度，复杂度为O(n)。
• 3、平均复杂度=(1+2+3+...+n)/n=(n+1)/2，则复杂度为O(n)。

1.6、复杂度震荡

数组在经过不断扩容之后，如果数组中的很多元素在被删除后，被删除元素的元素所在的空间依然存在就会浪费很多空间，所以可以对数组进行缩容：当数组中的元素的数量小于等于数组容量的一半时进行缩容操作。代码如下：

/**
 * 缩容：当size==capactity/2时就进行缩容,缩小为容量的一半
 */
private void trim() {
    int newCapacity = elements.length >> 1;
    if (size <= newCapacity && elements.length > DEFAULT_CAPACTITY) {
        E[] newElement = (E[]) new Object[newCapacity];
        for (int i = 0; i < size; i++) {
            newElement[i] = elements[i];
        }
        System.out.println(elements.length + "缩容为" + newCapacity);
        elements = newElement;
    }
}

经过上面的分析可知，缩放操作是在删除元素时调用。

public E remove(int index) {
    checkIndex(index);
    E oldE = elements[index];
    for (int i = index + 1; i < size; i++) {
        elements[i - 1] = elements[i];
    }
    // 如果数组中需要存入的数据类型为对象类型的，那么数组中存入的是对象的内存地址
    // 在删除元素时需要将元素向前移动，如果不将数组的最后一个元素置成null，那么它在
    // 下次被赋值之前都会一直引用这个对象，无法被垃圾回收。
    elements[size - 1] = null;
    size--;
        //缩容操作
    trim();
    return oldE;
}

除了在remove(int index)函数中，需要进行缩容操作，在函数clear()中，也需要进行缩容操作，代码如下：

public void clear() {
    for (E e : elements)
        e = null;
    size = 0;
    // 缩容
    if (elements != null && elements.length > DEFAULT_CAPACTITY)
        elements = (E[]) new Object[DEFAULT_CAPACTITY];
}

注意：如果扩容、缩容的设计不得当会造成复杂度震荡的问题。

如果扩容后的容量为原数组大小的两倍，当数组中元素的数量为数组容量的一半时，缩容为原容量的一半时就会造成复杂度震荡。
比如：当数组中元素的个数等于数组的容量时，进行add操作时会进行扩容，然后在删除元素时又会进行缩容操作。这样反复操作就会不断的扩容和缩容，这样反复执行都会耗费O(n)的复杂度，导致复杂度震荡。

如果扩容的系数X缩容的系数=1就会造成复杂度震荡。

2、链表的复杂度分析

2.1、链表的get方法

public E get(int index) {
    Node<E> node = nodeIndex(index);
    return node.element;
}

链表的查询会调用nodeIndex()方法，下面看下这个方法的具体实现

private Node<E> nodeIndex(int index) {
    checkIndex(index);
    Node<E> node = first;
    for (int i = 0; i < index; i++) {
        node = node.next;
    }
    return node;
}

从上面代码可知：

• 1、当查询index=0位置的元素，复杂度为O(1)，这也是最好情况复杂度。
• 2、当查询链表末尾的元素，复杂度为O(n)，这也是最坏情况复杂度。
• 3、平均复杂度=(1+2+3+...+n)/n=(n+1)/2，则复杂度为O(n)。

2.2、链表的set方法

public E set(int index, E element) {
    Node<E> node = nodeIndex(index);
    E old = node.element;
    node.element = element;
    return old;
}

set方法中依然是调用nodeIndex()方法来进行的，其复杂度同get()方法。

2.3、链表的add方法

public void add(int index, E element) {
    checkIndexForAdd(index);
    if (index == 0) {
        first = new Node<E>(element, first);
    } else {
        Node<E> preNode = nodeIndex(index - 1);
        preNode.next = new Node<>(element, preNode.next);
    }
    size++;
}

add方法中依然需要nodeIndex()方法进行操作，其复杂度同get()方法。

2.4、链表的remove方法

public E remove(int index) {
    checkIndex(index);
    Node<E> oldNode = first;
    if (index == 0) {
        first = first.next;
    } else {
        Node<E> preNode = nodeIndex(index - 1);
        oldNode = preNode.next;
        preNode.next = preNode.next.next;
    }
    size--;
    return oldNode.element;
}

remove方法中依然需要nodeIndex()方法进行操作，其复杂度同get()方法。

3、总结

数组和链表的增删改查的复杂度总结如下表：

image.png