Algorithm: An ordered set of well-defined steps that produce results and terminate in a finite amount of time.

Tools: UML, pseudocode, and structure diagrams. UML(Unified Modeling Language) is a graphical representation of algorithms; Pseudocode is an English-like representation of an algorithm; Structure diagrams are high-level design tools that show the relationships between algorithms and subalgorithms.

Common algorithms: sum, product, minimize and maximize, sort and find.

The basic sorting algorithm: selection sort, bubble sort and insert sort.

Search algorithm: sequential search and split search (binary search). A sequential lookup is a search for a target item in any list, while a split lookup is a search for a sorted list.

Methods: There are two ways to write an algorithm to solve a problem. One is iteration; The other is recursion.

The complexity of the

Time complexity: Used to measure the running time of the algorithm, denoted as T(n) = O(f(n)). It means that with the increase of input size n, the growth rate of algorithm execution time can be described by f(n). T(n) is the time frequency. Time frequency refers to the number of statements executed in an algorithm.

For a loop, assuming that the time complexity of the loop body is O(n) and the number of cycles is m, the time complexity of the loop is O(n×m).

It’s not difficult to get the time complexity from the number of executions T(n), but a lot of times it’s difficult to get T(n) from the algorithm through analysis and math. Here are four convenient rules, all of which can be easily derived and summarized to improve efficiency.

function aFunc(int n) { for(int i = 0; i < n; I++) {// loop n console.log("Hello, World! \n"); // Loop body time complexity is O(1)}}Copy the code

In this case, the time complexity is O(n × 1), that is, O(n).

function aFunc(int n) { for(int i = 0; i < n; I++) {// for(int j = 0; j < n; J++) {// loop n console.log("Hello, World! \n"); // Loop body time complexity is O(1)}}}Copy the code

The time complexity is O(n × n × 1), that is, O(n^2).

function aFunc(int n) { for (int i = 0; i < n; i++) { for (int j = i; j < n; j++) { console.log("Hello World\n"); }}}Copy the code

The inner loop performs n operations when I = 0, and n-1 operations when I = 1… When I = n-1, the inner loop performs one operation. So, the number of executions T(n) = n + (n-1) + (n-2)…… Plus 1 is n times n plus 1 over 2 is n squared over 2 plus n over 2. According to the big O derivation above, the time complexity is O(n^2).

function aFunc(int n) { for (int i = 2; i < n; i++) { i *= 2; console.log("%i\n", i); }}Copy the code

If the number of cycles is t, then the cycle condition satisfies 2^t < n. It can be concluded that the execution times t = log(2)(n), that is, t (n) = log(2)(n), the time complexity is O(log(2)(n)), that is, O(log n).

Spatial complexity

Definition: It is a measure of the storage space temporarily occupied by an algorithm during its running. It also reflects a trend and is defined by S(n). Let’s call it S(n)=O(f(n)) space complexity is how much memory the program takes up when running, not the size of the executable file.

int j = 0;
for (int i = 0; i < n; i++) {
    j++;
}
Copy the code

In the first code, we can see that as n changes, the amount of memory required does not change as n changes. That is, the spatial complexity of this algorithm is a constant, so it is expressed as big O(1).

let m = new Array[n]
for(i=1; i<=n; ++i)
{
   j = i;
   j++;
}
Copy the code

The first line is a new array, which occupies n(n elements). Lines 2-6 of this code are looping, but no new space is allocated. Therefore, the space complexity of this code is mainly based on the first line, that is, S(n) = O(n).

The complexity of array sorting algorithms