Estimation of the time complexity of the algorithm. Types of function of complexity of algorithms
Constant time
An algorithm is said to be an algorithm constant time(recorded as time O (1)) if the value T(n) is limited to a value that does not depend on the size of the input. For example, getting one element in an array takes constant time because a single command is executed to find it. However, finding the minimum value in an unsorted array is not a constant-time operation, since we have to scan each element of the array. So this operation takes linear time, O (n). If the number of elements is known in advance and does not change, such an algorithm can be referred to as a constant time algorithm.
Despite the name "constant time", the run time does not need to be independent of the size of the task, but the upper bound on the run time should not be. For example, the task "exchange values a and b, if it is necessary that as a result we get a≤b", is considered a constant-time problem, although the running time of the algorithm may depend on whether the inequality a ≤ b or not. However, there is a certain constant t, for which the task execution time is always does not exceed t.
Below are some code examples running in constant time:
Int index = 5; int item = list; if(condition is true) thenelse perform some operations with constant running time for i = 1 to 100 for j = 1 to 200 perform some operations with constant running time
If T(n) is O ( some constant value), this is equivalent to T(n) is O (1).
Logarithmic time
logarithmic time, if T(n) = O (log n) ... Since computers use the binary system, 2 is used as the base of the logarithm (that is, log 2 n). However, with base replacement logarithms log a n and log b n differ only by a constant factor, which is discarded in the O-large notation. So O (log n) is the standard notation for logarithmic time algorithms regardless of the base of the logarithm.
Logarithmic time algorithms are commonly found in binary tree operations or when using binary search.
O (log n) algorithms are considered highly efficient, since the execution time per element decreases with an increase in the number of elements.
A very simple example of such an algorithm is dividing a string in half, the other half is halved again, and so on. This takes O (log n) time (where n is the length of the string, we assume here that console.log and str.substring take constant time). This means that in order to increase the number of prints, the line length must be doubled.
// Function for recursively printing the right half of the line var right = function (str) (var length = str. length; // helper function var help = function (index) ( // Recursion: print the right half if (index< length ) { // Print characters from index to the end of the line console. log (str. substring (index, length)); // recursive call: call the helper function with the right side help (Math.ceil ((length + index) / 2)); )) help (0); )
Polylogarithmic time
The algorithm is said to run in polylogarithmic time, if T(n) = O ((log n) k), for some k... For example, the problem of the order of matrix multiplication can be solved in polylogarithmic time by parallel PAM machine .
Sublinear time
The algorithm is said to run in sublinear time, if T(n) = o ( n). In particular, this includes the time complexity algorithms listed above, as well as others, for example, Grover search with complexity O ( n ½).
Typical algorithms that, while accurate, still run in sublinear time, use parallelization of processes (as does the NC 1 algorithm for computing the determinant of a matrix), non-classical computations (as in Grover's search), or have a guaranteed assumption about the structure of the input (as operating in a logarithmic time, binary search algorithms, and many tree processing algorithms). However, formal constructs, such as the set of all strings that have a 1 bit in the position determined by the first log (n) bits of the string, may depend on each bit of the input, but still remain sublinear in time.
Term sublinear runtime algorithm usually used for algorithms that, unlike the examples above, operate on conventional sequential machine models and do not require a priori knowledge of the input structure. However, for them, the use of probabilistic methods is allowed, and even more, the algorithms must be probabilistic for most trivial problems.
Since such an algorithm must answer without completely reading the input data, it depends very much on the access methods allowed in the input stream. Usually for a bit string stream b 1 ,...,b k, it is assumed that the algorithm can request the value b i for anyone i.
Sublinear time algorithms, as a rule, are probabilistic and only give an approximate solution. Sublinear runtime algorithms arise naturally when investigating property checks.
Linear time
linear time, or O ( n) if its complexity is O ( n). Informally, this means that for a sufficiently large input size, the running time increases linearly with the input size. For example, a procedure that sums all the elements of a list takes time proportional to the length of the list. This description is not entirely accurate, since the operating time can differ significantly from the exact proportionality, especially for small values. n.
Linear time is often viewed as a desirable attribute of an algorithm. There has been a lot of research done to create algorithms with (almost) linear runtime or better. These studies included both software and hardware approaches. In the case of hardware execution, some algorithms that mathematically can never achieve linear execution time in standard computing models can run in linear time. There are some hardware technologies that use concurrency to achieve this goal. An example is associative memory. This concept of linear time is used in string comparison algorithms such as the Boyer-Moore algorithm and the Ukkonen algorithm.
Quasilinear time
An algorithm is said to run in quasilinear time if T(n) = O ( n log k n) for some constant k... Linear-logarithmic time is a special case with k= 1. When using weak-O notation, these algorithms are Õ ( n). Quasilinear time algorithms are also o ( n 1 + ε) for any ε> 0 and work faster than any polynomial in n
Algorithms that run in quasilinear time, in addition to the linear-logarithmic algorithms mentioned above, include:
- In-Place Merge Sort, O ( n log 2 n)
- Quick sort, O ( n log n), in the probabilistic version has a linear-logarithmic execution time in the worst case. The improbable version has a linear-log run time just to measure the difficulty on average.
- Heapsort, O ( n log n), merge sort, introsort, binary tree sort, smooth sort, solitaire sort, etc. at worst
- Fast Fourier transforms, O ( n log n)
- Calculation of Monge matrices, O ( n log n)
Linear logarithmic time
Linear-logarithmic is a special case of quasilinear time with exponent k= 1 on the logarithmic term.
Linear logarithmic function is a function of the form n log n(i.e. the product linear and logarithmic terms). The algorithm is said to work for linear-logarithmic time, if T(n) = O ( n log n) ... Thus, the linear-logarithmic element grows faster than the linear term, but slower than any polynomial in n with a degree strictly greater than 1.
In many cases, the running time n log n is simply the result of the operation Θ (log n) n once. For example, sorting with a binary tree creates a binary tree by inserting each element into an array of size n one by one. Since the insert operation in balanced binary search tree takes O (log n), the total execution time of the algorithm will be linear-logarithmic.
Sorts by comparison require at least the linear-log number of worst-case comparisons since log ( n!) = Θ( n log n) by the Stirling formula. The same execution time often arises from the recurrence equation T(n) = 2 T(n/ 2) + O ( n).
Squared time
Some examples of polynomial time algorithms:
Strictly and Weakly Polynomial Time
In some contexts, especially in optimization, algorithms are distinguished with strict polynomial time and weakly polynomial time... These two concepts only apply to input consisting of integers.
Strictly polynomial time is defined in the arithmetic computation model. In this model, basic arithmetic operations (addition, subtraction, multiplication, division, and comparison) are taken as units of execution, regardless of the length of the operands. The algorithm works in strictly polynomial time if
- the number of operations in the arithmetic computation model is limited by a polynomial in the number of integers in the input stream, and
- the memory used by the algorithm is bounded by a polynomial in the size of the input.
Any algorithm with these two properties can be reduced to a polynomial time algorithm by replacing arithmetic operations with the corresponding algorithms for performing arithmetic operations on a Turing machine. If the second of the above requirements is not met, this will no longer be true. Given an integer (which takes up memory proportional to n in the Turing machine), it can be computed in n operations using repeated exponentiation. However, the memory used to represent 2 2 n (\ displaystyle 2 ^ (2 ^ (n))), proportional to 2 n (\ displaystyle 2 ^ (n)), and it depends exponentially rather than polynomially on the memory used for the input. Hence, it is impossible to perform these calculations in polynomial time on a Turing machine, but it is possible to perform a polynomial number of arithmetic operations.
Conversely, there are algorithms that work in the number of steps of the Turing machine, limited by the polynomial length of the binary-coded input, but do not work in the number of arithmetic operations, limited by the polynomial of the number of numbers in the input. Euclid's algorithm for computing the greatest common divisor of two integers is one example. For two integers a (\ displaystyle a) and b (\ displaystyle b) the running time of the algorithm is limited O ((log a + log b) 2) (\ displaystyle O ((\ log \ a + \ log \ b) ^ (2))) steps of the Turing machine. This number is a polynomial of the size of the binary representation of numbers a (\ displaystyle a) and b (\ displaystyle b), which can be roughly represented as log a + log b (\ displaystyle \ log \ a + \ log \ b)... At the same time, the number of arithmetic operations cannot be limited by the number of integers in the input (which in this case is a constant - there are only two numbers in the input). In view of this remark, the algorithm does not work in strictly polynomial time. The real running time of the algorithm depends on the values a (\ displaystyle a) and b (\ displaystyle b), not just the number of integers in the input.
If an algorithm runs in polynomial time, but not strictly polynomial time, it is said to run in weak polynomial time... A well-known example of a problem for which a weakly polynomial algorithm is known, but a strictly polynomial algorithm is not known, is linear programming. Weakly polynomial time should not be confused with pseudo polynomial time.
Difficulty classes
The concept of polynomial time leads to several classes of complexity in computational complexity theory. Some important classes defined using polynomial time are shown below.
- : Complexity class of solvability problems that can be solved in a deterministic Turing machine in polynomial time.
- : Complexity class of solvability problems that can be solved in a non-deterministic Turing machine in polynomial time.
- ZPP: Complexity class of solvability problems that can be solved with zero error in a probabilistic Turing machine in polynomial time.
- : Complexity class of solvability problems that can be solved with one-sided errors in a probabilistic Turing machine in polynomial time.
- BPP probabilistic Turing machine in polynomial time.
- BQP: Complexity class of solvability problems that can be solved with two-sided errors in a quantum Turing machine in polynomial time.
P is the smallest time complexity class on a deterministic machine, which is sustainable in terms of changing the machine model. (For example, going from a single-tape Turing machine to a multi-tape Turing machine may result in a quadratic speedup, but any algorithm that runs in polynomial time on one model will run in polynomial time on another.)
Super polynomial time
The algorithm is said to work for superpolynomial time, if T(n) is not bounded above by a polynomial. This time is equal to ω ( n c) for all constants c, where n is an input parameter, usually the number of input bits.
For example, an algorithm that implements 2 n steps to enter size n requires superpolynomial time (more specifically, exponential time).
It is clear that an algorithm using exponential resources is superpolynomial, but some algorithms are very weakly superpolynomial. For instance, Adleman-Pomeranza-Roumeli simplicity test * works for the time n O (log log n) on the n-bit input. It grows faster than any polynomial for a large enough n, but the size of the input must become very large so that it is not dominated by a polynomial of small degree.
An algorithm requiring superpolynomial time is outside the complexity class. Cobham's thesis claims that these algorithms are impractical, and in many cases they are. Since the problem of equality of the classes P and NP has not been solved, no algorithms for solving NP-complete problems in polynomial time are currently known.
Quasi-polynomial time
Algorithms quasi-polynomial time are algorithms that run slower than polynomial time, but not as slow as exponential time algorithms. The worst-case running time for the quasi-polynomial algorithm is c... A well-known classical algorithm for factoring an integer into factors, not is quasi-polynomial, since the running time cannot be represented as 2 O ((log n) c) (\ displaystyle 2 ^ (O ((\ log n) ^ (c)))) for some fixed c... If the constant "c" in the definition of the quasi-polynomial time algorithm is 1, we get the polynomial time algorithm, and if it is less than 1, we get the sublinear time algorithm.
Quasi-polynomial time algorithms usually arise when reducing an NP-hard problem to another problem. For example, you can take an NP-hard problem, say 3SAT, and reduce it to another problem B, but the size of the problem becomes 2 O ((log n) c) (\ displaystyle 2 ^ (O ((\ log n) ^ (c))))... In this case, the reduction does not prove that problem B is NP-hard; such a reduction only shows that there is no polynomial algorithm for B, unless there is a quasi-polynomial algorithm for 3SAT (and then for all -problems). Similarly, there are some problems for which we know algorithms with quasi-polynomial time, but for which algorithms with polynomial time are unknown. Such problems appear in approximation algorithms. A famous example is the directed Steiner problem, for which there is an approximation quasi-polynomial algorithm with an approximation coefficient O (log 3 n) (\ displaystyle O (\ log ^ (3) n))(where n is the number of vertices), but the existence of a polynomial-time algorithm is an open problem.
Difficulty class QP consists of all problems with quasi-polynomial time algorithms. It can be defined in terms of DTIME as follows
QP = ⋃ c ∈ N DTIME (2 (log n) c) (\ displaystyle (\ mbox (QP)) = \ bigcup _ (c \ in \ mathbb (N)) (\ mbox (DTIME)) (2 ^ ((\ log n) ^ (c))))Relationship with NP-complete problems
In complexity theory, the unsolved problem of equality between the classes P and NP asks if all problems from the class NP have algorithms for solving in polynomial time. All well-known algorithms for NP-complete problems like 3SAT have exponential time. Moreover, there is a hypothesis that for many natural NP-complete problems there are no algorithms with subexponential execution time. Here "subexponential time" is taken in the sense of the second definition below. (On the other hand, many graph theory problems naturally represented by adjacency matrices are solvable in subexponential time simply because the size of the input is equal to the square of the number of vertices.) This hypothesis (for the k-SAT problem) is known as exponential time hypothesis... Since it assumes that NP-complete problems do not have quasi-polynomial time algorithms, some non-approximability results in the domain of approximation algorithms assume that NP-complete problems do not have quasi-polynomial time algorithms. For example, see the well-known results on the non-approximability of the set covering problem.
Subexponential time
Term subexponential time is used to express that the execution time of some algorithm can grow faster than any polynomial, but it remains significantly less than exponential. In this sense, problems with subexponential time algorithms are more malleable than algorithms with only exponential time. The precise definition of "sub-exponential" is not yet generally accepted, and we provide below two of the most common definitions.
First definition
A problem is said to be solved in sub-exponential time if it is solved by an algorithm whose logarithm of running time grows less than any given polynomial. More precisely, the problem has subexponential time if for any ε> 0 there is an algorithm that solves the problem in time O (2 n ε). The set of all such problems makes up the complexity class SUBEXP, which in terms of DTIME can be expressed as.
SUBEXP = ⋂ ε> 0 DTIME (2 n ε) (\ displaystyle (\ text (SUBEXP)) = \ bigcap _ (\ varepsilon> 0) (\ text (DTIME)) \ left (2 ^ (n ^ (\ varepsilon )) \ right))Note that here ε is not part of the input data and for each ε there may be its own algorithm for solving the problem.
Second definition
Some authors define sub-exponential time as the running time 2 o ( n). This definition allows for a longer run time than the first definition. An example of such a subexponential time algorithm is the well-known classical algorithm for factoring integers into factors, the general number field sieve method, which runs in about 2 O ~ (n 1/3) (\ displaystyle 2 ^ ((\ tilde (O)) (n ^ (1/3)))), where the length of the entrance is n... Another example is the well-known algorithm for graph isomorphism problems whose operating time is 2 O ((n log n)) (\ displaystyle 2 ^ (O ((\ sqrt (()) n \ log n)))).
Note that it makes a difference whether the algorithm is sub-exponential in the number of vertices or the number of edges. V parameterized complexity this difference is present explicitly by specifying a pair, a solvability problem, and a parameter k. SUBEPT is the class of all parameterized problems that run in subexponential time in k and for polynomial in n :
SUBEPT = DTIME (2 o (k) ⋅ poly (n)). (\ displaystyle (\ text (SUBEPT)) = (\ text (DTIME)) \ left (2 ^ (o (k)) \ cdot (\ text (poly)) (n) \ right).)More precisely, SUBEPT is the class of all parameterized tasks (L, k) (\ displaystyle (L, k)) for which there is a computable function f: N → N (\ displaystyle f: \ mathbb (N) \ to \ mathbb (N)) With f ∈ o (k) (\ displaystyle f \ in o (k)) and an algorithm that solves L during 2 f (k) ⋅ poly (n) (\ displaystyle 2 ^ (f (k)) \ cdot (\ text (poly)) (n)).
Chapter 2. Complexity of algorithms.
2.1 Time and computational complexity of algorithms.
Time complexity of the algorithm (T(N) , where N- the size of the task) is the execution time of the algorithm, measured in steps (instructions of the algorithm that must be executed to achieve the result). That is, this is the number of elementary operations that make up the algorithm for solving the problem (: =,<>, =, +, -, *, /; and, or, not, xor; call, return).
There are three types of time complexity, which depend on the combination of input data when solving a problem (equivalence, sparseness, ordering, and other properties of the input data).
https://pandia.ru/text/78/183/images/image002_151.gif "width =" 178 height = 60 "height =" 60 ">
Happening T(N)= C* N2 applicable for a square matrix.
Elementary operations in this case are a combination of "+" and "*".
If the original matrix is the identity one, then we get the Best Case.
If in the matrix half of the elements are 0, half are 1, then we get the Average Case.
Constant WITH, which cannot be accurately expressed, characterizes the influence of external factors on the execution time of algorithms (computer speed, compilation speed). Therefore, the use of time units to assess the time complexity of algorithms is not entirely correct. In this case, the time complexity of the matrix-vector multiplication algorithm is said to be proportional to N2 .
2.2 Oand Ω are notations.
The nature of the behavior of time complexity when increasing N (N® ¥ ) called asymptotic complexity of the algorithm.
To describe the growth rate of asymptotic complexity, we use O-notation. When the time complexity of an algorithm is said to be on the order of N2 :
T(N)= O(N2 )= O(f(N)),
Then it is assumed that there are positive constants C, n0 =const (C>0), such that for everyone N ³ N0 the inequality holds
T(N) £ C* f(N)
This is the upper bound on the complexity estimate.
Example 2:
Let Т (0) = 1, Т (1) = 4, ..., Т (N)=(N+1) 2, then the time complexity of this algorithm is of the order of growth T(N)= O(N2 ).
It can be shown that for all N > n0 at n0 = 1, C = 4 inequality (1) holds.
(N+1)2 £ 4* N2
Example 3:
If the time complexity is written as a polynomial
T(N)= C1 N2 + C2 N+ C3 ,
then such an algorithm has an order of complexity that is a multiple of the degree of the maximum element of the polynomial, since it grows most rapidly for N® ¥ :
T(N)= O(N2 ).
For instance:
3 n2 +5 n+1 £ 5 n2
" n ³ 1
Example 4:
If some algorithm has complexity multiple 3 n, then it can be shown that the order of growth of the velocity cannot be a multiple of O(2 n):
T(N)=3 n¹ O(2 n).
Let there be constants C, n0 , such that the following inequality holds:
3n £ C*2 n, n > n0 .
From here we get:
WITH³ (3/2)2, n > n0 .
But with n® ¥ no such constant exists WITH that would satisfy this inequality.
In addition to the upper limit of complexity, there is also a lower limit for the growth rate of temporal complexity:
T(N) ³ W(f(N))
Inequality (2) implies that there is some constant WITH for which at N® ¥ time complexity
T(N) ³ C* f(N).
Taking into account the complexity of the exact determination of T (N) (asymptotic time complexity), depending on the size of the initial data, in practice, the lower and upper bounds of the time complexity of the algorithm are used:
T(N) = q (f(N))
Depending on the value of the constant WITH the growth rate of the complexity of the algorithm can vary significantly.
Example 5:
Let the time complexity be written by the formula
T (N) = 3n2 –100n + 6 = O (n2)
3n2> 3n2 –100n + 6, n³ 1, C = 3.
If C1» 0 (C1 = 0.00001), then the inequality
10-5 n2 > 3 n2 –100 n+6, n³ 1
not executed.
But it can be shown that the order of growth of complexity
3n2 –100n + 6¹ O (N).
C * N< 3N2, N>C.
3n2 –100n + 6 = (n2)
C=2.29, n ³ n0.
2.99* n2 < 3 n2 –100 n+6
It can be shown that the lower bound
3 n2 –100 n+6 ¹ W(n3 ) at C = 1.
Inequality 3 n2 –100 n+6 ³ n3 not executed.
3 n2 –100 n+6= W(n)
C1 = , n> n0 .
https://pandia.ru/text/78/183/images/image007_89.gif "width =" 305 "height =" 247 src = ">
f1 (N)=100 n2
f2 (N)=5 n3
n0 =20 – critical point.
Another reason for preferring algorithms with a lower order of complexity is that the lower the order of complexity, the larger the size of the problem. N can be solved practically.
0 "style =" margin-left: 5.4pt; border-collapse: collapse; border: none ">
n!
Example 6:
It should be borne in mind that a larger order of growth in the complexity of algorithms, as a rule, has a smaller constant C1 in comparison with the small order of complexity growth, characterized by the constant C2.
In this case, an algorithm with rapidly growing complexity may be preferable for solving problems with small data sizes ( n® 0 ).
Let there be given five algorithms for solving the same problem, which have difficulties:
A1: 100 N
A2: 100 N* logN
A3: 10 N2
A4: N3
A5: 2 N
Then, for problems with N=2 ¸ 9 faster will be A5 ( f(N) ~ 4 ¸ 512 ). Other algorithms, when substituted, will give significantly lower rates.
At N=10 ¸ 58 A3 is preferred.
At N=59 ¸ 1024 the most effective will be A2.
At N>1024 A1 is preferred.
For programs consisting of several sequentially or concurrently executing algorithms, the complexity is estimated by sum rule and rule of works.
Sum rule : Let the program consist of two sequentially executing algorithms Р1 and Р2, for which the difficulties are determined O(f(n)) and O(g(n)) respectively. Then the time complexity of the entire program will be determined as the sum of the time complexity of each of the algorithms:
T(n) = T1 (n)+ T2 (n)
In general, we get:
T (n)Þ O (max f (n), g (n))
Rule of works: Let the time complexity of a program consisting of two parallel executing algorithms with the order of complexity O(f(n)) and O(g(n)) accordingly, it is defined as the product of the time complexity of each of the algorithms:
T(n) = T1 (n)* T2 (n)
In general:
T(n) Þ O(f(n)* g(n))
Logarithms.
2.3. Recursion.
The complexity of recursive algorithms is not easy to estimate due to the nesting of algorithmic structures
f(n) Þ f(n* f(n-1))
For example, to recursively evaluate the algorithm n! The complexity will depend on the complexity of each of the algorithms included in the recursion.
In general T(n) ~ O(N).
Other recursive algorithms generally have time complexity T(n) ~ O(an) , where a= const, which results in a total complexity greater than the complexity of a non-recursive algorithm for solving the same problem.
2.4 Estimation of the complexity of algorithms and programs.
2.4.2 Dependency recovery algorithms.
In some cases, the structure of the program is unknown, and you can only determine the time of its operation for various sizes of input data. T(N) (sec.)
To construct an analytical dependence of the complexity of the program, the function T(N) on some interval [ Nmin, Nmax] ... Then, the found curve of some analytical function is approximated with a change in the parameters of the function and an estimate of the approximation error.
As a rule, the well-known functions of time complexity are used as such a function: O(n!), O(XN), O(NX), O(logN), O(https://pandia.ru/text/78/183/images/image010_72.gif "width =" 307 "height =" 225 src = "> As a result of the experiment on the program, a table of time difficulties was obtained:
As a result of the search for the approximation of the function, the following analytical dependence was obtained:
https://pandia.ru/text/78/183/images/image012_68.gif "width =" 321 "height =" 143 src = ">
Example 2:
It often happens that the operating time of the same algorithm, in addition to the size of the problem, is influenced by other parameters entered by the user.
In this case, a family of approximation functions is constructed and the complexity of the algorithm is found analytically.
Labor intensity "href =" / text / category / trudoemkostmz / "rel =" bookmark "> labor intensity (time of work).
The polynomial or exponential nature of the algorithm is invariant with respect to the form of the input data (binary, decimal or other number system).
An algorithm is said to be polynomial if its running time, i.e., time complexity, is bounded from above by a polynomial of some degree T(N)= O(Nm) ... Then all problems that are solved by such an algorithm form a P-class of problems. These tasks are said to be included in R.
Problems with exponential time complexity ( T(N)= O(KN) ) are not included in R.
Comment : It can be shown that problems with linear complexity are included in P
T(N)= O(N1 )
Let us introduce a class of NP-problems that can be solved in polynomial time using a non-deterministic algorithm.
Let us define the state of the algorithm as a set of the address of the command being executed at the moment and the values of all variables, which is equivalent to the vector of the state of the process. Therefore, most algorithms are deterministic, that is, in them, for any state, there is only one admissible next state (including condition and selection operations). This means that such an algorithm can do one thing at a time.
V non-deterministic algorithm (NDA) for any given state there can be more than one admissible next state, i.e., such an algorithm can execute more than one operator at a time.
NDA is not a random or probabilistic algorithm. It is an algorithm that can be in many states (this is equivalent to solving a problem in parallel with many options).
Example:
 |
A deterministic algorithm (DA) would solve this problem sequentially (enumeration of all options, comparison with the optimality criterion K0 until it chooses alternative A0).
NDA can simultaneously (in parallel) get all alternatives and compare with K0, copying itself as a separate process for each alternative, which is performed independently.
In this case, if any copy discovers that an incorrect result has been received or the result has not been obtained, then it stops its execution. If the copy finds a solution that satisfies K0, then it announces success, and all other copies stop working.
That. NDA is characterized by three parameters:
1. choice- multivalued function, the values of which are elements of the set S;
2. failure causes the copy of the algorithm to terminate;
3. success causes all copies of the algorithm to terminate and produce a result.
Obviously, no physical device is capable of unlimited non-deterministic behavior, which means that NDA is a theoretical method.
Problems that can be solved using a polynomial NDA form a class of NP-problems.
2.5.2 NP- difficult andNP-Complete tasks.
The problem in P is NP- difficult if there exists a polynomial DA (PDA) of its solution, which can be used to obtain a solution to all problems included in NP. That is, such a problem is NP-hard if it is at least as hard as any problem in NP.
An NP-hard problem belonging to NP is called NP-full task. Such problems are no less difficult than any NP problem. Moreover, the existence of a PDA for an NP-hard or NP-complete problem means that the classes P and NP coincide, i.e., it is possible to solve all problems of the 3rd class by a fast algorithm.
To prove that the problem is NP-hard, it is necessary to show that if there is a PDA for the problem, then it can be used to obtain another PDA solution to the problems included in NP.
To establish that a problem is NP-complete, it is necessary to prove that it belongs to NP.
The idea of using an algorithm for solving one problem to obtain an algorithm for solving another is one of the most important algorithms in the theory of algorithms.
Definition 1: Problem Р1 is transformed into problem Р2, if any special case of problem Р1 can be transformed in polynomial time into some special case of problem Р2. Then the solution Р1 can be obtained in polynomial time from the solution of the particular case of the problem Р2.
https://pandia.ru/text/78/183/images/image024_39.gif "width =" 158 height = 56 "height =" 56 ">
For instance:
f2 (xi)=(x1 Ú x2 ) Ù ( ) Ù ()
is not feasible, since for any xi f2 (xi)= false.
Theorem :
The satisfiability problem is NP-complete.
xi selection (true, false)
if E (x1, x2,…, xN) then success
else failure
Using the transformation of problem P1 into P2, one can show that even a limited case of the satisfiability problem is NP-complete.
K-feasibility .
K-satisfiability means that any clause included in the CNF contains at most K logical variables.
The minimum case is K = 3. For a Boolean function represented in CNF, in polynomial time one can find the function E * (x2) containing at most three variables in each clause. Then E doable if doable E *.
E* (x1 , x2 ,…, xn) ® E* (xi)
For this, the method of decreasing the clause order is used
(a1 Ú a2 Ú … Ú ak)=(a1 Ú a2 Ú z) Ù (a3 Ú a4 Ú … Ú ak Ú )
By applying an iterative decomposition process, one can obtain E *.
Find a solution algorithm E * simpler than functions E... But at the same time, having proved the feasibility E *, we prove the satisfiability of the original function E.
A special case: for K = 2, the function E included in R.
Examples of NP-class problems are also graph problems :
1) Determination of the maximum of cliques of an undirected graph (NP-hard problem).
2) The problem of determining a complete subgraph (NP-complete problem).
3) Determination of vertex coverage of cardinality L for an undirected graph (NP-complete problem).
4) Determination of the maximum vertex coverings of an undirected graph (NP-hard problem).
5) The problem of determining the existence of a Hamiltonian cycle for a graph (NP-complete problem).
6) Traveling Salesman Problem: Determining the optimal movement along the graph with a single occurrence at each vertex (NP-hard problem).
7) Scheduling problem (NP-complete problem).
2.6 Algorithmically unsolvable problems
Share problems single and massive.
For instance:
5 + 7 =? Is a single problem.
x + y =? Is a massive problem.
Algorithms for obtaining objects that are paradoxical, or solving problems, from which the existence of paradoxical objects would follow, should be fundamentally unsolvable.
For example, paradoxes are:
Example 1:
Hilbert's 10th problem.
D. Hilbert in 1901, when solving Diophantine equations, put forward a problem that reads:
Find an algorithm that determines some integer solution for an arbitrary Diophantine equation
F(x, y, …)=0
This is a polynomial with integer exponents and integer coefficients for unknowns
anxn + an-1xn-1 +… + a2x2 + a1x + a0 = 0
For the above equation, there is a particular solution, which consists in the fact that every integer root xi is a divisor a0 ... Wherein a0 decompose into prime factors and check each factor for compliance with the root.
In 1970, the Leningrad mathematician Yu. Matiyasevich mathematically proved the algorithmic impossibility of solving the Diophantine equation in general form.
Example 2:
Fermat's theorem:
There are no such integers a, b, s, n (n>2) for which the equality
an + bn = cn
This theorem has been proven for many values n and verified for special cases, but a general proof of the theorem has not yet been created.
Example 3:
Goldbach's problem.
H. Holbach in 1742 in a letter to Euler formulated the problem:
Prove that every integer N³ 6 can be represented as the sum of three primes
N= a+ b+ c
This means that you need to find an algorithm that would allow for any integer N³ 6 find at least one decomposition into three simple terms.
Euler suggested a frequent solution to this problem: for even N this problem is solvable and is equivalent to decomposition into two simple terms.
I. Vinogradov in 1937 proved that for odd N three simple terms can be found, but for even numbers a solution has not yet been found.
O (1) - Most of the operations in a program are performed only once, or only a few times. Constant complexity algorithms. Any algorithm that always requires the same time regardless of the size of the data has constant complexity.
O (N) - Program run time linearly usually when each element of the input needs to be processed only a linear number of times.
O (N 2), O (N 3), O (N a) - Polynomial complexity.
O (N 2) -quadratic complexity, O (N 3) - cubic complexity
O (Log (N)) - When is the program running time logarithmic, the program starts to run much slower with increasing N. Such run times are usually found in programs that divide a large problem into small ones and solve them separately.
O (N * log (N)) - Such a running time has those algorithms that divide a big problem into small, and then, having solved them, combine their solutions.
O (2 N) = Exponential Complexity. Such algorithms most often result from an approach called brute force.
The programmer must be able to analyze algorithms and determine their complexity. The time complexity of the algorithm can be calculated based on the analysis of its control structures.
Algorithms without loops and recursive calls have constant complexity. If there are no recursion and loops, all control structures can be reduced to structures of constant complexity. Consequently, the entire algorithm is also characterized by constant complexity.
Determining the complexity of an algorithm is mainly reduced to the analysis of loops and recursive calls.
For example, consider an algorithm for processing array elements.
For i: = 1 to N do
Begin
...
End;
The complexity of this algorithm is O (N), since the body of the loop is executed N times, and the complexity of the body of the loop is O (1).
If one cycle is nested in another and both cycles depend on the size of the same variable, then the whole construction is characterized by quadratic complexity.
For i: = 1 to N do
For j: = 1 to N do
Begin
...
End;
The complexity of this program is O (N 2).
Exists two ways to analyze the complexity of an algorithm: bottom-up (from internal governing structures to external ones) and descending (from external and internal).
 |
