Shulou(Shulou.com)06/03 Report--

This article focuses on "how to understand dynamic arrays and time complexity". Interested friends may wish to take a look. The method introduced in this paper is simple, fast and practical. Let's let the editor learn "how to understand dynamic arrays and time complexity".

I. Array basic 1.1 definition

Array is a linear table data structure that uses a continuous set of memory space to store a set of data of the same type.

1.2 create process

When we create an array in java, we divide a contiguous piece of memory in memory, and when data enters, the data is stored sequentially in this continuous memory. When you need to read the data in the array, you need to provide the index in the array, and then the array takes the data in memory according to the index and returns it to the reader.

To store data in a row:

All data structures support several basic operations: read, insert, delete array indexes can be semantic or non-semantic, such as student [2], which represents the third student in the array.

Because arrays are stored sequentially when storing data, and the memory for storing data is continuous, the biggest advantage of arrays is that they can be queried quickly, and it is easier to address and read data, but it is more difficult to insert and delete.

Why the greatest advantage of arrays is that they can be queried quickly. Because when we are reading the data, we only need to tell the array where the data is indexed, and the array will read out the data in the corresponding position.

Inserting and deleting are difficult because the memory in which these data are stored is contiguous, the array size is fixed, and inserts and deletes all need to move elements.

For example: an array numbered 0 > 1 > 2 > 3 > 4 has array data stored in all five memory addresses, but now you need to insert a data into 4, which means that starting from 4, all the data in memory will be moved back one position.

Second, write our own array classes

We know that if we want to maintain a certain data, we need to have the most basic functions of adding, deleting, changing, and querying the data, so the array classes we write manually also need to use these basic functions. Although they are not as powerful as List and Map classes, they are basically satisfying for our ordinary developers. The following figure shows one of our basic array classes, so how do we modify the array to write our own array class? here we focus on adding and deleting. All the source codes in this article will be posted at the end, please read on.

From the figure above, we can see that when we create an array class, we need three elements: data, size, and capacity, and the array we need must be able to support multiple data types rather than a single data structure, so we can design classes with generics support so that our data structure can support any data type.

Data: data to be passed size: number of elements capacity: initial capacity of the array

Note: the placement of any data type mentioned above can only be a class object, not a basic data type, but each of our basic data types has a corresponding wrapper class, so our basic type can also be used, but only its wrapper class is used.

So, when we design our array classes, we can design them like this.

/ * @ program: * @ ClassName ArrayPlus * @ description: * @ author: lyy * @ create: 2019-11-18 22:27 * @ Version 1.0 * * / public class ArrayPlus {private E [] data; private int size; / / constructor, pass in the capacity of the array capacity to construct array public ArrayPlus (int capacity) {data = (E []) new Object [capacity]; size = 0 } / / Constructor with no parameters, pass in the capacity of the array capacity=10 public ArrayPlus () {this (10);} / get the number of elements in public int getSize () {return size;} / / get the capacity of the array public int getCapacity () {return data.length } / / returns whether the array is empty public boolean isEmpty () {return size = = 0;} @ Override public String toString () {StringBuffer res = new StringBuffer (); res.append ("Array:Size =% d force 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(); } }2.1 数组添加元素 在数组中是如何添加数据的呢，首先我们需要创建一个 拥有初始容量的数组，当我们创建完成之后，size是指向第一个元素的，也就是 index=0的地方，当我们添加第一个数据后 也就是 data[0]=12后，我们的元素中的个数 size，需要往后挪一位的，也就是 size++的操作，每当我们操作一位，就需要将上面的操作重复执行，直到最后一个元素添加到我们的数组中。 如下图所示： 知道了怎么操作，但是我们要如果通过代码来完成呢? 首先我们要清楚在添加的时候， 在哪里?添加什么数据?，在哪里：我们要在数据的什么地方进行添加，也就是要添加到数组中的哪个下标—— index的地方，知道了在下标，我们只需要将添加的数据，添加到数组中为 index 的地方即可，除此之外，我们只需要对添加时，做一些基本的判断就可以了，代码如下： //在所有元素后添加一个新元素 public void addLast(E e){ add(size,e); } //想所有元素前添加一个新元素 public void addFirst(E e){ add(0,e); } //在第Index个位置插入一个新元素e public void add(int index,E e){ if(size == data.length) throw new IllegalArgumentException("Add failed . Array is full."); if(index < 0 || index >

Size) throw new IllegalArgumentException ("Add failed. Require index"

< 0 || index >

Size. "); for (int I = size-1; I > = index; iMel -) data [iTun1] = data [I]; data [index] = e; size++;} Test Code: public class Main2 {public static void main (String [] args) {ArrayPlus arr = new ArrayPlus (); for (int I = 12; I)

< 16; i++) arr.addLast(i); System.out.println(arr); } }返回结果：Array：Size = 4，capacity = 10 [12，13，14，15] 在数组中是如何执行插入呢?如下图所示： 测试代码：public static void main(String[] args) { ArrayPlus arr = new ArrayPlus(); for (int i = 12; i < 16; i++) arr.addLast(i); System.out.println(arr); arr.add(1,100); System.out.println(arr); }返回结果：Array：Size = 4，capacity = 10 [12，13，14，15] Array：Size = 5，capacity = 10 [12，100，13，14，15]2.2 数组删除元素 如果我们想要删除 索引为1的元素，是怎样操作的呢，首先我们需要先将 索引为2的数据，覆盖到 索引为1的元素上，再将 索引为3的数据放到 索引为2上，依次循环操作，直到最后一位元素，我们在将最后一位元素的数据设置为 null，这样垃圾回收机制就会自动帮我们清除这个元素。整个过程就完成了删除元素的功能，具体流程如下图所示： 实现代码：//查找数组中元素e所在的索引，如果不存在元素e，则返回-1 public int find(E e){ for (int i = 0; i < size; i++) { if(data[i].equals(e)) return i; } return -1; } //从数组中删除index位置的元素，返回删除的元素 public E remove(int index){ if(index < 0 || index >

