![](/images/doc/24fee09e455cb1ab6539f56bec6001b1.jpg)
This article is only my own notes, and does not have any guiding significance.
The original intention of the code is to make it easy to understand. There are many codes optimized by God on the Internet. It is not recommended to copy the code in this article in the project.
Catalog
-
Time complexity
- Operation of Constant Time
- Computation of Time Complexity
- Time Complexity of Constant Operational Expression Types
- Comparisons with the same time complexity
-
Bubble sort
- Improved Bubble Sorting
-
Selection sort
- Binary Selective Sorting
- Insertion sort
- Worst case, best case, average case of time complexity
- Logarithmic device
Time complexity
There are two very important indicators to measure the quality of the code: run time and occupied space.
The former is represented by time complexity, and the latter is represented by time complexity. Spatial complexity (that is, the measure of the size of the temporary storage space occupied by the algorithm in the running process).
-
Operation of Constant Time
If an operation has nothing to do with the amount of data, each operation is completed in a fixed time, called a constant operation.
For example, the addressing of array subscripts, a pair of subscripts exchange.
-
Constant Operating Quantity
For a single constant time operation, write O(1). Read big O 1.
-
Computation of Time Complexity
In the method, the number of repeated executions of basic operations is a function of the problem size n, which is expressed by T(n).
If there is a function, f (N). When N approaches infinity, T(n)/f(n) approaches a constant of not 0.
f(n) is the same order of magnitude function of T(n). T(n) = O (f(n). O (f(n) is the asymptotic time complexity of the algorithm.
-
Linear time complexity
For example, an algorithm needs to perform N cycles, each of which is a constant operation O(1).
for i in 1..<N+1 { //Constant operation let firstItem = arr[i-1] let secondItem = arr[i] if firstItem > secondItem { arr.swapAt(i-1, i) } }
T(N)=F(N)=N, time complexity is O (F (N) = O (N).
-
Time Complexity of Constant Operational Expression Types
For the time complexity of T(N) as an expression type, F(N) is simply to simplify it into an expression that has the greatest impact on N when it approaches infinity.
Specifically speaking. In the expression of constant number of operations, as long as the higher order term, not the lower order term, and not the coefficients of the higher order term, the remaining part if recorded as f(N), then the time complexity is O (f(N).
To borrow examples from Baidu Encyclopedia:
for(i=1; i<=n; ++i) { c[i];//This step belongs to the number of basic operations performed:n for(j=1; j<=n; ++j) { c[i][j] = 0;//This step belongs to the basic operation execution times: n square times. for(k=1; k<=n; ++k) c[i][j] += a[i][k] * b[k][j];//This step belongs to the number of times the basic operation is executed: the third power of n. } }
T(N) = A*N_+B*N_+C*N. When N approaches infinity, the influence of cubic power is much greater than that of quadratic power and primary power. Of course, it is also greater than the effect of constant term A.
So the expression f(N)=N.
Time complexity is O(N)=O(f(N)=O(N)=N_
A diagram is attached to facilitate understanding the changes of higher order items when the cardinality increases:
![](/images/doc/e8350fa938ab35f2f86041991348ed10.jpg)
-
Comparisons with the same time complexity
To evaluate the performance of an algorithm process, first look at the time complexity index, and then sub-divide it.
The actual running time under different data samples is analyzed, that is, the constant term time.
Bubble sort
In the bubble sorting process, the array will be divided into two parts, the first half is an unordered sequence, and the second half is an ordered sequence. The largest value in an unordered sequence is constantly bubbling into an ordered sequence. After bubbling, our sequence is created.
Specifically, if the two adjacent digits are larger, the two digits are exchanged and stop when they reach the boundaries of the disordered array.
![](/images/doc/159a7606367b011899f6d56287324ac7.jpg)
func bubbleSort(arr: inout [Int]) { if arr.count < 2 { return } for i in 0..<arr.count { for j in 0..<arr.count - (i+1) { if arr[j] > arr[j+1] { let temp = arr[j] arr[j] = arr[j+1] arr[j+1] = temp } } } }
Time complexity O(N_) and extra space complexity O(1).
The source of time complexity f (N) = N + (N-1) + (N-2) +... + 2 + 1 is one Arithmetic progression . The general formula of the sum of the first N terms is: N*(N-1)/2 simplified f(N)=N_.
-
Improved Bubble Sorting
The classic bubble sort, whether or not the array has been ordered. We can improve on this point by traversing it over and over again.
func bubbleSort2(arr: inout [Int]) { if arr.count < 2 { return } var swapped = false //Record whether there are variables for swapping actions for i in 0..<arr.count { swapped = false for j in 0..<arr.count - (i+1) { if arr[j] > arr[j+1] { let temp = arr[j] arr[j] = arr[j+1] arr[j+1] = temp swapped = true //Record switching actions } } if swapped == false { break //There is no exchange action, indicating that there is order. } } }
In extreme cases (for an already ordered array), the algorithm returns after completing the first outer loop.
In fact, only N - 1 Comparisons occur, so in the best case, the complexity of the algorithm is O(N).
Selection sort
The basic idea is the same as bubble sort. The first half is an ordered sequence, but the second half is an unordered sequence. The largest value in an unordered sequence is constantly bubbling into an ordered sequence. After bubbling, our sequence is created.
Specifically, each iteration records the position of the minimum value in the disordered sequence, and at the end of the iteration, it exchanges with the first position of the disordered sequence to make it the last position of the ordered sequence.
![](/images/doc/cb6955ea41aef436660cf0e58f8d31b4.jpg)
func selectionSort(arr : inout [Int]) { if arr.count<2 { return } var minIndex :Int for i in 0..<arr.count { minIndex = i for j in i+1..<arr.count { //The loop starts with i+1, which is the second bit of the unordered array. minIndex = arr[j]<arr[minIndex] ? j:minIndex //Comparing the current position with the recorded position, the record is the smallest. } arr.swapAt(i, minIndex) //Exchange the first and the smallest bit of an unordered array } }
-
Binary Selective Sorting
There's nothing to improve on the selection sort itself, but we can open the bow left and right.
The sequence is divided into three parts: the ordered part of the front segment, the disordered part of the middle segment and the ordered part of the back end.
In each cycle, the maximum and minimum values are placed in two ordered sequences.
func selectionSort2(arr : inout [Int]) { if arr.count<2 { return } var minIndex :Int var maxIndex :Int for i in 0..<arr.count { minIndex = i maxIndex = i if i+1 >= arr.count - i { return // Because of this step, the loop actually ends at i=arr.count/2. } for j in i+1..<arr.count - i { //The loop starts with i+1, which is the second bit of the disordered array. And stop at the front of the back-end ordered sequence minIndex = arr[j]<arr[minIndex] ? j:minIndex //Comparing the current position with the recorded position, the record is the smallest. maxIndex = arr[j]>arr[maxIndex] ? j:maxIndex //Comparing the current position with the recorded position, the record is the largest. } if maxIndex == i && minIndex == arr.count - (i+1) { //If the maximum and minimum are exactly at the boundary, direct exchange can lead to disorder. Manual assignment is required let maxValue = arr[maxIndex]; let minValue = arr[minIndex]; let maxToValue = arr[arr.count - (i+1)] let minToValue = arr[i] arr[maxIndex] = maxToValue arr[arr.count - (i+1)] = maxValue arr[minIndex] = minToValue arr[i] = minValue }else if maxIndex == i{ //If the maximum is in the position where the minimum is to be exchanged, the maximum is exchanged first. arr.swapAt(arr.count - (i+1) , maxIndex) //Exchange the last bit of an unordered array with the largest bit arr.swapAt(i, minIndex) //Exchange the first and the smallest bit of an unordered array }else { arr.swapAt(i, minIndex) //Exchange the first and the smallest bit of an unordered array arr.swapAt(arr.count - (i+1) , maxIndex) //Exchange the last bit of an unordered array with the largest bit } } }
In this way, although the complexity is O(N), in fact, the expression coefficients are more than 1/2 smaller than the classical selection ranking.
Insertion sort
The basic idea is that the first half is ordered, and the second half is disordered. The disordered sequence continuously pushes its first element to the ordered sequence, and the ordered sequence inserts it into the appropriate position.
Specifically, it will be compared from the end of the ordered sequence, and exchanged if the front bit is larger than the rear bit.
![](/images/doc/c833de7202dab446601fae9c103bfb6b.jpg)
func insertionSort(arr : inout [Int]) { if arr.count<2 { return } for i in 1..<arr.count { //Unordered arrays from i=1 to the end for j in (0...i-1).reversed() { //Cycling in an ordered array from i-1 to 0 if arr[j+1] > arr[j] { //j+1 is at the top of an unordered array when it is first executed break //If the back position is larger than the front position, the order is indicated. Exit the current loop } arr.swapAt(j, j+1)//Otherwise exchange } } }
If it's improved, maybe you can try to determine the specific position by dichotomy and then move the whole back and insert it.
Worst case, best case, average case of time complexity
For insertion sort, which has definite termination conditions, the actual time complexity is related to the actual situation of the data.
Best of all, it's orderly at the beginning. We only need to perform a large loop with O(N) complexity.
The worst case is that the entire array is arranged in reverse order once with O(N_) complexity.
Average case refers to the average expected complexity in most cases.
When the actual situation of the data has an impact on the algorithm process, the worst case is used as the time complexity.
However, we can take advantage of active disruption of the impact of data conditions. Express the complexity in a way that is easily mathematically desirable (refer to random fast scheduling).
Logarithmic device
Logger is used to test the correctness of code. When we can't find a suitable oj system to test our own code, we can write a logger to test the code ourselves.
-
The general steps for designing logarithms are:
1. Have a method you want to test a; write your own method
2. Implement an absolutely correct method even if the complexity is not good b; the system can bring its own method.
3. Implement a random sample generator.
4. The method of realizing the comparison; whether the two results are consistent in the end
5. Compare method a with method b many times to verify that method a is correct.
6. If there is a sample that makes the alignment wrong, which method does the printed sample analysis make a mistake?
7. When the number of samples is large, the comparison test is still correct, which can confirm that method a is correct.
-
Realize logarithm
One, two and four of them have already been said. There's nothing to say about 6 and 7.
3. Implementing a Random Sample Generator
/// Random Array Generator /// /// - Parameters: ///- size: maximum length ///- value: Maximum ///- Returns: Random Array func generateRandomArray(size : Int ,value : Int) -> [Int] { var arr :[Int] arr = Array.init() for i in 0..<Int(arc4random() % 10) * size / 10 { let item = Int(arc4random() % 10)*value/10 arr.append(item) } print(arr) return arr }
-
Compare method a with method b many times to verify that method a is correct.
var checkOK = true for i in 0..<10000 { var arr1 = generateRandomArray(size: 5, value: 20) var arr2 = arr1 //Arrays are of value type in swift, and assignment actions copy automatically let originalArr = arr1 arr1.sort() heapSort(arr: &arr2) if arr1 != arr2 { checkOK = false print(originalArr) print(arr2) break } } print(checkOK ? "Comparison success":"Comparison failure") //Printing [0, 6, 2, 12, 18] [0, 6, 12, 2, 18] //Comparison failure
The wrong raw data has been printed out, and you can reproduce it at will for debugging.
var arr = [0, 6, 12, 2, 18]; print(arr) heapSort(arr: &arr) print(arr)
Reference material
Zuo Shenniu Course Network Algorithms Course
A Simple Explanation of Time Complexity and Space Complexity
Selection and Sorting and Improvement Method