Collection framework and algorithm of Java data structure

1 collection frame
- 1.1 Collection framework concept
- 1.2 The data structure involved in the container
2 algorithms
- 2.1 Algorithm concept
- 2.2 Algorithm Efficiency
3 Time complexity
- 3.1 Concept of Time Complexity
- 3.2 Asymptotic representation of big O
- 3.3 Derivation of big O order method
4 Space Complexity

1 collection frame

1.1 Collection Framework Concept

The Java Collection Framework Java Collection Framework, also known as the container container, is a set of interfaces and its implementation classes defined in the java.util package.
Its main performance is to put multiple element elements in one unit, which is used to store, retrieve, and manipulate these elements quickly and conveniently, which is commonly known as CRUD.

Classes and Interfaces Overview:

1.2 Data structures involved in containers

Collection: is an interface that contains some methods commonly used by most containers
List: is an interface that specifies the methods to be implemented in ArrayList and LinkedList
- ArrayList: implements the List interface, and the bottom layer is a dynamic type sequence table
- LinkedList: implements the List interface, and the bottom layer is a doubly linked list
Stack: The bottom layer is the stack, and the stack is a special sequence table
Queue: The bottom layer is a queue, which is a special order table
Deque: is an interface
Set: set, which is an interface, and the K model is placed in it
- HashSet: The bottom layer is a hash bucket, and the time complexity of the query is O(1)
- TreeSet: The bottom layer is a red-black tree, the time complexity of the query is O( ), and the keys are ordered
Map: Mapping, which stores the key-value pairs of the K-V model
- HashMap: The bottom layer is a hash bucket, and the query time complexity is O(1)
- TreeMap: The bottom layer is a red-black tree, the time complexity of the query is O( ), and the keys are ordered

2 algorithms

2.1 Algorithm concept

Algorithm: It is a well-defined calculation process that takes one or a set of values as input and produces one or a set of values as output. Simply put, an algorithm is a series of computational steps used to transform input data into output results.

2.2 Algorithm Efficiency

There are two types of algorithm efficiency analysis: the first is time efficiency, and the second is space efficiency. Time efficiency is called time complexity, while space efficiency is called space complexity. Time complexity mainly measures the running speed of an algorithm, while space complexity mainly measures the extra space required by an algorithm. In the early days of computer development, the storage capacity of computers was very small. So I am very concerned about the space complexity. However, with the rapid development of the computer industry, the storage capacity of computers has reached a very high level. So we no longer need to pay special attention to the space complexity of an algorithm.

3 time complexity

3.1 Concept of Time Complexity

Definition of time complexity: In computer science, time complexity of an algorithm is a mathematical function that quantitatively describes the running time of the algorithm. Theoretically speaking, the time it takes for an algorithm to execute cannot be calculated. Only when you put your program on the machine and run it can you know it. But do we need to test each algorithm on the computer? It is possible to test them all on the computer, but it is very troublesome, so there is an analysis method of time complexity. The time spent by an algorithm is proportional to the number of executions of the statements in it. The number of executions of the basic operations in the algorithm is the time complexity of the algorithm.

3.2 Asymptotic representation of big O

// Please calculate how many times the basic operation of func1 has been executed?
void func1(int N){<!-- -->
int count = 0;
for (int i = 0; i < N ; i ++ ) {<!-- -->
for (int j = 0; j < N ; j ++ ) {<!-- -->
count + + ;
}
}
for (int k = 0; k < 2 * N ; k ++ ) {<!-- -->
count + + ;
}
int M = 10;
while ((M--) > 0) {<!-- -->
count + + ;
}
System.out.println(count);
}

Number of basic operations performed by Func1: F(N)=N^2 + 2*N + 10

N = 10 F(N) = 130
N = 100 F(N) = 10210
N = 1000 F(N) = 1002010

In practice, when we calculate the time complexity, we do not necessarily need to calculate the exact number of executions, but only the approximate number of executions, so here we use the asymptotic notation of big O.
Big O notation (Big O notation): is a mathematical notation used to describe the asymptotic behavior of a function

3.3 Derivation of big O-order method

Replace all additive constants in run time with the constant 1.
In the modified run count function, only the highest order term is kept.
If the highest-order term exists and is not 1, remove the constant that is multiplied by this term. The result is big O order.

After using the asymptotic representation of big O, the time complexity of Func1 is: O(n^2)

N = 10 F(N) = 100
N = 100 F(N) = 10000
N = 1000 F(N) = 1000000

Through the above, we will find that the progressive representation of big O removes those items that have little influence on the result, and expresses the number of executions concisely and clearly. In addition, there are best, average and worst case time complexities of some algorithms:
Worst case: maximum number of runs for any input size (upper bound)
Average case: expected number of runs for any input size
Best case: Minimum number of runs (lower bound) for any input size
For example: search for a data x in an array of length N
Best case: 1 find
Worst case: N times to find
Average case: N/2 found
In practice, the general concern is the worst case of the algorithm, so the time complexity of searching data in the array is O(N)

4 space complexity

Space complexity is the degree to which an algorithm temporarily occupies storage space during its operation. Space complexity is not how many bytes the program occupies, because this is not very meaningful, so space complexity is calculated by the number of variables. The space complexity calculation rules are basically similar to the practical complexity, and Big O asymptotic notation is also used.
Example 1:

// Calculate the space complexity of bubbleSort?
void bubbleSort(int[] array) {<!-- -->
for (int end = array. length; end > 0; end--) {<!-- -->
boolean sorted = true;
for (int i = 1; i < end; i ++ ) {<!-- -->
if (array[i - 1] > array[i]) {<!-- -->
Swap(array, i - 1, i);
sorted = false;
}
}
if(sorted == true) {<!-- -->
break;
}
}
}

Example 2:

// Calculate the space complexity of fibonacci?
int[] fibonacci(int n) {<!-- -->
long[] fibArray = new long[n + 1];
fibArray[0] = 0;
fibArray[1] = 1;
for (int i = 2; i <= n ; i ++ ) {<!-- -->
fibArray[i] = fibArray[i - 1] + fibArray[i - 2];
}
return fibArray;
}

Example 3:

// Calculate the space complexity of factorial recursive Factorial?
long factorial(int N) {<!-- -->
return N < 2 ? N : factorial(N-1)*N;
}

Example 1 uses a constant amount of extra space, so the space complexity is O(1)
Example 2 dynamically opens up N spaces, and the space complexity is O(N)
Example 3 recursively calls N times, opens up N stack frames, and each stack frame uses a constant space. The space complexity is O(N)

Table of Contents