= size) throw new IllegalArgumentException ("remove failed. Index is illegal."); E ret = data [index]; for (int I = index+1; I

< size; i++) data[i - 1] = data[i]; size--; // loitering objects != memory leak data[size] = null;//如果一旦使用新的元素，添加新的对象就会覆盖掉 return ret; } //从数组中删除第一个位置的元素，返回删除的元素 public E removeFirst(){ return remove(0); } //从数组中删除最后一个位置的元素，返回删除的元素 public E removeLast(){ return remove(size-1); } //从数组中删除元素e public void removeElement(E e){ int index = find(e); if(index != -1) remove(index); }测试：import com.bj.array.ArrayPlus; public class Main2 { public static void main(String[] args) { ArrayPlus arr = new ArrayPlus(); for (int i = 12; i < 16; i++) arr.addLast(i); System.out.println(arr); arr.add(1,100); System.out.println(arr); arr.remove(1); System.out.println(arr); } }返回示例：Array：Size = 4，capacity = 10 [12，13，14，15] Array：Size = 5，capacity = 10 [12，100，13，14，15] Array：Size = 4，capacity = 10 [12，13，14，15] 我们看到结果已经把索引为1的删除了，到这里我们已经完成了一大半了，还有一小点也是最重要的，就是当我们添加数据超过了我们的初始容量大小的时候，就会报错，初始容量，无法添加超过的数据，那么我们应该怎么操作呢?其实很简单，我们只需要给我们数组类，添加一个扩容的方法即可，当我们元素的个数等于数组长度的时候，我们就进行扩容，我们称之为 动态数组。 2.3 动态数组 前边我们讲过的用new给基本类型和对象在运行时分配内存，但它们的已经在编译时就已经确定下来，因为我们为之申请内存的数据类型在程序里有明确的定义，有明确的单位长度。但是，总有些时候，必须要等到程序运行时才能确定需要申请多少内存，甚至还需要根据程序的运行情况追加申请更多的内存。从某种意义上讲，这样的内存管理才是真正的动态。下面，我将带大家编写一个程序为一个整数型数组分配内存，实现动态数组。当你们看到下面这个图的时候，有没有想到什么，没错，有点像C++里面的指针 实现代码：//在第Index个位置插入一个新元素e public void add(int index,E e){ if(index < 0 || index >

