算法和数据结构

支持动态扩容的数组及复杂度分析

2021年3月30日 /

零 引言

我们实现了自己的数组，并且将其改造成了可以支持任意类型的泛型数组。但是，这还不算完，我们的数组还不支持动态扩容。如果我们初始化时，指定容量小了，则没法扩容，反之，如果我们初始化容量偏大，后面用不到那么多，则造成空间的浪费。

一 改造add()为支持动态扩容的方法

改造前：

public void add(E e, int index) {
    if(size==data.length){
      throw new IllegalArgumentException("add failed.array is full");
    }
    if (index < 0 || index > size) {
        throw new IllegalArgumentException("add failed.index is invalid");
    }
    for (int i = size; i>index; i--) {
        data[i] = data[i - 1];
    }
    data[index] = e;
    size++;
}

改造后：

public void add(E e,int index){
  if (index<0 || index>size){
    throw new IllegalArgumentException("add failed.index is invalid");
  }
  //如果数组满了，即size==data.length,则扩容为原来的2倍大小
  if(size==data.length){
    resize(2*data.length);
  }
  for(int i=size;i>index;i--){
    data[i]=data[i-1];
  }
  data[index]=e;
  size++;
}
//添加新的扩容方法，将元素组的元素copy到新数组，然后原数组的引用指向新数组。
private void resize(int newCapacity){
  E[] newData=(E[])new Object[newCapactiy];
  for(int i=0;i<size;i++){
    newData[i]=data[i];
  }
  data=newData;
}

二 改造remove()为支持动态扩容的方法

改造前：

publiv E remove(int index){
  if(index<0||index>=size){
    throw new IllegalArgumentException("remove failed.index is invalid");
  }
  E temp=data[index];
  for(int i=index;i+1<size;i++){
    data[i]=data[i+1];
  }
  size--;
  retrun temp;
}

改造后：

public E remove(int index){
  if(index<0||index>=size){
    throw new IllegalArgumentException("remove failed.index is invalid");
  }
  E temp=data[index];
  for(int i=index;i+1<size;i++){
    data[i]=data[i+1];
  }
  size--;
  //如果实际元素个数是总容量的一般，且总容量的二分之一大小不等于1的时候，执行缩容，所谓原来的1/2大小
  if(size==data.length/2 && data.length/2 ! = 1){
    resize(data.length/2);
  }
}

三 动态扩容的测试验证

public static void main(String[] args) {
  //初始化容量为1的数组
    Array<Student> studentArray = new Array<Student>(1);
    studentArray.addLast(new Student("Jim", 10));
  //数组的容量和大小都是1
    System.out.println(studentArray);
  
  //继续插入元素，数组就会自动扩容，扩容为原来的2倍
    studentArray.addFirst(new Student("Kate", 8));
  //数组的容量和大小都是2
    System.out.println(studentArray);
  //再次插入，出发扩容，容量是4，大小变为3
    studentArray.add(new Student("Jerry", 9), 1);
    System.out.println(studentArray);
  //继续插入，容量，大小都是4
    studentArray.add(new Student("Parker", 7), 2);
    System.out.println(studentArray);
  //再次执行插入，触发扩容，容量是8，大小为5；
    studentArray.add(new Student("Charlie", 11), 0);
    System.out.println(studentArray);
    System.out.println(studentArray.contains(new Student("Jerry", 9)));
 //执行删除操作，容量是8，大小为4，触发缩容操作，变为容量和大小都是4的数组
    studentArray.removeElement(new Student("Jim", 10));
    System.out.println(studentArray);
}
//Array size: 1 ,length: 1
Student{name='Jim', age=10}]
Array size: 2 ,length: 2
Student{name='Kate', age=8} , Student{name='Jim', age=10}]
Array size: 3 ,length: 4
Student{name='Kate', age=8} , Student{name='Jerry', age=9} , Student{name='Jim', age=10}]
Array size: 4 ,length: 4
Student{name='Kate', age=8} , Student{name='Jerry', age=9} , Student{name='Parker', age=7} , Student{name='Jim', age=10}]
Array size: 5 ,length: 8
Student{name='Charlie', age=11} , Student{name='Kate', age=8} , Student{name='Jerry', age=9} , Student{name='Parker', age=7} , Student{name='Jim', age=10}]
true
Array size: 4 ,length: 4
Student{name='Charlie', age=11} , Student{name='Kate', age=8} , Student{name='Jerry', age=9} , Student{name='Parker', age=7}]

