Concepts of algorithms

An Algorithm is the essence of how a computer processes information, because a computer program is essentially an Algorithm that tells the computer the exact steps to perform a given task. Typically, when an algorithm processes information, it reads the data from the input device or the storage address of the data and writes the results to the output device or a storage address for later invocation.

Algorithm is an independent method and idea to solve problems.

Algorithms can have different language description implementation version (such as C, C++, Python, Java description, etc.), for the algorithm, the implementation of the language is not important, important is the idea.


Five features of the algorithm

  1. Input: The algorithm has zero or more inputs.
  2. Output: The algorithm has at least one or more outputs.
  3. Fineness: The algorithm terminates automatically after a finite number of steps rather than an infinite loop, and each step can be completed in an acceptable amount of time.
  4. Deterministic: Each step in the algorithm has a definite meaning, without ambiguity.
  5. Feasibility: Each step of the algorithm is feasible, that is, each step can be performed a limited number of times.


Requirements for algorithm design

Correctness: The algorithm should at least have unambiguous input, output and processing, reflect the needs of the problem, and get the correct answer to the problem.

Readability: Algorithms are also designed to be easy to read, understand, and communicate.

Robustness: When the input data is invalid, the algorithm can also do relevant processing, rather than producing abnormal or unintelligible results.

High time efficiency and low storage:

Time efficiency refers to the execution time of the algorithm, and storage requirement refers to the storage space required by the algorithm during its execution. The design algorithm should meet the requirements of high time efficiency and low storage as far as possible.


Algorithmic efficiency measurement

1. Post-hoc statistics

This method through the design of good test procedures and data, and then run in the computer, and then compare the running time, time-consuming less efficient.

Performance time response algorithm efficiency

For the same problem, we provide two solutions. In the realization of the two algorithms, we measure the execution time of the program and find that the execution time of the two programs is significantly different (214.583347 seconds compared with 0.182897 seconds). Therefore, we can draw the conclusion: The execution time of the algorithm program can reflect the efficiency of the algorithm, that is, the merits of the algorithm.

Is time value alone absolutely reliable?

What if we ran our second attempt at algorithmic programming on a computer with an ancient configuration and poor performance? It probably won’t run much faster than the 214.583,347 seconds it took to run Algorithm one on our computer.

It is not necessarily accurate to compare algorithms only by running time!

The program cannot run without the computer environment (including hardware and operating system). These objective reasons will affect the speed of the program and reflect in the execution time of the program. Obviously, this approach has major drawbacks. First, it takes time to design the test data of the algorithm, because different test data often directly affects the running time, and then the hardware of the computer also affects the running time. This results in erratic measurements.


2. Prior analysis

Thus, the prior analysis method was born, which can analyze the efficiency of an algorithm without running a program.

After extensive analysis, predecessors concluded that the time an algorithm takes to run on a computer depends on the following factors:

1. Strategies and methods adopted by the algorithm

2. Quality of code generated by compilation

3. The input scale of the problem

4. The machine executes at the specified speed


3. Time Complexity and “Big O notation”

We assume that the computer takes a fixed unit of time to perform each basic operation of the algorithm, so the number of basic operations represents the number of units of time it will take. Although the exact unit time is different for different machine environments, the number of basic operations performed by the algorithm (i.e. how many units of time are spent) is of the same order of magnitude. Thus, the time efficiency of the algorithm can be objectively reflected by ignoring the influence of the machine environment.

For the time efficiency of the algorithm, we can use “big O notation” to express it.

“Big O notation” : For monotone integer function f, if there is an integer function g and a real constant C >0, such that for sufficiently large n there is always f(n)<= C *g(n), the function g is said to be an asymptotic function of F (ignoring the constant), denoted by f(n)=O(g(n)). In other words, in the limit as it approaches infinity, the growth rate of f is constrained by g, that is, f and G have similar characteristics.

Time complexity: Suppose there is A function G, so that T(n)=O(g(n)) is taken by algorithm A to process the sample problem of size N, then O(g(n)) is called the asymptotic time complexity of algorithm A, which is referred to as time complexity and denoted as T(n).

How to understand “Big O notation”

A particularly detailed analysis of algorithms is fine, but of limited practical value in practice. For the temporal and spatial properties of the algorithm, the most important are its order of magnitude and trend, which are the main part of analyzing the efficiency of the algorithm. The constant factors in the scale function of the basic number of operations of the metering algorithm can be ignored. For example, you can consider 3n² and 100n² to be of the same magnitude, and if two algorithms deal with instances of the same size at the cost of these two functions, they are considered to be “about the same” efficient, both of order N ².


4. Worst time complexity

When analyzing the algorithm, there are several possible considerations:

  • The minimum number of basic operations required by the algorithm to complete its work, that is, the optimal time complexity
  • The maximum number of basic operations an algorithm needs to complete its work, i.e. the worst time complexity
  • How many basic operations does the algorithm need on average to complete its work, that is, the average time complexity

For the optimal time complexity, its value is not much, because it provides no useful information, it only reflects the most optimistic and ideal situation, there is no reference value.