Size) throw new IllegalArgumentException ("Add failed. Require index"

< 0 || index >

Size. "); if (size = = data.length) resize (2 * data.length); for (int I = size-1; I > = index; iMub -) data [iTun1] = data [I]; data [index] = e; size++;} private void resize (int newCapacity) {E [] newData = (E []) new Object [newCapacity] For (int I = 0; I

< size; i++) newData[i] = data[i]; data = newData; }动态数组测试：import com.bj.array.ArrayPlus; public class Main2 { public static void main(String[] args) { ArrayPlus arr = new ArrayPlus(); for (int i = 0; i < 10; i++) arr.addLast(i); System.out.println(arr); arr.add(1,100); System.out.println(arr); for (int i = 0; i < 6; i++) arr.remove(i); arr.removeLast(); System.out.println(arr); } }测试结果：Array：Size = 10，capacity = 10 [0，1，2，3，4，5，6，7，8，9] Array：Size = 11，capacity = 20 [0，100，1，2，3，4，5，6，7，8，9] Array：Size = 4，capacity = 10 [100，2，4，6] 从结果中我们可以看到，当我们数组元素超过初始容量大小时，自动扩容到初始容量的 两倍也就是20，当我们数组长度小于1/4的时候，为什么是1/4的时候而不是1/2的时候呢，下面我们会做详细介绍。当我们数组长度小于1/4的时候，会自动缩回到初始10的容量，不会去占据大量的内存空间。 三、时间复杂度分析3.1 基础 五种常见的时间复杂度 1) O(1)：常数复杂度, 最快的算法，数组的存取是O(1) 1) O(n)：线性复杂度, 例如：数组, 以遍历的方式在其中查找元素 1) O(logN)：对数复杂度 1) O(nlogn)：求两个数组的交集, 其中一个是有序数组，A数组每一个元素都要在B数组中进行查找操作，每次查找如果使用二分法则复杂度是 logN 1) O(n2)：平方复杂度，求两个无序数组的交集 在这里，大O描述的是算法的运行时间和输入数据之间的关系 3.2 举例说明 大家可以看下面一个例子 public static int sum(int[] nums){ int sum = 0; for(int num: nums) sum += num; return sum; } 这个算法是 O(n) 复杂度的，其中 n是nums中的元素个数，算法和n呈线性关系 为什么说他是 O(n)的时间复杂度呢，因为这个算法运行的时间的多少是和 nums中元素的个数成线性关系的，那么这个线性关系，表现在我们的 n 是一次方，它不是 O(n) 方的，也不是 O(n) 的立方，n 对应的是一次方。 我们忽略常数，实际时间是：T=c1*n+c2c1：我们要把这个数据从 nums数组中取出来，其次我们还要把 sum这个数取出来，然后 num这个数和 sum相加，最终呢我们要这个结果扔回给 sum中c2：开始开辟了一个Int型的空间，我们把它叫 sum ，要把 0 初始化赋值给sum，在最终呢我们还要把这个 sum 给 return 回去 一方面把 c1 和 c2 具体分析出来是不大必要的，另一方面也是不太可能的，为什么说不可能呢?如果说把 num 从 nums 中取出来，基于 不同的语言，基于 不同的实现，它实际运行的 时间是不等的，就算转换成机器码，它对应的机器码的指令数也有可能是不同的，就算是指令数是相同的，同样的一个指令，在我们 cpu 的底层，你使用的 cpu 不同，很有可能，执行的操作也是不同的，所以在实际上我们可能说出 c1 是几条指令，但是却很难说出 c1 到底是多少，c2也是同理，正因为如此，我们在进行时间复杂度时，是忽略这些常数的。 忽略这些常数就意味着什么，就意味着这些 t=2*n+2和t=2000*n+10000算法这些都是 O(n) 的算法，见下面列表：换句话说他们都是线性数据的算法，也就是说我们这个算法消耗的时间是和我们输入数据的规模成一个线性相关的， t=1*n*n+0也线性算法是和我们成平方关系的 ，他的性能比上面的差，因为他是 O(n^2)的 O(n)和O(n^2)并不代表说 O(n)的算法快于 O(n^2)的算法，我们要看 n 的常数，比如 n=3000的时候，或者 n>

At 3000, O (n ^ 2) consumes much more time than O (n). The larger n is, O (n) is much faster than O (n ^ 2) O: it describes an algorithm, that is, asymptotic time complexity. When high-order terms and low-order terms occur at the same time, low-order terms are ignored. For example, 2*n*n in T=2*n*n+300n+10 is an O (n ^ 2)-level algorithm, which belongs to high-order terms. 300n is the low-order term of O (n). When n is infinite, the low-order term plays a very small role.

3.3 analyze the time complexity of dynamic arrays 3.3.1 add operations

The overall complexity of the add operation is at the O (n) level, as listed below

In programming, we need to adopt the most rigorous design and take into account the worst-case scenario, so we say that the complexity of adding operations belongs to the O (n) level because when we are in addLast, we may perform resize operations. We are right to analyze the worst-case scenario, but addLast cannot perform resize operations every time. For example, there are ten size operations. We need to add ten elements to trigger a resize, and we need to add ten elements to trigger a resize, so it is unreasonable for us to use the worst-case scenario to analyze the time complexity of addLast. See the following section.

3.3.2 complexity Analysis of resize

A total of 17 basic operations were performed: 9 add operations and 8 element transfer operations

9 addLast operations, triggered resize, performed a total of 17 basic operations, an average of each addLast operation, performed 2 basic operations

Suppose capacity = n addLast once, trigger resize, perform a total of 2n+1 basic operations, average, each addLast operation, perform 2 basic operations

