Algorithm
algorithm
 A finite instruction set
 Accept some input (in some cases, no input is required)
 Generate output
 Must terminate after limited steps
 Each instruction must:
There are fully clear objectives, and there can be no ambiguity
Within the range of computer processing
The description shall not depend on any computer language and specific implementation means
What is a good algorithm?
When analyzing the efficiency of general algorithms, we often pay attention to the following two complexities:
 Worst case complexity Tworst(n)
 Average complexity Tavg(n)
 Tavg(n) <= Tworst(n)
Space complexity s (n)  space

The program written according to the algorithm occupies the length of the storage unit when executing.
This length is often related to the size of the input data. 
An algorithm with too high space complexity may cause the memory used to exceed the limit, resulting in abnormal program interruption.
Time complexity T (n)  time
 The length of time spent in the execution of a program written according to an algorithm.
This length is often related to the size of the input data.  Inefficient algorithms with high time complexity may cause us to wait for running results in our lifetime.
Progressive representation of complexity
 T(n)=O(f(n)) indicates that there are constants C > 0 and N0 > 0, so that when n > = N0, there is t (n) < = C * f (n)
(for sufficiently large N, O(f(n)) means that f(n) is some upper bound of T(n))  T(n) = Ω (g(n)) indicates that there are constants C > 0 and N0 > 0, so that when n > = N0, there is T(n) > = C * g (n)
g(n) is a lower bound of T(n)  T(n)= Θ (h(n)) indicates that there are both T(n)=O(h(n)) and t (n) = Ω (h(n))
Indicates that there are both upper and lower bounds, and they are equivalent
Complexity analysis tips
 When analyzing, we should find: the smallest upper bound and the largest next bound
 If the two algorithms have complexity T1(n)=O(f1(n)) and T2(n)=O(f2(n)), then:
T1(n)+T2(n)=max(O(f1(n)), O(f2(n)));
T1(n)xT2(n)=O(f1(n) x f2(n));  If T(n) is a korder polynomial about n, then T(n)= Θ (nk)
When n is large enough, only the item with the largest order works, and the other items can be ignored  The time complexity of a for loop is equal to the number of loops multiplied by the complexity of the loop body code
 The complexity of if else structure depends on the conditional judgment complexity of if and the complexity of two branches. The overall complexity is the largest of the three
Select Sorting Algorithm
 Pseudo code description
void SelectionSort (int List[], int N) { /*List N integers [0] List [N1] for non decreasing sort*/ for(i=0; i<N; i++) { /*Find the smallest element from List[i] to List[N1] and assign its position to MinPosition*/ MinPosition = ScanForMin(List, i, N1); /*Change the smallest element of the unordered part to the last position of the ordered part*/ Swap(List[i], List[MinPosition]); } }
 Valid code
#include <stdio.h> #define NUM 10 int ScanForMin (int List[], int i,int N) //Find the smallest element of the unordered part { int j; int min = i; for(j=i+1; j<=N; j++) { if(List[j] < List[min]) { min = j; } } return min; } void Swap(int List[], int i, int MinPosition) //Change the smallest element of the unordered part to the last position of the sorted part { int temp; temp = List[i]; List[i] = List[MinPosition]; List[MinPosition] = temp; } void SelectionSort (int List[], int N) //Select sort function { int i; int MinPosition = 0; for(i=0; i<N; i++) { MinPosition = ScanForMin(List, i, N1); Swap(List, i, MinPosition); } } int main(void) { int a[NUM] = {89,123,4,23,18,7,45,3,33,66}; int i; SelectionSort(a,NUM); for(i=0; i<NUM; i++) { printf("%d ", a[i]); } printf("\n"); return 0; }
Find the maximum continuous sub column sum (multiple for loops)
Algorithm 1: T(N) = O(N3)
int MaxSubseqSum1(int A[], int N) { int ThisSum, MaxSum=0; int i, j, k; for(i=0; i<N; i++) //i is the left end of the child column { for(j=i; j<N; j++) // j is the right end of the child column { ThisSum=0; //ThisSum is the sum of the child columns from A[i] to A[j] for(k=i; k<=j; k++) { ThisSum += A[k]; } if(ThisSum > MaxSum)//If the sum of the just obtained sub column is larger { MaxSum = ThisSum; //The results are updated } }//j end of cycle }//i end of cycle return Max }
Algorithm 2: T(N) = O(N2)
int MaxSubseqSum2(int A[], int N) { int ThisSum, MaxSum=0; int i, j; for(i=0; i<N; i++) //i is the left end of the child column { ThisSum=0;//ThisSum is the sum of the child columns from A[i] to A[j] for(j=i; j<N; j++) //j is the right end of the child column { ThisSum += A[j]； //For the same i and different j, just add one term on the basis of j1 cycles if(ThisSum>MaxSum) //If the sum of the just obtained sub column is larger { MaxSum=ThisSum; //The results are updated } }//j end of cycle }//i end of cycle return MaxSum; }
Algorithm 3: divide and conquer T(N) = O(N*LogN)
 The basic idea is to divide the original problem into several small problems, solve them separately, and then combine the results to cure them. It is very convenient to implement it recursively.
int Max3(int A, int B, int C) { return A>B?A>C?A:C:B>C?B:C; } int DivideAndConquer(int List[], int left, int right) { //Divide and conquer to find the maximum sum of sub columns from List[left] to List[right] int MaxLeftSum, MaxRightSum; //Solution of left and right subproblems int MaxLeftBorderSum，MaxRightBorderSum; //Store results across boundaries int LeftBorderSum, RightBorderSum; int center, i; if(left==right)//Recursive termination condition, the sub column has only 1 number { if(List[left]>0) { return List[left]; } else { return 0; } } //The following is the process of "dividing" center=(left+right)/2; //Find the midpoint //Recursively find the maximum sum of two sub columns MaxLeftSum=DivideAndConquer(List, left, center); MaxRightSum=DivideAndConquer(List, center+1, right); //Next, find the maximum sum of sub columns across the boundary MaxLeftBorderSum=0; LeftBorderSum=0; for(i=center; i>=left; i) { LeftBorderSum += List[i]; if(LeftBorderSum>MaxLeftBorderSum) { MaxLeftBorderSum=LeftBorderSum; } } //Left scan end MaxRightBorderSum=0; RightBorderSum=0; for(i=center+1; i<=right; i++) //Scan right from midline { RightBorderSum += List[i]; if(RightBorderSum>MaxRightBorderSum) { MaxRightBorderSum= RightBorderSum; } } //Right scan end //The result of "governance" is returned below return Max3(MaxLeftSum, MaxRightSum, MaxLeftBorderSum+MaxRightBorderSum); } int MaxSubseqSum3(int List[], int N) { //Maintain the same function interface as the first two algorithms return DivideAndConquer(List, 0, N1); }
Algorithm 4: online processing T(N)= O(N)
"Online" means that every time a data is input, it will be processed immediately. If the input is terminated anywhere, the algorithm can correctly give the current solution.
int MaxSubseqSum4(int A[], int N) { int ThisSum, MaxSum; int i; ThisSum=MaxSum=0; for(i=0; i<N; i++) { ThisSum += A[i]; //Right accumulation if(ThisSum > MaxSum) { MaxSum = ThisSum; //If a larger sum is found, the current result is updated } else if(ThisSum < 0) //If the current child column sum is negative { ThisSum = 0; // It is impossible to enlarge the rear part and discard it } } return MaxSum; }