For the worst time complexity, it provides a guarantee that the algorithm will perform its job at this level of basic operation.

As for the average time complexity, it is a comprehensive evaluation of the algorithm, so it completely reflects the nature of the algorithm. On the other hand, this measurement does not guarantee that not every calculation will be done within this basic operation. Moreover, the calculation of the average case is also difficult to calculate because the distribution of instances of the applied algorithm may not be uniform.

Therefore, we focus on the worst-case, or worst-time complexity, of the algorithm.


Some basic calculation rules of time complexity

  1. The basic operation, which has only constant terms, is considered O(1) in time complexity.
  2. Sequential structure, time complexity is calculated by addition.
  3. Cyclic structure, time complexity is calculated by multiplication.
  4. Branch structure, maximum time complexity.
  5. When judging the efficiency of an algorithm, only the highest order term of the number of operations is concerned, and other minor terms and constant terms can be ignored
  6. In the absence of special instructions, the time complexity of the algorithms we analyze refers to the worst time complexity.


Program, for example,

1. Constant order

 void main(a){
	int sum = 0,n = 100;
	sum = (1 + n) * n / 2;
	printf("%d",sum);
}
Copy the code

At this time, according to the conclusion, all addition constants are replaced by constant 1 without the highest order term, so the time complexity of the algorithm is O(1).


2. Linear order

void main(a){
	int i,sum = 0,n = 100;
	for(i = 1; i <= n; i++){ sum += i; }printf("%d",sum);
}
Copy the code

The number of executions is 1 + (n + 1) + n + 1 = 2n + 3. According to the conclusion, the addition constant is replaced by constant 1, and 3 is replaced by 1. The highest order term 2n is retained and the constant multiplied by the highest order term is removed, so the time complexity of the algorithm is O(n).

In fact, we do not need to calculate The Times of execution of each line of code in this way. For assignment, loop conditions and output statements, we can directly ignore them, so we can directly conclude that the time complexity of this algorithm is O(n).


Logarithmic order

void main(a){
    int count = 1;
    while(count < n){
        count *= 2; }}Copy the code

In this program, we just need to count the number of cycles to figure out the time complexity, because every time we multiply count by 2, we get one point closer to n, in other words, how many 2’s are greater than n before we get out of the loop. From 2x = n, x=log2nx =log2 ^nx=log2n, so the time complexity of the algorithm is O(logn).


4. Square order

void main(a){
    int i,j,n = 100;
    for(i = 0; i < n; i++){for(j = 0; j < n; j++){printf("%d\t",n); }}}Copy the code

We know that for the inner loop, the time complexity is O(n), while the outer loop only executes the inner loop n times, so the algorithm’s time complexity is O(n2)O(n^2)O(n2).


Common time complexity

Example of a number of times function order Informal terms

12 12
O ( 1 ) O(1) 		Constant of the order

2 n + 3 2n+3
O ( n ) O(n) 		Linear order

3 n squared + 2 n + 1 3 n squared + 2 n + 1
O ( n 2 ) O(n^2) 		Square order

5 l o g 2 n + 20 5log2^n+20
O ( l o g n ) O(logn) 		The logarithmic order

2 n + 3 n l o g 2 n + 19 2n+3nlog2^n+19
O ( n l o g n ) O(nlogn) 		Nlogn order

6 n 3 + 2 n 2 + 3 n + 4 6n^3+2n^2+3n+4
O ( n 3 ) O(n^3) 		Cubic order

2 n 2^n
O ( 2 n ) O(2^n) 		The index order

Note that often will
l o g 2 n log2^n Log base two is logn


Relationships between common time complexity

The commonly used time complexity takes up the following order of time:


O ( 1 ) < O ( l o g n ) < O ( n ) < O ( n l o g n ) < O ( n 2 ) < O ( n 3 ) < O ( 2 n ) < O ( n ! ) < O ( n n ) O(1) < O(logn) < O(n) < O(nlogn) < O(n^2) < O(n^3) < O(2^n) < O(n!) < O(n^n)

Exponential order O(2n)O(2^n)O(2n) and factorial order O(n!) O(n!) O(n!) Unless it’s a very, very small value of n, even n of 100 is a nightmare running time. So we’re not going to talk about the time complexity of these unrealistic algorithms.


Spatial complexity

With the development of Internet technology, storage that used to be expensive is now cheaper, so in certain scenarios, you can consider using space to trade for time.

The spatial complexity of the algorithm is realized by calculating the storage space required by the algorithm. The calculation formula of the spatial complexity is as follows: S(n) = O(f(n)), where N is the size of the problem and f(n) is the function of the statement regarding the storage space occupied by n.

In general, we pay more attention to the time complexity of the algorithm, so the spatial complexity is only an understanding.


A profound

If a plus b plus c is equal to 1000, and
a 2 + b 2 = c 2 a^2 + b^2 = c^2 (A,b,c are natural numbers)

Design the program to find all possible combinations of A, B, and C?

What is the time complexity of the program?


The source code

The source code has been uploaded to GitHub data-structure-of-C, welcome to visit.

✍ code word is not easy, the long journey always feeling, praise again go line, also hope you heroes support ❤️