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 k-order 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 [N-1] for non decreasing sort*/
	for(i=0; i<N; i++)
	{
		/*Find the smallest element from List[i] to List[N-1] and assign its position to MinPosition*/
		MinPosition = ScanForMin(List, i, N-1);
		/*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, N-1);
		
		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 j-1 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, N-1);
}

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; 
}