动态数组及均摊复杂度与防止复杂度震荡(Java)

心已赠人 2023-06-30 02:52 6阅读 0赞

# 动态数组 #

动态数组是指在声明时没有确定数组大小的数组，即忽略圆括号中的下标；当要用它时，可随时重新指出数组的大小。使用动态数组的优点是可以根据用户需要，有效利用存储空间。

//动态数组
    public class Arr<E> {
        
    	private E[] data;// 创建一个数组
    	private int size;// 数组中元素个数
    	
    	//自定义构造器初始化数组   capacity数组的长度
    	public Arr(int capacity) {
        
    		// TODO Auto-generated constructor stub
    		data = (E[]) new Object[capacity];
    		size = 0;
    	}
    	
    	//默认构造方法   capacity数组的长度=10
    	public Arr() {
        
    		// TODO Auto-generated constructor stub
    		this(10);
    	}
    	
    	//获取数组个数
    	public int getSize() {
        
    		return size;
    	}
    	
    	//获取数组长度
    	public int getCapacity() {
        
    		return data.length;
    	}
    	
    	//判断数组是否为空
    	public boolean isEmpty() {
        
    		return size == 0;
    	}
    
    	//数组中添加元素  index是插入元素的位置，e是插入的元素，时间复杂度为O(n)
    	public void add(int index, E e) {
        
    		if (index < 0 || index > size) {
        
    			try {
        
    				throw new Exception("数组排列要求不能有空");
    			} catch (Exception e1) {
        
    				// TODO Auto-generated catch block
    				e1.printStackTrace();
    			}
    		}
    		//数组扩容
    		if (size == data.length) {
        
    			try {
        
    				resize(2 * data.length);  //这里是扩容为原数组的2倍，Arraylist是扩容1.5倍
    			} catch (Exception e1) {
        
    				// TODO Auto-generated catch block
    				e1.printStackTrace();
    			}
    		}
    		for (int i = size - 1; i >= index; i--) {
        
    			data[i + 1] = data[i];
    		}
    		data[index] = e;
    		size++;
    	}
    	
    	//数组扩容或者缩容,时间复杂度为O(n)
    	private void resize(int newcapacity) {
        
    		// TODO Auto-generated method stub
    		E[] newData = (E[]) new Object[newcapacity];
    		for (int i = 0; i < size; i++) {
        
    			newData[i] = data[i];
    		}
    		data = newData;
    	}
    	
    	//在数组末尾添加元素,时间复杂度为O(1)
    	public void addLast(E e) {
        
    		add(size, e);
    	}
    	
    	//在数组首部添加元素,时间复杂度为O(n)
    	public void addFirst(E e) {
        
    		add(0, e);
    	}
    
    	//重写toString  使用字符串拼接
    	@Override
    	public String toString() {
        
    		StringBuilder res = new StringBuilder();
    		res.append(String.format("Array:size = %d, capacity = %d\n", size, data.length));
    		res.append('[');
    		for (int i = 0; i < size; i++) {
        
    			res.append(data[i]);
    			if (i != size - 1) {
        
    				res.append(',');
    			}
    		}
    		res.append(']');
    		return res.toString();
    	}
    	
    	//获取index位置的数组元素,时间复杂度为O(1)
    	E get(int index) {
        
    		if (index < 0 || index >= size) {
        
    			try {
        
    				throw new Exception("index非法");
    			} catch (Exception e) {
        
    				// TODO Auto-generated catch block
    				e.printStackTrace();
    			}
    		}
    		return data[index];
    	}
    
    	//修改数组元素,时间复杂度为O(1)
    	void set(int index, E e) {
        
    		if (index < 0 || index >= size) {
        
    			try {
        
    				throw new Exception("index非法");
    			} catch (Exception e3) {
        
    				// TODO Auto-generated catch block
    				e3.printStackTrace();
    			}
    		}
    		data[index] = e;
    	}
    	
    	//查询是否包含数组元素e,时间复杂度为O(n)
    	public boolean contains(E e) {
        
    		for (int i = 0; i < size; i++) {
        
    			if (data[i].equals(e))
    				return true;
    		}
    		return false;
    	}
    
    	//查找数组元素e,时间复杂度为O(n)
    	public int find(E e) {
        
    		for (int i = 0; i < size; i++) {
        
    			if (data[i].equals(e))
    				return i;// 返回元素e的位置
    		}
    		return -1;// 找不到元素e，返回-1
    	}
    	
    	//删除指定位置index的数组元素,时间复杂度为O(n)
    	public E remove(int index) {
        
    		if (index < 0 || index >= size) {
        
    			try {
        
    				throw new Exception("index非法");
    			} catch (Exception e3) {
        
    				// TODO Auto-generated catch block
    				e3.printStackTrace();
    			}
    		}
    		//缩容  防止new数组长度为0
    		if (size==data.length/2 && data.length/2 != 0) {
        
    			resize(data.length/2);
    		}
    		E ret = data[index];
    		for (int i = index + 1; i < size; i++) {
        
    			data[i - 1] = data[i];
    		}
    		size--;
    		data[size]=null;
    		return ret;// 返回删除的元素
    	}
    
    	//数组删除首个元素,时间复杂度为O(n)
    	public E removeFirst() {
        
    		return remove(0);
    	}
    	
    	//数组删除最后一个元素,时间复杂度为O(1)
    	public E removeLast() {
        
    		return remove(size - 1);
    	}
    	
    	//数组删除元素e,时间复杂度为O(n)
    	public void removeElement(E e) {
        
    		int index = find(e);
    		if (index != -1) {
        
    			remove(index);
    		} else {
        
    			System.out.println("数组中没有元素e");
    		}
    	}
    }

