Questions about algorithm time complexity analysis

Who told you that the time complexity of analysis is measured in the number of comparisons?

The time it takes to execute an algorithm cannot be calculated theoretically, and it can only be known when you run tests on the computer. But it is not possible or necessary to test every algorithm on the machine, we just need to know which algorithm takes more time and which algorithm takes less time. And the time spent by an algorithm is proportional to the number of executions of statements in the algorithm.

The number of times a statement is executed in an algorithm is called statement frequency or time frequency. Denoted as t(n).

In general, the number of times the basic operation of the algorithm is repeated is a function f(n) of module n, so the time complexity of the algorithm is recorded as: t(n)=o(f(n)).

Analysis: With the increase of module n, the growth rate of algorithm execution time is proportional to the growth rate of f(n), so the smaller f(n), the lower the time complexity of the algorithm, and the higher the efficiency of the algorithm.

When calculating the time complexity, first find out the basic operation of the algorithm, then determine the number of its executions according to the corresponding statements, and then find the same order of magnitude as t(n) (its same order of magnitude is as follows: 1, log2n, n, nlog2n, n square, n cubic, 2 n power, n! ), f(n) = this order of magnitude, if t(n) f(n) finds the limit to obtain a constant c, then the time complexity t(n) = o(f(n)).

In general, time complexity is measured in terms of the most complex loop in your algorithm, such as one.

for(i = 0;i < n;i ++

for(j = 0;j < n;j ++

It doesn't matter how many solitary ones he has.

for(i = 0;i < n;i ++

His time complexity is o(n2).

It won't be o(n2) +o(n) +o(n) +o(2n)...Such.

For equations 3n 3+n 2+8n with a complexity of o(n 3), we only consider the effect of the highest number of terms on the value of the equation, and other statements such as variable assignment are calculated in the coefficients of n.

This kind of time complexity analysis is very coarse, and the real time complexity analysis is described by Turing machines.

The time complexity of an algorithm is a function that qualitatively describes the running time of the algorithm.

This is a function that represents the length of the string of the algorithm's input values. The time complexity is often expressed by the big o symbol, excluding the low-order term and the first coefficients of this function. In this way, the time complexity can be referred to as asymptotic, i.e., when the size of the input values approaches infinity.

What does the time complexity of the algorithm depend onThe time complexity of the algorithm depends on the state of the data to be processed and the size of the problem. An instruction in an algorithm describes a computation that, when run, can start with an initial state and (possibly empty) initial input, go through a finite and well-defined series of states, and finally produce an output and stop at a final state. The transition from one state to another is not necessarily definitive.

Some algorithms, including randomization algorithms, include some random inputs.

Here we only list some simple algorithm time complexity analysis.

The time complexity of a cycle is 0 (n).

The time complexity of the double cycle is 0 (n2

The time complexity of the triple cycle is 0 (n3

And so on. Let's take an example of a simple leakage list.

If you look at this, you can probably estimate how big the log is. Judge whether it is timed out according to the calculation speed of the evaluation machine.

int has a range of -2147483648 2147483647. Probably at 2 109

The range of long long is probably 1018

Some numbers should be noted to the power.

o(n!)、o(2n)、o(n

2)、o(nlogn)、o(n)、o(logn)、o(1)..

Representatives:Worst-case time.

The factorial of a positive integer is the product of all positive integers less than or equal to that number, and the factorial of 0 is 1. The factorial of the natural number n is written as n!. In 1808, Keystone Carman introduced this notation.

n to the nth power, is the meaning of superscript.

If a = n (a>0 and a ≠ 1), then the number x is called the logarithm of a base n, denoted as x=logan, read as the logarithm of a base n, where a is called the base of the logarithm and n is called the true number.

where x is the independent variable and the domain of the function is (0, + is x>0. It's actually the inverse of an exponential function, which can be expressed as x= a. Therefore, the definition of a in the exponential function also applies to the logarithmic function.

When describing the complexity of an algorithm, o(1), o(n), o(logn), and o(nlogn) are commonly used to represent the temporal complexity of the corresponding algorithm, which is the representation of the spatiotemporal complexity of the algorithm. It is used not only to represent temporal complexity, but also spatial complexity.

o There is a function in parentheses that indicates the relationship between the time and space consumed by an algorithm and the amount of data growth. where n represents the amount of input data.

The time complexity is o(n), which means that the amount of data increases by several times, and the time consumption also increases by several times, and increases linearly, such as the common :

The time complexity o(n 2) means that when the amount of data increases by n times, the time taken increases by a square multiple of n, which is a higher time complexity than linear. For example:

O(nlogn) is the same way, that is, n multiplied by logn, when the data is increased by 256 times, the time taken increases by 256 * 8 = 2048 times. This complexity is higher than linear and below squared. For example:

When the data is increased by n times, the time taken is increased by logn times (the log here is based on 2, for example, when the data is increased by 256 times, the time taken is only increased by 8 times, which is lower than the linear time complexity). For example:

o(1) is the lowest spatiotemporal complexity, that is, the time and space consumption is not related to the size of the input data, no matter how many times the input data is increased, the time and space consumption remains the same. For example:

Substituting the value after n, and the relationship between time and time10 8 = > seconds, the largest n are:

o(1) When the general time complexity reaches 2 n (exponential) and larger, we basically don't use such an algorithm, which is too impractical. For example, the recursive implementation of the Tower of Hanoi problem algorithm is o(2 n).

The square-order (n 2) algorithm is barely usable, while the nlogn and smaller time complexity algorithms are very efficient algorithms.

Spatial complexity.

Bubbling sorting, simple selection sorting, heap sorting, direct insertion sorting, the spatial complexity of Hill sorting is o(1) because a temporary variable is needed to swap the position of the element, (in addition, when traversing the sequence, it is indispensable to use a variable to do the index).

The quicksort space complexity is logn (because recursively called), and the merge sort space complexity is o(n) and requires a temporary array of size n.

The spatial complexity of cardinality sorting is o(n), and the spatial complexity of bucket sorting is uncertain. Original.

The execution frequency of ** is the number of executions of the loop statement in the loop, which is equal to 12+3+...n-1=n(n-1)/2

The time complexity is o(n 2).

Under normal circumstances, I think that if the algorithm time is complex, in this case, you can directly follow the three questions from the background, and this choice is fine.

You can upload it to a professional software to view the algorithm.