Original link: blog.csdn.net/weixin_3964…
First, algorithm concept
An algorithm is a description of the steps to solve a particular problem. It does not depend on any language, can be described by natural language, programming language, flow chart, block diagram.
Second, the characteristics of
- Finiteness: An algorithm is a finiteness sequence of instructions that always ends after a number of executions.
- Deterministic: Each statement has a definite meaning without ambiguity.
- Feasibility: The algorithm can be implemented by a finite number of operations in the current environment.
- Input output: having zero or more inputs, one or more outputs.
Good algorithms
- Correctness: Correctness means that the algorithm can meet the requirements of specific problems, the program runs normally without syntax errors, and can pass typical software tests to meet the expected requirements.
- Legibility: The algorithm follows the naming rules of identifiers, is concise and easy to understand, and the annotation language is appropriate and appropriate, which is convenient for reading by oneself and others, and for debugging and modification in the later stage.
- Robustness: The algorithm has good response and processing to illegal data and operations.
- High efficiency: High operating efficiency, that is, short running time of the algorithm. The time complexity of an algorithm is the time it takes to run an algorithm.
- Low storage: The storage space required by the algorithm is low. Algorithm space complexity is the size of the algorithm space.
4. Time complexity
The execution time of an algorithm is proportional to the number of statements executed in the algorithm. The number of statements executed in the algorithm is called statement frequency or time frequency, denoted by T(n).
// sum=0; // Run 1 time total=0; // Run for(I =1; i<=n; I ++) {sum=sum+ I; // Run n times for(j=1; j<=n; J ++) // Run n*n times total=total+ I *j; } T (n) = 1+1+n+n+n*n+n*n = 2n^2+2n+2Copy the codeIn general, the number of repeated basic operations in the algorithm is a function of the problem size N, expressed by T(n). If there is some auxiliary function F (n), such that the limit value of T(n)/f(n) is a constant that is not equal to zero when n approaches infinity, then F (n) is said to be a function of the same order of magnitude as T(n). Let T(n) = O(f(n)), and call O(f(n)) the asymptotic time complexity of the algorithm, or time complexity for short. Such as:
//算法二
i=1; //运行1次
while(i<=n) //可假设运行x次
{
i=i*2; //可假设运行x次
}
Copy the codeIn the above column, we cannot immediately determine how many times while and I = I * 2 are executed. After each operation, I is 2, 222^222… 2×2 to the x2x, ends when I is equal to n, ends when 2×2 to the x2x is equal to n, so x is equal to log base 2n. The time complexity is O(f(n)) = O(log2n).
5. Spatial complexity
Space complexity is a measure of the amount of storage space temporarily occupied by an algorithm during its running. The space an algorithm takes up on a computer consists of three parts:
- Input/output data
- The space taken up by the algorithm itself
- Additional auxiliary space required
Swap (int x, int y) //x and y swap {int temp; temp=x; //temp is the auxiliary space x=y; y=temp; }Copy the codeThis algorithm uses only one auxiliary variable, namely constant, so the space complexity is O(1).
6. Case analysis
Sample code:
decimal Factorial(int n) { if (n == 0) return 1; else return n * Factorial(n - 1); Example code: int FindMaxElement(int[] array) {int Max = array[0]; for (int i = 0; i < array.Length; i++) { if (array[i] > max) { max = array[i]; } } return max; }Copy the codeHere, n is the size of array, so in the worst case, n comparisons are needed to get the maximum, so the time complexity is O(n). Only one auxiliary variable Max is used, so the space complexity is O(1).
Sample code:
long FindInversions(int[] array)
{
long inversions = 0;
for (int i = 0; i < array.Length; i++)
for (int j = i + 1; j < array.Length; j++)
if (array[i] > array[j])
inversions++;
return inversions;
}
Copy the codeHere, n is the size of array, so the number of basic steps is about N *(n-1)/2, so the time complexity is O(n2). No auxiliary space is used and the space complexity is O(1).
Sample code:
long SumMN(int n, int m)
{
long sum = 0;
for (int x = 0; x < n; x++)
for (int y = 0; y < m; y++)
sum += x * y;
return sum;
}
Copy the codeGiven size n and m, the number of basic steps is n*m, so the time complexity is O(n2). The space complexity is O(1).
Sample code:
decimal Sum3(int n)
{
decimal sum = 0;
for (int a = 0; a < n; a++)
for (int b = 0; b < n; b++)
for (int c = 0; c < n; c++)
sum += a * b * c;
return sum;
}
Copy the codeThen, the number of basic steps is about NNN, the time complexity is O(n3), and the space complexity is O(1).
Sample code:
decimal Calculation(int n)
{
decimal result = 0;
for (int i = 0; i < (1 << n); i++)
result += i;
return result;
}
Copy the codeThe number of basic steps is 2n2^n2n, so the time complexity is O(2n2^n2n) and the space complexity is O(1).
Sample code:
Fib (0) = 1; Fib of 1 = 1; Fib of n = fib of n minus 1 plus fib of n minus 2; n > 2 int Fibonacci(int n) { if (n <= 1) return n; else return Fibonacci(n - 1) + Fibonacci(n - 2); }Copy the codeThe time required to compute Fib of n is the sum of the time required to compute Fib of n minus 1 and the time required to compute Fib of n minus 2. T(n<=1) = O(1) T(n) = T(n-1) + T(n-2) + O(1) In the worst case is a full binary tree with 2n−1 −1 executions, so the time complexity is O(2n2^n2n). Space complexity depends on depth, so space complexity is O(n).
Sample code:
int Fibonacci(int n) { if (n <= 1) return n; else { int* f = new int[n + 1]; f[0] = 0; f[1] = 1; for (int i = 2; i <= n; i++) { f[i] = f[i - 1] + f[i - 2]; } return f[n]; }}Copy the codeFor the same Fibonacci sequence, we use the array F to store the calculation results, so that the time complexity is optimized to O(n) and the space complexity is optimized to O(n).
Sample code:
int Fibonacci(int n) { if (n <= 1) return n; else { int iter1 = 0; int iter2 = 1; int f = 0; for (int i = 2; i <= n; i++) { f = iter1 + iter2; iter1 = iter2; iter2 = f; } return f; }}Copy the codeThe same Fibonacci sequence, since only the first two results are actually useful, we can use intermediate variables to store, so that we do not need to create an array to save space. Similarly, the time degree optimization of the algorithm is O(n) and the space complexity is O(1).
Sample code:
static int Fibonacci(int n) { if (n <= 1) return n; int[,] f = { { 1, 1 }, { 1, 0 } }; Power(f, n - 1); return f[0, 0]; } static void Power(int[,] f, int n) { if (n <= 1) return; int[,] m = { { 1, 1 }, { 1, 0 } }; Power(f, n / 2); Multiply(f, f); if (n % 2 ! = 0) Multiply(f, m); } static void Multiply(int[,] f, int[,] m) { int x = f[0, 0] * m[0, 0] + f[0, 1] * m[1, 0]; int y = f[0, 0] * m[0, 1] + f[0, 1] * m[1, 1]; int z = f[1, 0] * m[0, 0] + f[1, 1] * m[1, 0]; int w = f[1, 0] * m[0, 1] + f[1, 1] * m[1, 1]; f[0, 0] = x; f[0, 1] = y; f[1, 0] = z; f[1, 1] = w; }Copy the codeAfter optimization, the time complexity is O(log2n) and the space complexity is O(1).