**测试类Test**

public class Test {
        
    	public static void main(String[] args) {
        
    		Arr<Integer> arr = new Arr();
    		for (int i = 0; i < 10; i++) {
        
    			arr.addLast(i);
    		}
    		System.out.println(arr);
    		
    		arr.add(1, 100);
    		System.out.println(arr);
    		
    		arr.addFirst(-1);
    		System.out.println(arr);
    		
    		arr.remove(2);
    		System.out.println(arr);
    		
    		arr.removeElement(4);
    		System.out.println(arr);
    		
    		arr.removeFirst();
    		System.out.println(arr);
    		
    	}
    }

**测试结果**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDE5MDExMw_size_16_color_FFFFFF_t_70]  
**动态数组时间复杂度分析**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDE5MDExMw_size_16_color_FFFFFF_t_70 1]  
以上时间复杂度都是采取最坏的情况计算的。  
**均摊复杂度分析**  
resize复杂度：O(n)  
但是并不是每次添加和删除都会触发resize。  
以addLast为例，假设capacity=n，每次都使用addLast添加，第n+1次addLast才会触发resize，总共进行了2n+1次基本操作（基本操作即数组元素移动位置）；所以说每次进行addLast操作，进行2次基本操作，均摊复杂度计算出addLast时间复杂度为O(1)。均摊复杂度计算会比最坏情况下复杂度更有意义。  
**复杂度震荡**  
当capacity=n时，再进行addLast操作，数组已经满了，需要进行扩容，时间复杂度为O(n)；然后再进行removeLast操作，size=data.length/2，需要进行缩容，时间复杂度为O(n)；以此类推重复下去，addLast与removeLast操作时间复杂度均为O(n)，这样就出现了复杂度震荡。  
出现问题的原因：removeLast的时候过于着急  
解决方法：Lazy  
当removeLast的时候，先不着急缩容，当size==capacity/4，再进行缩容，这样就避免了复杂度震荡。  
**修改后的remove**

//删除指定位置index的数组元素,时间复杂度为O(n)
    	public E remove(int index) {
        
    		if (index < 0 || index >= size) {
        
    			try {
        
    				throw new Exception("index非法");
    			} catch (Exception e3) {
        
    				// TODO Auto-generated catch block
    				e3.printStackTrace();
    			}
    		}
    		//缩容  为了避免复杂度震荡，当size==capacity/4，再进行缩容
    		//new数组空间时候长度不能为0
    		if (size==data.length/4 && data.length/2 != 0) {
        
    			resize(data.length/2);
    		}
    		E ret = data[index];
    		for (int i = index + 1; i < size; i++) {
        
    			data[i - 1] = data[i];
    		}
    		size--;
    		data[size]=null;
    		return ret;// 返回删除的元素
    	}

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDE5MDExMw_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/2020011419302828.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDE5MDExMw==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDE5MDExMw_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20200114194735224.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDE5MDExMw==,size_16,color_FFFFFF,t_70