1. Complexity analysis
1. Significance of complexity analysis
1. Post-hoc statistics
Run the code again, through monitoring and statistical means to obtain the algorithm execution time and memory occupation, called time statistics.
2. Limitations of post-hoc statistics
- Test results are greatly influenced by the test environment
- Test results are heavily influenced by test data
3. We need a method that can roughly estimate the efficiency of algorithm execution independently of the specific test environment and test data.
2. Large O complexity notation
Large O time complexity does not represent the actual execution time of a particular code, but the trend of code execution time as data size increases
3. Time complexity analysis method
1. Rule of addition
The total code complexity is equal to the complexity of the code with the highest magnitude
2. The product rule
The complexity of nested code is equal to the product of the complexity of both inside and outside of the nested code
4. Several common levels of time complexity
1. O(1)
2. O(logn) , O(nlogn)
3. O(m+n) , O(mn
5. Several common levels of spatial complexity
O(1) , O(n), O(n^2) , O(logn) , O(nlogn)
6. Best time complexity, worst time complexity, average time complexity, amortized time complexity
1. Best time complexity
At best, the time complexity of executing a piece of code
2. Worst time complexity
In the worst case, the time complexity of executing a piece of code
3. Average time complexity
The best time complexity and the worst time complexity are the time complexity in extreme cases, the probability of occurrence is not large. The average time complexity is the average of the number of times the code is repeated. Take into account the probability of each situation.
4. Amortize the time complexity
Amortized event complexity is a special case of average time complexity. A set of continuous operations on a single data have low time complexity in most cases and high time complexity in some cases, and there are regular temporal relationships between these operations. At this point, we can analyze the set of operations together, amortizing the higher time complexity operation over the other lower time complexity operations.
An array of 2.
1. The linear table
The data is arranged as a linear structure. The data in a linear table only goes in two directions. Arrays, linked lists, stacks, and queues are all linear table structures.
2. Nonlinear tables
Data are not simply contextual. Trees, graphs are nonlinear tables.
3. Array definition
An array is a linear table structure that uses a contiguous memory space to store a group of data of the same type.
1. Continuous memory space
The elements in an array are contiguous at memory addresses
2. Same type of data
4. The most important feature of arrays: random access
Random access means that arrays support subscript access to the corresponding array elements in O(1) time complexity.
- a[i]_address = base_address + i * data_type_size
- Base_address is the first address of the memory space in the array, I is the subscript of the array element, and data_type_size is the memory size occupied by each element in the array.
5. Insert and delete array elements
1. Normally, to ensure ‘memory continuity ‘, the time complexity of array insertion and deletion is O(n).
2. To improve insertion efficiency, optimization measures are as follows:
- The element to be inserted first is placed at the end
- The inserted element is then placed in the specified position
3. In order to improve deletion efficiency, optimization measures are as follows:
- Each deletion of data is not actually deleted, but merely marks the location data as invalid
- When the space in the array is insufficient, the data of the marked location will be uniformly deleted and the data will be uniformly moved
6. Can containers completely replace arrays
1. Advantages of ArrayList
- A lot of array operations are encapsulated, easy to use
- Dynamic capacity Expansion
- Dynamic capacity expansion involves data relocation and memory application, which is time-consuming. If data size can be determined by extraction, the container capacity must be specified during container initialization.
2. Disadvantages of ArrayList
- Unable to store basic types, using encapsulation classes involves automatic boxing and unboxing, with performance loss.
- Multidimensional arrays it is more intuitive to use arrays directly
Conclusion 3.
- Business development uses container classes directly
- Low-level development, such as writing network framework, do performance optimization to use arrays in preference.
7. Why do array subscripts start at 0
To compute the memory address of an array element for best performance, the subscript starts at 0, and the memory address of the element is computed less than if the subscript starts at 1.
- address = base + singleSize * i
- address = base + singleSize * (i – 1)
8. Arrays in programming languages do not necessarily conform to the definition of arrays in data structures.
1. Arrays implemented in C/C++ fully comply with the standard definition of arrays, storing the same type of data in a contiguous memory space
2. In Java
- An array of primitive types meets the definition of an array in a data structure, storing data of the same type in contiguous memory space.
- Object arrays store the location of objects in memory, not the instance itself. The instances themselves are not contiguous in memory.
3. The linked list
1. Cache elimination algorithm
The cache size is limited, and when the cache is filled, it is up to the cache elimination algorithm to determine which data should be removed and which data should be retained.
First In, First Out
2. LFU/Least Frequently Used
3. LRU/Lease Recently Used is Used at least
2. Linked lists do not require contiguous memory space, and use Pointers to concatenate a set of discrete memory blocks/nodes.
3. Arrays are good at random access by subscript, while linked lists are good at insert and delete operations.
4. Types of linked lists
1. The singly linked list
- Each Node has only a next pointer
- tail.next = null
2. Bidirectional linked lists
- Each Node has a next pointer and a pre pointer
- tail.next = null
3. Circular linked lists
- Each Node has only a next pointer
- tail.next = head
4. Bidirectional circular linked lists
- Each Node has a next pointer and a pre pointer
- tail.next = head
5. Compare linked lists and arrays
- Array uses a group of contiguous memory space, can effectively use the CPU cache, preread the array of multiple elements, improve access efficiency; Linked list elements are not contiguous in memory and are not CPU cache friendly.
- Once the array is declared, it will occupy continuous memory space, and the container triggers OOM. If the array is declared too small, it will frequently expand and consume performance. Linked list itself has no memory limit, naturally support dynamic expansion.
- Each node of the linked list needs to store the next pointer, which consumes more memory. Frequent insertions and deletions can involve frequent memory requisition and freeing, triggering GC and affecting performance. Arrays are better if memory is tight.
6. Use Sentinel to simplify the linked list operation code
public class LinkedList{
public class Node{
public int data;
public Node next;
}
private Node head;
private Node tail;
public LinkedList(a){
// Make sure the list is never empty
Node guard = new Node();
head = guard;
tail = guard;
}
public void insertAtTail(Node node){ tail.next = node; tail = node; }}// Find the specified value in the array
public int findKey(int[] a, int count, int key){
if(a == null || count <= 0) {return -1;
}
if(a[count - 1] == key){
return count - 1;
}
int temp = a[count -1];
//a[count-1] = key
a[count - 1] = key;
int i = 0;
while(a[i] ! = key){ i++; } a[count -1] = temp;
if(i == count - 1) {return -1;
}
return i;
}
Copy the code7. Arrays and linked lists
1. Customize a single linked list to check whether the string is a palindrome string
class Node{
public char data;
public Node next;
}
public class LinkedList{
public Node head;
public Node reverseList(Node tail){
Node curr = head;
Node next = null;
while(curr.next ! = tail){ next = curr.next; curr.next = next.next; next.next = head; head = next; } curr.next =null;
tail.next = head;
head = tail;
return head;
}
public boolean palindrome(a){
if(head == null) {return false;
}
if(head.next == null) {return true;
}
if(head.next.next == null) {return head.data == head.next.data;
}
if(head.next.next.next == null) {return head.data == head.next.next.data;
}
Node slow = head;
Node fast = head.next;
while(slow ! =null&& slow.next ! =null&& fast ! =null&& fast.next ! =null&& fast.next.next ! =null){
slow = slow.next;
fast = fast.next.next;
}
// Get the starting node of the right side of the list to compare
Node right = null;
if(fast.next == null) {// Even number of elements
right = slow.next;
}else{
// Odd number of elements
right = slow.next.next;
}
// Turn the left side of the list upside down
Node left = reverseList(slow);
while(left ! =null&& right ! =null && left.data == right.data){
left = left.next;
right = right.next;
}
// If it is a palindrome string, the left and right halves of the list are equal to each character, and are eventually null
return left.next == null && right.next == null; }}Copy the code2. Use arrays to implement LRU algorithm
public class LRUArray<T>{
public int capacity = 16;
public T[] datas;
public Map<T,Integer> map = new HashMap<>();
public int count = 0;
public LRUArray(a){
datas = new T[capacity];
}
public LRUArray(int cap){
capacity = cap;
datas = new T[capacity];
}
public boolean isFull(a){
return count == capacity;
}
public void transferToRight(int idx){
for(int i = idex; i>0; i--){ datas[i] = datas[i -1]; map.put(datas[i],i); }}public void addToHead(T t){
datas[0] = t;
map.put(t,0);
}
public void access(T t){
if(map.containsKey(t)){
// Place the old element first and move all the previous elements
int index = map.get(t);
transferToRight(index);
addToHead(t);
}else{
/ / the new element
if(isFull()){
// If the array is full, move all the previous elements and add the new element to the first place
transferToRight(capacity - 1);
addToHead(t);
}else{
// Move all previous elements to the right and add the new element to the first placetransferToRight(count); addToHead(t); count++; }}}}Copy the code3. LRU algorithm using single linked list
public class LRUList<T>{
public class Node{
public T data;
public Node next;
}
public Node head;
public int capacity = 16;
public int size = 0;
public LRUList(a){}public LRUList(int cap){
capacity = cap;
}
public boolean isFull(a){
return size == capacity;
}
public void addHead(T t){
t.next = head;
head = t;
}
public void removeTail(a){
if(head == null) {return;
}
if(head.next == null){
head = null;
size--;
return;
}
Node curr = head;
while(curr ! =null&& curr.next ! =null&& curr.next.next ! =null){
curr = curr.next;
}
curr.next = null;
size--;
}
public void access(T t){
if(head == null){
addHead(t);
size++;
return;
}
if(t == head){
return;
}
Node pre = head;
while(pre ! =null&& t ! = pre.next){ pre = pre.next; }if(pre ! =null) {// t is an old element
pre.next = t.next;
addHead(t);
}else{
// t is a new element
if(isFull()){
// The current list is full, we need to remove the tail element and add the new element to the head
removeTail();
addHead(t);
size++;
}else{
// If the list is not full, add the new element directly to the headaddHead(t); size++; }}}}Copy the code4. Single-linked list inversion
public Node reverseList(Node list){
if(list == null) {return null;
}
Node curr = list;
Node head = list;
Node next = null;
while(curr.next ! =null){
next = curr.next;
curr.next = next.next;
next.next = head;
head = next;
}
return head;
}
Copy the code5. Detection of single linked list ring
public boolean hasCircle(Node list){
if(list == null) {return false;
}
Node slow = list;
Node fast = list.next;
while(slow ! =null&& slow.next ! =null&& fast ! =null&& fast.next ! =null&& fast.next.next ! =null){
slow = slow.next;
fast = fast.next.next;
if(slow == fast){
return true; }}return false;
}
Copy the code6. Merge two ordered singly linked lists
public Node mergeTwoSortedList(Node n1, Node n2){
Node soldier = new Node();
Node curr = soldier;
while(n1 ! =null&& n2 ! =null) {if(n1.data <= n2.data){
curr.next = n1;
n1 = n1.next;
}else{
curr.next = n2;
n2 = n2.next;
}
curr = curr.next;
}
if(n1 ! =null){
curr.next = n1;
}
if(n2 ! =null){
curr.next = n2;
}
return soldier.next;
}
Copy the code7. Delete the KTH node from the penultimate list
public void deleteLastK(Node list, int k){
if(lsit == null || k < 1) {throw new IllegalArgumentException("Wrong parameter!");
}
Node fast = list;
int i = 0;
while(fast ! =null && i < k){
fast = fast.next;
}
if(i < k){
throw new IllegalArgumentException("Not long enough!");
}
if(fast == null) {// There are only k elements in the list
Node next = head.next;
head.next = null;
head = next;
return;
}
Node slow = head;
while(slow.next ! =null&& fast.next ! =null){
slow = slow.next;
fast = fast.next;
}
// The node to be deleted is slow.next
Node next = slow.next;
slow.next = next.next;
next.next = null;
return list;
}
Copy the codeFind the center node of the linked list
public Node gainMiddleNode(Node list){
if(list == null) {throw new IllegalArgumentException("Wrong parameter!");
}
Node slow = list;
Node fast = list;
// Fast is fast
while(fast.next ! =null&& fast.next.next ! =null){
slow = slow.next;
fast = fast.next.next;
}
return slow;
}
Copy the code