In this way, the time complexity is O (1), and in this case, it makes more sense than the worst-case scenario.

The addLast sharing complexity is O (1). Similarly, if we look at the removeLast operation, the average sharing complexity is also O (1).

3.3.3 complexity shock

When the capacity of our array is full, because it is a dynamic array, we go back to automatically expand the capacity, and we immediately remove an operation, because when the capacity of the array is less than half of the initial capacity, the resize will be automatically reduced to half of the size. In this way, there will be a problem, that is, when we are in removeLast, resize is too anxious (Eager)

Solution: Lazy, lazy, is actually very simple, as shown in the following figure:

When our size = = capacity / 4, the capacity is halved as follows:

/ / Delete the element at index position from the array and return the deleted element public E remove (int index) {if (index)

< 0 || index >

= size) throw new IllegalArgumentException ("remove failed. Index is illegal."); E ret = data [index]; for (int I = index+1; I

< size; i++) data[i - 1] = data[i]; size--; // loitering objects != memory leak data[size] = null;//如果一旦使用新的元素，添加新的对象就会覆盖掉 if(size == data.length / 4 && data.length / 2 != 0) resize(data.length / 2); return ret; }完整代码：package com.bj.array; /** * @program: Data-Structures * @ClassName Array * @description: * @author: lyy * @create: 2019-11-18 22:27 * @Version 1.0 **/ public class ArrayPlus { private E[] data; private int size; //构造函数，传入数组的容量capacity 构造array public ArrayPlus(int capacity){ data = (E[])new Object[capacity]; size = 0; } //无参数的构造函数，传入数组的容量capacity=10 public ArrayPlus(){ this(10); } //获取元素中的个数 public int getSize(){ return size; } //获取数组的容量 public int getCapacity(){ return data.length; } //返回数组是否为空 public boolean isEmpty(){ return size == 0; } //在所有元素后添加一个新元素 public void addLast(E e){ add(size,e); } //想所有元素前添加一个新元素 public void addFirst(E e){ add(0,e); } //在第Index个位置插入一个新元素e public void add(int index,E e){ if(index < 0 || index >

Size) throw new IllegalArgumentException ("Add failed. Require index"

< 0 || index >

Size. "); if (size = = data.length) resize (2 * data.length); for (int I = size-1; I > = index; iMub -) data [iTun1] = data [I]; data [index] = e; size++;} / / get the element public E get (int index) {if (index) of the index index position

< 0 || index >

= size) throw new IllegalArgumentException ("Get failed. Index is illegal."); return data [index];} / / modify the element of the index index position as e public void set (int index,E e) {if (index)

< 0 || index >

= size) throw new IllegalArgumentException ("Set failed. Index is illegal."); data [index] = e;} / / find whether there is an element e public boolean contains (E e) {for (int I = 0; I) in the array

< size; i++) { if(data[i].equals(e)) return true; } return false; } //查找数组中元素e所在的索引，如果不存在元素e，则返回-1 public int find(E e){ for (int i = 0; i < size; i++) { if(data[i].equals(e)) return i; } return -1; } //从数组中删除index位置的元素，返回删除的元素 public E remove(int index){ if(index < 0 || index >

= size) throw new IllegalArgumentException ("remove failed. Index is illegal. "); E ret = data [index]; for (int I = index+1; I < size; iTunes +) data [I-1] = data [I]; size--; / / loitering objects! = memory leak data [size] = null / / once a new element is used, adding a new object will overwrite if (size = = data.length / 4 & & data.length / 2! = 0) resize (data.length / 2); return ret;} / / removes the element in the first position from the array and returns the deleted element public E removeFirst () {return remove (0) Delete the element in the last position from the array and return the deleted element public E removeLast () {return remove (size-1);} / / remove the element from the array e / / thinking? If you return whether the deletion was successful or not. 2. If there is duplicate data, how to delete multiple public void removeElement (E e) {int index = find (e); if (index! =-1) remove (index);} @ Override public String toString () {StringBuffer res = new StringBuffer () Res.append (String.format ("Array:Size =% dForce capacity =% d\ n", size,data.length)); res.append ("["); for (int I = 0; I < size; itemized +) {res.append (data [I]); if (I! = size-1) res.append (",") } res.append ("]"); return res.toString ();} private void resize (int newCapacity) {E [] newData = (E []) new Object [newCapacity]; for (int I = 0; I < size; ionization +) newData [I] = data [I]; data = newData }} at this point, I believe you have a deeper understanding of "how to understand dynamic arrays and time complexity". You might as well do it in practice. Here is the website, more related content can enter the relevant channels to inquire, follow us, continue to learn!

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.