四 复杂度分析

1 增加元素复杂度

addLast(E e), O(1)

addFirst(E e); O(n)

add(E e,int index); O(n/2)，看做O(n)，因为每次插入的位置index不确定，所以，每次需要移动的元素个数也不确定。从概率上讲，可以认为每次需要移动n/2个元素，进而复杂度是O(n)。

2 删除元素复杂度

removeLast() O(1)

removeFirst() O(n)

remove(int index) O(n/2)，看做是O(n)，处理方式跟任意位置添加元素一样。

3 查找元素复杂度

find(E e) O(n)

get(int index) O(1)

contains(E e) O(n)

如果有索引下标的查找，复杂度为O(1)，没有索引下标的查找，复杂度是O(n)。

4 修改元素复杂度

modify(E e,E newValue) O(n)

set(E e,int index) O(1)

5 均摊复杂度分析

对于添加元素，如果每次都是addLast()，则复杂度是O(1)，但是我们肯定不能说数组的添加元素的时间复杂度是O(1)，因为这是最为理想的情况。当我们在考虑算法的时间复杂度的时候，我们一般都是考虑最坏的情况，而不会考虑最优的情形。反之，也不能因为每次都调用addFirst()，我们就说时间复杂度是O(n)。那么，添加元素时，数组的复杂度到底是O(1)还是O(n)呢？该怎么分析它的复杂度呢？

假定数组初始化容量为10，执行了10次addLast()操作，每次操作的复杂度是O(1)，最后一次导致数组扩容，resize()扩容的复杂度为O(n)，那么就相当于执行了20 次操作，一共执行了11次，平均每次的复杂度是O(2)，记为O(1)。同样，对于removeLast()操作，导致数组缩容的情况下，其时间复杂度也是O(1)。

这是采用了均摊复杂度分析的思想。即对于第n+1次操作导致的resize()，将此次操作的成本平均的分摊给前n次操作。

采用均摊复杂度分析的情况下，addLast()，removeLast()的复杂度都是O(1)。

五 复杂度震荡

对于addLast()和removeLast()，假定数组满的话，就触发扩容2倍的操作，数组实际大小=总容量的/2的时候，就执行缩容操作。

那么，假定当前数组容量是10，size=10，执行一次addLast()则触发扩容：size=11，capacity=20；

此时，执行了removeLast()，则size=10,capacity=10，触发缩容操作，size=10,capacity=10;

接下来执行了addLast()，导致扩容；

removeLast()，导致缩容。

此时，每一次扩容操作的时间复杂度都将达到O(n)，性能变得很差。

因此，如何避免这种情况出现呢？我们考虑对于缩容操作的时候，缩容的时候，当实际空间size=capacity/4的时候，我们才执行缩容操作，这样就可以避免复杂度震荡。

public E remove(int index){
  if(index<0||index>=size){
    throw new IllegalArgumentException("remove failed.index is invalid");
  }
  E temp=data[index];
  for(int i=index;i+1<size;i++){
    data[i]=data[i+1];
  }
  size--;
  //如果实际元素个数是总容量的一般，且总容量的二分之一大小不等于1的时候，执行缩容，所谓原来的1/2大小
  if(size==data.length/4 && data.length/2 ! = 1){
    resize(data.length/2);
  }
}

六 小结

至此，我们自己动手实现了一个基本的数据结构，数组。涵盖了常见的方法：

带初始化容量大小的构造方法；

默认构造方法；

返回数组实际长度；

返回数据包含元素个数；

判断数组是否为空；

向数组末尾添加元素；

向数组首位添加元素；

向数组任意位置添加元素；

删除数组末尾元素；

删除数组首位元素；

删除数组任意位置元素；

判断数组是否包含某个元素；

返回数组中任意位置处元素；

返回数组中第一个元素；

返回数组中最后一个元素；

查找某个元素在数组中存放的位置；

修改某个位置处的元素；

修改数组中某个元素的值；

修改数组中所有特定元素的值。

我们还将数组改造成了支持任意类型的泛型数组。

最后，还将它改造成了支持动态扩容的数组。接下来，我们开始研究一下栈和队列这两种基本数据结构。

Post Views: 2,223

您可能也喜欢

链表头指针和虚拟头节点小结

2021年4月26日

如何实现一个支持动态扩展的循环队列

2021年4月10日

LeetCode21题-合并有序链表

2021年4月28日