O (H) = O (1) + O (1) + O (1) = O (1);
O (I) = O (N) * (O (F) + O (J)) = O (N) * O (condition dominants) = O (N);
O (G) = O (N) * (O (C) + O (I) + O (K)) = O (N) * (O (1) + O (N) + O (1)) = O (N 2);
O (E) = O (N) * (O (B) + O (G) + O (L)) = O (N) * O (N 2) = O (N 3);
O (D) = O (A) + O (E) = O (1) + O (N 3) = O (N 3)
The complexity of this algorithm is O (N 3).
As a rule, about 90% of the program's running time requires repetitions, and only 10% is directly calculated. An analysis of the complexity of programs shows which fragments fall within these 90% - these are the cycles of the greatest nesting depth. Repetitions can be organized as nested loops or nested recursion.
This information can be used by the programmer to build a more efficient program as follows. First of all, you can try to reduce the depth of nesting of repetitions. Then you should consider reducing the number of statements in the deepest loops. If 90% of the execution time is in the execution of inner loops, then a 30% reduction in these small sections results in a 90% * 30% = 27% reduction in the execution time of the entire program.
This is the simplest example.
A separate section of mathematics deals with the analysis of the effectiveness of algorithms and it is not so easy to find the most optimal function.
Let's rate binary search algorithm in an array - dichotomy.
The essence of the algorithm: we go to the middle of the array and look for the correspondence of the key to the value of the middle element. If we can't find a match, we look at the relative key size and median value and then move to the bottom or top half of the list. In this half, we again look for the middle and again compare with the key. If it doesn’t work, divide the current interval by half again.
function search (low, high, key: integer): integer;
var
mid, data: integer;
begin
while low<=high do
begin
mid: = (low + high) div 2;
data: = a;
if key = data then
search: = mid
else
if key< data then
high: = mid-1
else
low: = mid + 1;
end;
search: = - 1;
end;
The first iteration of the loop deals with the entire list. Each subsequent iteration halves the size of the sublist. So, the sizes of the list for the algorithm are
n n / 2 1 n / 2 2 n / 2 3 n / 2 4 ... n / 2 m
In the end, there will be an integer m such that
n / 2 m<2 или n<2 m+1
Since m is the first integer for which n / 2 m<2, то должно быть верно
n / 2 m-1> = 2 or 2 m = It follows that Usually the problem being solved has a natural "size" (usually the amount of data it processes) which we call N. Ultimately, we would like to obtain an expression for the time required for a program to process data of size N, as a function of N. Usually we are not interested in the average case - the expected runtime of the program on "typical" inputs, and the worst case is the expected runtime of the program on the worst input. Some algorithms are well studied in the sense that exact mathematical formulas for mean and worst cases are known. Such formulas are developed by carefully studying programs in order to find the running time in terms of mathematical characteristics, and then performing their mathematical analysis. There are several important reasons for this type of analysis: The best, average and worst cases play a big role in sorting. O-complexity analysis has become widespread in many practical applications. Nevertheless, it is necessary to clearly understand its limitations. TO main disadvantages of the approach include the following: Determining complexity in O-notation is far from trivial. In particular, the efficiency of binary search is determined not by the depth of nesting of the loops, but by the method of choosing each successive attempt. Another tricky part is defining the "average case". This is usually quite difficult to do due to the impossibility of predicting the operating conditions of the algorithm. Sometimes an algorithm is used as part of a large, complex program. Sometimes the efficiency of the hardware and / or operating system, or some component of the compiler, significantly affects the complexity of the algorithm. Often, the same algorithm can be used in many different applications. Due to the difficulties associated with analyzing the time complexity of an algorithm "on average", it is often necessary to be content with estimates for the worst and best cases. These estimates essentially define the lower and upper bounds for the "average" difficulty. Actually, if it is not possible to analyze the complexity of the algorithm "on average", it remains to follow one of Murphy's laws, according to which the estimate obtained for the worst case can serve as a good approximation of the complexity "on average". Perhaps the main disadvantage of O-functions is that they are too crude. If algorithm A performs some task in 0.001 * N s, while it takes 1000 * N s to solve it using algorithm B, then B is a million times faster than A. Nevertheless, A and B have the same the same time complexity is O (N). Most of this lecture was devoted to analyzing the time complexity of algorithms. There are other forms of complexity that should not be forgotten: spatial and intellectual complexity. Spatial complexity, as the amount of memory required to execute a program, was mentioned earlier. When analyzing the intellectual complexity of an algorithm, the intelligibility of algorithms and the complexity of their development are investigated. All three forms of complexity are usually related. Typically, when developing an algorithm with a good temporal complexity estimate, one has to sacrifice its spatial and / or intellectual complexity. For example, the quick sort algorithm is significantly faster than the sample sort algorithm. The payment for increasing sort speed is expressed in more memory required for sorting. The need for additional memory for quick sort is associated with multiple recursive calls. Quicksort is also more intelligently complex than insertion sort. If you ask hundreds of people to sort a sequence of objects, then most likely most of them use a sample sorting algorithm. It is also unlikely that either of them will use quicksort. The reasons for the greater intellectual and spatial complexity of quick sort are obvious: the algorithm is recursive, it is rather difficult to describe it, the algorithm is longer (meaning the text of the program) than simpler sorting algorithms. More than one algorithm can often be devised to solve the same problem. In this connection, the question arises: which of the algorithms is “better”? In most cases, “better”, apparently, is an algorithm that, using the same input data, comes to the solution of the problem, consuming less computational resources (memory and time). This is, of course, loose reasoning. For a more rigorous reasoning, we introduce several concepts. The computational process of an algorithm is a sequence of steps that went through the execution of the algorithm for some input data. It is important to understand the difference between the algorithm itself and the computational process generated by this algorithm. The first is only description second. The time complexity of the algorithm is the time \ (T \) required to complete the computational process of the algorithm for some input data. It is clear that the execution time depends on the specific executor. Let's say an electronic calculator and a supercomputer are likely to run the same algorithm at different times. However, the time \ (T \) can be expressed in terms of the number of elementary actions \ (k \) and the average execution time of an elementary action \ (t \): Moreover, \ (k \) is a property most algorithm, and \ (t \) - the property of the executor. Since \ (t \) can be considered a constant for a given executor, usually the complexity of algorithms is estimated up to a constant factor. In other words, the complexity of the algorithm is estimated order of growth. Growth order A positive definite function \ (g (x) \) has a growth order \ (f (x) \) (written \ (g (x) = \ mathcal (O) (f (x)) \)) if \ (\ exists c> 0: \: \ forall x> x_0, \, g (x) \ leq c f (x) \).
Depending on the input data, the algorithm can run at different times. Usually graded average complexity and complexity at worst... There is also a dependence on quantity input data \ (n \). It is usually the growth order of \ (n \) that is evaluated. So, for example, reading data and storing it in memory as an array will have complexity \ (\ mathcal (O) (n) \), or linear complexity, and matrix multiplication is already cubic\ (\ mathcal (O) (n ^ 3) \). In addition to the time complexity of the algorithm, it is also important spatial the complexity of the algorithm. The spatial complexity of the algorithm is the number additional memory \ (S \), which the algorithm requires to work. The memory \ (D \) required to store input data is not included in \ (S \). \ (S \) generally also depends on the actuator. For example, if two actuators support integers of 4 and 8 bytes, respectively, then the spatial complexity of the algorithm for 8-byte integers will be twice as large as for 4-byte integers. Therefore, the spatial complexity is estimated in the same order of growth. Certain difficulty classes: These are categories that have similar difficulty. The following main classes of difficulty are distinguished: DTIME A Turing machine finds a solution to a problem in a finite time (number of steps). The asymptotics of the algorithm is often specified, so, say, if the order of growth of the running time is \ (T (n) = \ mathcal (O) (f (n)) \), then \ (DTIME (f (n)) \) is indicated. P The Turing machine finds a solution to the problem in polynomial time (number of steps), i.e. \ (T (n) = \ mathcal (O) (n ^ k) \), where \ (k \ in \ mathbb (N) \). \ (P = DTIME (n ^ k) \) EXPTIME The Turing machine finds a solution to the problem in exponential time (number of steps), i.e. \ (T (n) = \ mathcal (O) (2 ^ (n ^ k)) \), where \ (k \ in \ mathbb (N) \). \ (EXPTIME = DTIME (2 ^ (n ^ k)) \). DSPACE A Turing machine finds a solution to a problem using a finite amount of additional memory (cells). The asymptotics of the algorithm is often specified, for example, if the order of growth of memory consumption is \ (S (n) = \ mathcal (O) (f (n)) \), then \ (DSPACE (f (n)) \) is indicated. L The Turing machine finds a solution to a problem with logarithmic spatial complexity, i.e. \ (S (n) = \ mathcal (O) (\ log n) \)... \ (L = DSPACE (\ log n) \). PSPACE The Turing machine finds a solution to a problem with polynomial spatial complexity, that is, \ (S (n) = \ mathcal (O) (n ^ k) \), where \ (k \ in \ mathbb (N) \). \ (PSPACE = DSPACE (n ^ k) \). EXPSPACE A Turing machine finds a solution to a problem with exponential spatial complexity, i.e. \ (S (n) = \ mathcal (O) (2 ^ (n ^ k)) \), where \ (k \ in \ mathbb (N) \). \ (EXPSPACE = DSPACE (2 ^ (n ^ k)) \). In addition, there are theoretical classes of complexity that operate on the concept undetermined Turing machines (TMT). Their definitions coincide with the above, with the replacement of the Turing machine by НМТ, and the names have the prefix N (for example NP), except for NTIME and NSPACE, where D is replaced by N. NMT is a purely theoretical construction, which, in terms of its principles of operation, is similar to MT, with the difference that for each of the states there can be several possible actions. At the same time, NMT always chooses from the possible actions the one that leads to a solution in the minimum possible number of steps. Equivalently, HMT calculates of all branches and selects the branch that leads to the solution in the minimum possible number of steps. One sometimes hears that quantum computers are implementations of HMT. While this may seem to be true in some cases, in general, an HMT is a more powerful system than a quantum computer. It is known that \ (P \ subseteq NP \ subseteq PSPACE \ subseteq EXPTIME \ subseteq NEXPTIME \ subseteq EXPSPACE \) Also, \ (P \ subsetneq EXPTIME \), \ (NP \ subsetneq NEXPTIME \), \ (PSPACE \ subsetneq EXPSPACE \) It is also known that if \ (P = NP \), then \ (EXPTIME = NEXPTIME \). The question of the equality of P and NP is one of the main unsolved questions of modern computer science. Here are some examples of simple algorithms and consider their complexity. This algorithm was described in ancient India before our era and is used to calculate the natural power \ (n \) of a real number \ (x \) In this algorithm, we have the number of multiplication operations equal to the number of digits in binary representation \ (n \) at best, and \ (2 (n-1) \) at worst. Time complexity anyway. In an efficient implementation of the algorithm, additional memory is practically not required, and it does not depend on the input data, therefore the spatial complexity is \ (S (n) = \ mathcal (O) (1) \). It should be noted that there are more efficient algorithms. However, compared to the “naive” implementation requiring \ (\ mathcal (O) (n) \) multiplication operations, this algorithm is relatively efficient. This multiplication algorithm is sometimes called Russian or peasant, although it was known as far back as Ancient Egypt. The first factor is sequentially multiplied by two, and the second is divided entirely by 2. The results are recorded in two columns until the second is 1. The result of multiplication is the sum of the numbers in the first column, opposite which are the odd numbers in the second column. Since integer division and multiplication by 2 can be performed by shifting, this algorithm gives \ (2 \ log_2 n \) shift operations, where \ (n \) is the smaller of the two numbers. In the worst case, \ (\ log_2 n - 1 \) addition operations are also obtained. Anyway, time complexity \ (T (n) = \ mathcal (O) (\ log n) \). For efficient implementation of the algorithm, additional memory is practically not required, and it does not depend on the input data, therefore \ (S (n) = \ mathcal (O) (1) \) Again, it should be noted that there are more efficient algorithms. However, compared to the “naive” implementation requiring \ (\ mathcal (O) (n) \) addition operations, this algorithm is relatively efficient. Multiply 23 by 43. Let's take 23 as the second factor. Result \ (43 + 86 + 172 + 688 = 989 \) We got 10 shift operations and 4 addition operations. For reference, \ (\ log_2 (23) \ approx 4.52 \). Determining the complexity of an algorithm The estimate of the complexity function obtained in the asymptotic analysis is called the complexity of the algorithm. It should be borne in mind that there are several estimates of the complexity of the algorithm. The asymptotic behavior of the complexity function is the operational complexity. In addition to it, you can specify the following types of difficulties. Temporary complexity is an asymptotic estimate of the running time of the algorithm on input data of length P. Obviously, in the absence of parallelization of computational procedures, the running time of the algorithm is uniquely determined by the number of operations performed. Constant coefficients expressing the duration of operations do not affect the order of time complexity, so the formulas for operational and time complexity often coincide with each other. Capacitive complexity - an asymptotic estimate of the number of simultaneously existing scalars when executing the algorithm on input data of length P. Structural complexity - a characteristic of the number of control structures in the algorithm and the specifics of their interposition. Cognitive complexity - a characteristic of the availability of an algorithm for understanding by specialists in applied fields. Types and notation of asymptotics In the asymptotic analysis of algorithms, it is customary to use the notation of mathematical asymptotic analysis. In this case, three estimates (asymptotics) of the complexity of the algorithms are considered, which are denoted as follows: Instead of notation C1 ^ (n)) very often the simpler o (^ (")) with the letter" o "is used in lowercase italics. Let us explain the semantics of the formulas using an example: if it is written / (i) = 0 (^ 2 (l)), THEN THIS means that the function g (n) = og2
(n) is an asymptotically accurate estimate for the complexity function / (α). In fact, there is a two-position definition in the form of a statement: If f (n)= @ (log 2 (")), mo g (n)= log 2 (l) - asymptotically sharp estimate for f (n). Note that the constant factor does not affect the order of complexity of the algorithm, therefore, the base of the logarithm is omitted when indicating the logarithmic complexity, and they simply write / (n) = @ (log (n)), implying an arbitrary base greater than one for the logarithm. Formal definitions of asymptotics Asymptotically Sharp Estimate of the Labor Intensity Function With, With 2, n 0 such that for n> n 0 the function f (n), up to constant factors, does not differ from the function g ( l), then the function g (n) is called an asymptotically sharp estimate for the function f (x). where 9 ^, N are the sets of all real and natural numbers, respectively. Asymptotically Sharp Upper Bound for the Complexity Function verbally defined as follows: if there are positive numbers With and n 0 such that for n> n 0 the function f (n) grows no faster than the function g (n) up to a constant factor c, then the function g (n) is called an asymptotically sharp upper bound for the function Ap). A more precise formal notation of the definition is as follows: Asymptotically Sharp Lower Bound for the Complexity Function verbally defined as follows: if there are positive numbers With and n 0 such that for n> n 0 the function f (n) grows no slower than the function g (n) up to a constant factor With, then the function? (l) is called an asymptotically sharp lower bound for the function A more precise formal notation of the definition is as follows: /(I am) = 0. ^ (N)) Note the following: Coincidence and difference of asymptotics Let us pay attention to the following fact: the estimate f (i) = 0 (? (I)) establishes for f (i) both the upper and lower bounds, since its definition presupposes the validity of the relation c g (n) The following property of asymptotics is quite obvious: if the estimate φ (n) = © ^ (n)) exists, then the equalities / ( P) = 0 (^ (i)) and f (i) =? 2 (# (i)), i.e. the upper and lower estimates of the labor intensity coincide with each other; if f (i) = 0 (? max (i)) and φ (n) = C1 ^ mt (n)), and g max (n) фg m Ln (i), then there is no function g (n), such that / (i) = 0 (? (i)). The coincidence of the upper and lower estimates of the labor intensity is possible in the following cases: There are three important rules to keep in mind when it comes to estimating the order of operational complexity: In the above rules, the symbol of only one asymptotics is used 0 (»), but they are valid for all asymptotic estimates - and for 0( )
, and &.{ ).
In the set of elementary functions, you can specify a list of functional dominance: if is a variable, a, b - numerical constants, the following statements are true: I "I dominate!; I! dominate a "; a" dominates Zj "if a> b a n dominates P b if a> 1 for any b e 9? ; n a dominates a / if a> b i dominates log q (i) if a > 1. Estimation of average labor intensity In practice, re In some calculations, the estimate f (n) of the mathematical expectation of the complexity of M is of significant interest, since in the overwhelming majority of cases f (n) is a random function. However, in the process of experimental studies of algorithms with random f (i), an additional problem arises - the choice of the number of tests for a reliable estimate of M. The proposed solution is based on using the beta distribution to approximate / (i). This is a very constructive and versatile technique. However, in modern conditions, when the productivity of the computer is sufficiently high, in many cases it is possible to use a simpler method of choosing the scope of tests, based on the control of the current variability of values f (n) - the values are evaluated until the variability of the estimates becomes less than the specified error. Estimating the Operational Complexity of an Algorithm The complexity of the algorithm can be determined based on the analysis of its control structures. Algorithms without loops and recursive calls have constant complexity. Therefore, the determination of the complexity of an algorithm is reduced mainly to the analysis of loops and recursive calls. Consider the deletion algorithm To th element from the array of size P consisting of moving array elements from (k + 1) th to P-th one position back to the beginning of the array and decreasing the number of elements P per unit. The complexity of the array processing cycle is Oh (p-k) since the body of the loop (move operation) is performed PC times, and the complexity of the loop body is 0 (1), i.e. is constant. In the example under consideration, the complexity is characterized by the asymptotics 0 ("), since the number of operations performed in this algorithm does not depend on the specifics of the data values. The complexity function is deterministic, and all types of asymptotics coincide with each other: f (n) = Q (n-k), f (n) = 0 (n-k) and f (n) = Q (n- to). This fact is evidenced by the indication of © (). You should use 0 (*) and / or? 2 (*) only if these asymptotics are different. The loop type (for, while, repeat) does not affect the complexity. If one cycle is nested in another and both cycles depend on the size of the same variable, then the whole construction is characterized by quadratic complexity. Repetition nesting is a major factor in increasing difficulty. As an example, we present the complexities of well-known search and sorting algorithms for an array of size P: Note that the number of comparison operations in the simple exchange method have the asymptotics 0 (n 2), and the number of permutation operations has two different asymptotics 0 (n 2) and? 2 (0), because the number of comparisons does not depend on the specifics of the values of the sorted data, while the number of permutations is determined precisely by this specifics. Permutations may not be carried out at all - if the data array is correctly ordered initially, or the number of permutations can be maximum - about P 2, - if the array being sorted is originally ordered in the opposite direction. Function name g (n) in the asymptotics f (n) = @ (t (n)) and f (a) = 0 (g (n)) the complexity function / (") is used to characterize the algorithm. Thus, one speaks of algorithms of polynomial, exponential, logarithmic, etc. complexity.
2 m =
m =
So O (log 2 n).
1. Programs written in a high-level language are translated into machine codes, and it can be difficult to understand how long it will take to execute one or another operator.
2. Many programs are very sensitive to input data, and their performance can be very dependent on them. The average case may turn out to be a mathematical fiction not related to the data on which the program is used, and the worst case is unlikely.
Sorting computation
1) for complex algorithms, obtaining O-estimates, as a rule, is either very time consuming or almost impossible,
2) it is often difficult to determine the complexity "on average",
3) O-estimates are too coarse to reflect more subtle differences between algorithms,
4) O-analysis provides too little information (or does not provide it at all) for analyzing the behavior of algorithms when processing small amounts of data.Algorithm complexity classes
Algorithm examples
Exponentiation
Multiplication of integers
Example
43
23
odd
86
11
odd
172
5
odd
344
2
688
1
odd
How to convert images to PNG format?
Download graphics driver with opengl 2 support
Galvanic isolation of analog signal