Algorithm analysis ideas

Analysis Framework

1. Use the algorithm input scale n as a parameter to analyze the algorithm efficiency

2. Time complexity: Find the basic operation O(1), and then calculate its number of runs (ignore the multiplication constant and only focus on the number of increases)

3. Number of increases: log2n

4. The worst, average and best efficiency all refer to the efficiency when the input size is n (the average efficiency can refer to the known push result)

Main summary analysis framework:

1. The time efficiency and space efficiency of the algorithm are measured as a function of the input size.

2. Use the number of execution times of the basic operations of the algorithm to measure time efficiency, and use the number of additional units consumed by the algorithm to measure the space unit

3. When the input scale is the same, the efficiency of written algorithms will be significantly different. For this type of algorithm, the worst, average and best efficiency need to be analyzed

4. The main concern of the framework is: its efficiency when the input scale tends to be infinite

Asymptotic notation and basic efficiency types

1. O(g(n)) is a set of functions with growth times

2. Ω(g(n)) is a set of functions with growth times >= c*g(n), lower order

3. θ(g(n)) is a set of functions with the number of growth = c*g(n), of the same order

You can use limits to compare the number of increases (Lópida's law)
The overall efficiency of the algorithm is determined by the part with larger growth times.

General scheme for mathematical analysis of non-recursive problems

1. Decide which parameter represents the metric of input size

2. Find out the basic operations of the algorithm

3. Check whether the number of executions of basic operations only depends on the input size. If it also depends on some other characteristics (for example: the position of the element in the array, etc.), analyze the worst, average and best efficiency

4. Establish a summation expression (possibly a recursive expression) of the number of execution times of the basic operation of the algorithm

5. Use standard operations or rules of summation operations to establish a closed formula for the number of operations, or at least determine its number of increments

General scheme for mathematical analysis of recursive problems

1. Decide which parameter represents the metric of input size

2. Find out the basic operations of the algorithm

3. Check whether the number of executions of basic operations only depends on the input size. If it also depends on some other characteristics (for example: the position of the element in the array, etc.), analyze the worst, average and best efficiency

4. Regarding the execution times of the basic operations of the algorithm, establish a recursive relationship and corresponding initial conditions.

5. Solve this recurrence, or at least determine its number of increments.

The above is the detailed content of Algorithm analysis ideas. For more information, please follow other related articles on the PHP Chinese website!