Algorithm Analysis –
Types of analysis
Worst case: T(n)
Average case: T(n)
Asymptotic estimate
O
f (n) = O(g(n)) Þ
($c > 0, n 0 >
O(g(n)) = (f (n) : $ c > 0, n 0 >
Example: 2n 2 = O(n 3)
Merge sort
if(p< r) //1
 |
Recursion tree: T(n) = 2*T(n/2) +cn, with –const, c>0
Methodology for evaluating recursive algorithms.
Iteration method
Based on the formula T(n), we write the formula for the smaller element located on the right side of the formula for T(n).
Substitute the right side of the resulting formula into the original formula
We carry out the first two steps until we expand the formula into a series without the function T(n)
Let's estimate the resulting series based on an arithmetic or geometric progression
T(n)=T(n-1)+n, T(1)=1
T(n)=θ(g(n)), g(n)=?
T(n-1)=T(n-2)+(n-1)
T(n-2)=T(n-3)+(n-2)
T(n-3)+(n-2)+(n-1)+n=…
1+…(n-2)+(n-1)+n=
Recursion tree - a graphical method of displaying the substitution of a relation into itself
T(n)=2T(n/2)+n 2
T(n/4) T(n/4) T(n/4) T(n/4)
(n/2) 2 (n/2) 2 log n (1/2)*n 2
(n/4) 2 (n/4) 2 (n/4) 2 (n/4) 2 (1/4)*n 2
Substitution method
- Guess (suggest) a solution
- Check the solution using induction
- Find and substitute constants
T(n) = 2T(n/2) + n
T(n) = (n log n)
Induction premise: T(n) ≤ с * n* log n, c>0
Let this estimate be true for n/2
T(n/2) ≤ c*(n/2)*log(n/2)
Let's substitute it into the original formula for T(n)
T(n) ≤ 2*(c*(n/2)*log(n/2))+n ≤
c*n*log(n/2)+n =
c*n*log n - c*n*log 2 +n =
c*n*log n - c*n +n ≤
c*n*log n
c≥1, n ≥ 2
Main theorem on recurrent estimates
T (n) = aT (n/b) + f (n), a ≥ 1, b > 1, f (n) − (f (n) > 0, n > n0)
Algorithms for sorting arrays in polynomial time
Sorting is the process of rearranging objects for a given
aggregates in a certain order (increasing
or decreasing).
The purpose of sorting is usually to facilitate subsequent
searching for elements in a sorted set.
Simple insertion sort
void sort_by_insertion(key a , int N)
for (i=1; i< N; i++)
for (j=i-1; (j>=0)&& (x< a[j]); j--)
a = a[j];
Analysis of simple insertion sort
Number of comparisons:
C (N) = 1 + 2 + 3 + ... + N - 1 = (N * (N -1))/2= O (N 2)
Total time: T(N) = θ(N 2)
Sorting by simple exchange. Bubble method.
void bubble_sort (key a, int N)
for (i=0; i for (j=N-l; j>i; j--) if (a > a[j]) ( x = a[j]; a[j] = a[j-1]; a[ j -1] = x; Sorting analysis by simple exchange Worst case: reverse ordered array Number of comparisons: C(N) = (N - 1) + (N - 2) + ... + 1 = (N * (N-1))/2 = O(N 2) Total time: T(N) = θ(N 2) Addition Node* _Add(Node *r, T s) r = new Node(s); else if(s< r->inf) r->left = _Add(r->left, s); r->right = _Add(r->right, s); Removing an element from the tree Tree T with root n and key K. remove from tree T a node with key K (if there is one). Algorithm: If tree T is empty, stop; Otherwise, compare K with the key X of the root node n. If K>X, recursively remove K from the right subtree of T; If K If K=X, then three cases need to be considered. If both children do not exist, then we delete the current node and reset the parent node’s link to it; If one of the children is missing, then we put the values of the fields of child m instead of the corresponding values of the root node, overwriting its old values, and free the memory occupied by node m; If both children are present, then we find the node m that is next to the given one; copy the data (except for links to child elements) from m to n; recursively delete node m. Element following given Given: tree T and key x Return a pointer to the element next to x or NULL if x is the last element in the tree. Algorithm: Separately considers two cases. If the right subtree of a vertex x is not empty, then the element next to x is the minimum element in this subtree. Otherwise, if the right subtree of vertex x is empty. We move up from x until we find a vertex that is the left child of its parent. This parent (if there is one) will be the element being searched for. Inserting nodes Inserting a new key into an AVL tree is done in the same way as it is done in simple search trees: we go down the tree, choosing the right or left direction of movement depending on the result of comparing the key in the current node and the inserted key. The only difference is that when returning from recursion (that is, after the key has been inserted into either the right or left subtree), the current node is rebalanced. The imbalance that arises with such an insertion in any node along the path of movement does not exceed two, which means that the application of the balancing function described above is correct. Removing nodes To remove a vertex from an AVL tree, the algorithm is taken as a basis, which is usually used when removing nodes from a standard binary search tree. We find node p with the given key k, in the right subtree we find node min with the smallest key and replace the deleted node p with the found node min. During implementation, several options arise. First of all, if the found node p does not have a right subtree, then, according to the property of the AVL tree, on the left this node can only have one single child node (tree of height 1), or node p is even a leaf. In both of these cases, you simply delete node p and return as the result a pointer to the left child node of p. Let now p have a right subtree. We find the minimum key in this subtree. According to the property of a binary search tree, this key is located at the end of the left branch, starting from the root of the tree. We use the recursive findmin function. removemin function - removing the minimum element from a given tree. According to the property of an AVL tree, the minimal element on the right either has a single node or is empty. In both cases, you just need to return the pointer to the right node and perform balancing on the way back (when returning from recursion). Hash tables, chaining method Direct addressing is used for small sets of keys. It is required to define a dynamic set, each element of which has a key from the set U = (0,1,..., m - 1), where m is not too large, no two elements have the same keys. To represent a dynamic set, an array (directly addressed table), T, is used, each position or cell of which corresponds to a key from the key space U. Cell k points to an element of the set with key k. If the set does not contain an element with key k, then T[k] = NULL. Key search operation takes time O(1) Disadvantages of direct addressing: If the key space U is large, storing a table T of size |U| impractical, if not impossible, depending on the amount of available memory and the size of the keyspace The set K of actually stored keys may be small compared to the key space U, in which case the memory allocated to table T is largely wasted. A hash function is a function h that determines the location of the elements of the set U in the table T. In hashing, an element with key k is stored in cell h(k), the hash function h is used to calculate the cell for a given key k. The function h maps the key space U onto the cells of the hash table T [O..m - 1]: h: U → (0,1,..., m -1). the value h(k) is called the hash value of the key k. When the set K of keys stored in the dictionary is much smaller than the space of possible keys U, a hash table requires significantly less space than a directly addressing table. The purpose of a hash function is to reduce the working range of array indices, and instead of |U| values, you can get by with just m values. Memory requirements can be reduced to θ(|K|), while the search time for an element in the hash table remains equal to O(1) - this is a bound on the average search time, while in the case of a direct-addressing table this bound is valid for worst case scenario. A collision is a situation where two keys map to the same cell. For example, h(43) = h(89) = h(112) = k Chain method: Idea: Store elements of a set with the same hash value as a list. Analysis Worst case: if the hash function for all elements of the set produces the same value. The access time is Θ(n), with |U |
= n. Average case: for the case where the hash values are uniformly distributed. Each key can be equally likely to end up in any cell of the table, regardless of where the other keys fall. Let a table T be given and n keys stored in it. Then, a = n/m is the average number of keys in the table cells. The time to search for a missing element is Θ(1 + α). Constant time to calculate the hash function value plus time to traverse the list to the end, because the average length of the list is α, then the result is Θ(1) + Θ(α) = Θ(1 + α) If the number of table cells is proportional to the number of elements stored in it, then n = O(m) and, therefore, α = n/m = O(m)/m = O(1), which means searching for an element in the hash table in on average requires time Θ(1). Operations Inserting an element into a table Removal also require O(1) time Selecting a hash function The keys should be evenly distributed across all cells The pattern of distribution of hash function keys should not correlate with the patterns of the data. (For example, the data is even numbers). Methods: Division method Multiplication method Division method h (k) = k mod m Problem of small divisor m Example No. 1. m = 2 and all keys are even Þ odd cells are not filled. Example No. 2. m = 2 rÞ hash does not depend on bits in above r. Multiplication method Let m= 2 r , the keys are w-bit words. h(k) = (A k mod 2 w) >> (w - r), Where A mod 2 = 1 ∩ 2 w-1< A< 2 w You shouldn't choose A close to 2w-1 And 2w This method is faster than the division method Multiplication method: example m = 8 = 2 3 , w = 7 Open addressing: search Search is also sequential research Success when the meaning is found Failure when you find an empty cell or go through the entire table. Research Strategies Linear - h(k, i) = (h′(k) + i) mod m This strategy is easy to implement, but is subject to problems primary clustering associated with the creation of a long sequence activity of occupied cells, which increases the average search time. Quadratic h(k, i) = (h′(k) + c 1 i+ c 2 i 2) mod m where h′(k) is a regular hash function Double hashing – h(k,i) = (h 1 (k) + i h 2 (k)) mod m. Double hashing This method gives excellent results, but h 2 (k) must be coprime to m. This can be achieved: using m as powers of two and making h 2 (k) produce only odd numbers m = 2 r иh 2 (k)– odd. m- prime number, values h 2 – positive integers less than m For simple m can be installed h1(k)=k mod m h2(k)=1+(k mod m’) m’ less than m (m’ =m-1 or m-2) Open Addressing: Insertion Example Let table A be given: Double hashing h2(k)=1+(k mod 11) Where will the element be embedded? Open addressing analysis Additional assumption for uniform hashing: each key is equally likely to receive any of the m! permutations of table exploration sequences regardless of other keys. Finding a missing element Number of trials for successful search Open addressing A< 1 - const Þ O(1)
How does he behave? A: Table 50% complete Þ2 research The table is 90% complete Þ 10 studies The table is 100% complete Þ m studies The principle of greedy choice They say that it is applicable to the optimization problem greedy choice principle, if a sequence of locally optimal choices gives a globally optimal solution. Typically, a proof of optimality follows this pattern: It is proved that the greedy choice at the first step does not close the path to the optimal solution: for every solution there is another, consistent with the greedy choice and no worse than the first. It is shown that the subproblem arising after the greedy choice at the first step is similar to the original one. The argument is completed by induction. Optimal for subtasks The problem is said to have the property optimality for subproblems, if the optimal solution to a problem contains optimal solutions for all its subproblems. Construction of the Huffman code Any message consists of a sequence of characters from some alphabet. Often, in order to save memory and increase the speed of information transfer, the task of compressing information arises. In this case, special character encoding methods are used. These include Huffman codes, which provide compression from 20% to 90% depending on the type of information. The Huffman algorithm finds optimal character codes based on the frequency of characters used in the compressed text. Huffman's algorithm is an example of a greedy algorithm. Let's assume that in a file of length 100,000 characters the character frequencies are known: We need to construct a binary code in which each character is represented as a finite sequence of bits called a codeword. When using a uniform code, in which all codewords are the same length, a minimum of three bits are spent per character and the entire file will require 300,000 bits. An uneven code will be more economical if frequently occurring characters are encoded with short sequences of bits, and rarely occurring characters with long sequences. When encoding, the entire file will cost (45*1 + 13*3 + 12*3 + 16*3 + 9*4 + 5*4)*1000 = 224000. That is, uneven code gives about 25% savings. Prefix codes Consider codes in which, for each of two sequences of bits representing different characters, neither is a prefix of the other. Such codes are called prefix codes. When encoding, each character is replaced with its own code. For example, the string abc looks like 0101100. For a prefix code, decoding is unique and occurs from left to right. The first character of a text encoded with a prefix code is uniquely determined, since its codeword cannot be the beginning of any other character. Having identified this symbol and discarded its codeword, we repeat the process for the remaining bits, and so on. To effectively implement decoding, you need to store information about the code in a convenient form. One possibility is to represent the code as code binary tree, whose leaves correspond to the characters to be encoded. In this case, the path from the root to the encoded symbol determines the encoding sequence of bits: moving along the tree to the left gives 0, and moving to the right gives 1. The internal nodes indicate the sum of frequencies for the leaves of the corresponding subtree. The optimal code for a given file always corresponds to a binary tree in which every vertex that is not a leaf has two children. The uniform code is not optimal, since the corresponding tree has a vertex with one son. A tree of the optimal prefix code for a file that uses all the characters from some set C and only they contain exactly | C | leaves one for each symbol and exactly | C | - 1 nodes that are not leaves. Knowing the tree T corresponding to the prefix code, it is easy to find the number of bits required to encode the file. For each character c from the alphabet C, let f[c] denote the number of its occurrences in the file, and dT(c) the depth of its corresponding leaf and, therefore, the length of the sequence of bits encoding c. Then to encode the file you will need: This value is called the cost of the tree T. It is necessary to minimize this value. Huffman proposed a greedy algorithm that constructs an optimal prefix code. The algorithm builds a tree T corresponding to the optimal code from bottom to top, starting from the set of | C | leaves and making | C | - 1 mergers. For each symbol its frequency f [c] is specified. To find two objects to merge, a priority queue Q is used, using frequencies f as priorities - the two objects with the lowest frequencies are merged. As a result of the merger, a new object (internal vertex) is obtained, the frequency of which is considered equal to the sum of the frequencies of the two merged objects. This vertex is added to the queue. Huffman ( C)
1. n ←│C│ │ C
│- power C 2. Q ← C
Q – priority queue 3. for i ← 1 to n-1 4. do z ← Create_Node() z – node consisting of fields f, left, right 5. x ← left [z] ← Dequeue(Q) 6. y ← right [z] ← Dequeue(Q) 7. f[z] ← f[x] + f[y] 8. Enqueue(Q,z) 9. return Dequeue(Q) return the root of the tree Grade The queue is implemented as a binary heap. You can create a queue in O(n). The algorithm consists of a loop that is executed n-1 times. Each queue operation is completed in O(log n). The total running time is O(n log n). Network construction problem Areas of occurrence: communication and road networks. Given: many network nodes (hosts, cities). Necessary: building a network with the smallest total edge weight (length of network cables, length of roads). Graph model: network nodes are graph nodes, E = V 2, we know the weights of all edges. Result: free tree. Approach to searching for MOD We construct tree A by adding one edge at a time, and before each iteration, the current tree is a subset of some MOD. At each step of the algorithm, we determine an edge (u, v) that can be added to A without violating this property. We call such an edge safe GenericMST(G, w) 2 while A is not MOD 3 do Find an edge (u, v) that is safe for A 4 A ← A U ((u, v)) ____________________________________________________________________________ Rib classification 1. Tree ribs(tree edges) are the edges of the graph G. An edge (u, v) is a tree edge if vertex v is open when examining this edge. 2. Back edges(back edges) are the edges (u,v) connecting vertex u to its ancestor v in the depth-first search tree. Cycle edges that can occur in directed graphs are considered back edges. 3. Straight ribs(forward edges) are edges (u,v) that are not tree edges and connect vertex u to its descendant v in the depth-first search tree. 4. Cross ribs(cross edges) - all other edges of the graph. They can connect vertices of the same depth-first search tree when no vertex is an ancestor of another, or they can connect vertices in different trees. The DFS algorithm can be modified so that it will classify the edges encountered during operation. The key idea is that each edge (u, v) can be classified using the color of vertex v when it is first examined (though straight and cross edges are not distinguished). The first case follows directly from the definition of the algorithm. Considering the second case, note that gray vertices always form a linear chain of descendants corresponding to the stack of active calls to the DFS_Visit procedure; the number of gray vertices is one greater than the depth of the last open vertex in the depth-first search tree. The exploration always starts from the deepest gray vertex, so that an edge that reaches another gray vertex reaches the ancestor of the original vertex. In the third case, we are dealing with the remaining edges that do not fall under the first or second case. It can be shown that an edge (u, v) is straight if d [u]< d [v], и перекрестным, если d [u] >d[v] ___________________________________________________________________________ Topological sorting IN precedence column every edge (u, v) means u precedes v Topological sorting graph is the construction of a sequence a, where for all a i and a j the following holds: $(a i ,a j) Þ i< j. Topological sorting of an oriented acyclic graph G = (V, E) is a linear ordering of all its vertices such that if the graph G contains an edge (u,v) then u in this ordering is located before v (if the graph is not acyclic , such sorting is not possible). Topological sorting of a graph can be thought of as ordering its vertices along a horizontal line such that all edges are directed from left to right. Sorted sequence: C2, C6, C7, C1, C3, C4, C5, C8 for each(u in V) color[u] = white; // initialize L = new linked_list; // L is an empty linked list for each (u in V) if (color[u] == white) TopVisit(u); return L; // L gives final order TopVisit(u) ( // start a search at u color[u] = gray; // mark u visited for each (v in Adj(u)) if (color[v] == white) TopVisit(v); Append u to the front of L; // on finishing u add to list T (n) = Θ(V + E) Procedures Create - Set (u)- create a set from one vertex u. Find - Set (u)- find the set to which the vertex belongs ureturns in what set the specified element is located. In fact, this returns one of the elements of the set (called representative or leader). This representative is selected in each set by the data structure itself (and can change over time, namely, after calls Union). If the Find - Set call for some two elements returned the same value, then this means that these elements are in the same set, otherwise, they are in different sets. Union (u,v)- combine sets that contain vertices u And v We will store sets of elements in the form trees: one tree corresponds to one set. The root of the tree is the representative (leader) of the set. When implemented, this means that we create an array parent, in which for each element we store a link to its ancestor in the tree. For tree roots, we will assume that their ancestor is themselves (i.e., the link loops at this place). To create a new element (operation Create - Set), we simply create a tree rooted at vertex v , noting that its ancestor is itself. To combine two sets (operation Union(a,b)), we will first find the leaders of the set in which a is located and the set in which b is located. If the leaders coincide, then we do nothing - this means that the sets were already united. Otherwise, you can simply specify that the ancestor of vertex b is equal to f (or vice versa) - thereby joining one tree to another. Finally, the implementation of the leader search operation ( Find - Set(v)) is simple: we climb the ancestors from the vertex v until we reach the root, i.e. while the reference to the ancestor does not lead to itself. It is more convenient to implement this operation recursively. Path compression heuristic This heuristic is designed to speed things up Find - Set() . It lies in the fact that when after the call Find - Set(v) we will find the leader we are looking for p set, then remember that at the vertex v and all the peaks passed along the way - it is this leader p. The easiest way to do this is to redirect them parent to this peak p . Thus, the array of ancestors parent the meaning changes somewhat: now it is compressed ancestor array, i.e. for each vertex, not the immediate ancestor can be stored there, but the ancestor of the ancestor, the ancestor of the ancestor of the ancestor, etc. On the other hand, it is clear that it is impossible to make these pointers parent always pointed to the leader: otherwise, when performing an operation Union would have to update the leaders O(n) elements. Thus, to the array parent should be approached exactly as an array of ancestors, perhaps partially compressed. Applying the Path Compression Heuristic allows achieving logarithmic asymptotics: per request on average Analysis Initialization – O(V) The loop runs V times and each extractMin operation runs in - O(logV) times, for a total of O(V logV) times The for loop runs O(E) times, decreaseKey takes O(logV) time. Total running time - O(V log V +E logV)= O(E logV) Shortest path property Let p = (v 1 , v 2 ..... v k)- the shortest path from vertex v 1 to the vertex vk in a given weighted directed graph G = (U. E) with weight function w: E → R a p ij = (v i , v i+1 .....v j)- partial path of path p that goes from the vertex v i to the top v j for arbitrary i and j (1 ≤ i< j ≤ k).
Then p ij– the shortest path from the vertex v i To v i Dijkstra(G, w, s) ( for each (u in V) ( // initialization d [u] = +infinity color [u] = white d[s] =0 // dist to source is 0 Q = new PriQueue(V) // put all vertices in Q while (Q.nonEmpty()) ( // until all vertices processed u = Q.extractMin() // select u closest to s for each (v in Adj[u]) ( if (d[u] + w(u,v)< d[v]) { // Relax(u,v) d [v] = d [u] + w(u,v) Q.decreaseKey(v, d[v]) color [u] = black Difficulty rating The Bellman-Ford algorithm terminates within a period of time O(V*E), since the initialization in line 1 takes O(V) time, for each of the |V| - 1 pass along the edges in lines 2-4 takes O(E) time, and executing the for loop in lines 5-7 takes O(E) time. . Asymptotic evaluation of the algorithm Algorithm Analysis – theoretical study of the performance of computer programs and the resources they consume. Performance – the operating time of the algorithm, depending on the amount of input data. Determined by the function T(n), where n is the volume of input data Types of analysis Worst case: T(n)– maximum time for any input data of size n. Average case: T(n)– expected time for any input data of size n. The best case is the minimum operating time. Asymptotic estimate O- notation: asymptotic upper bound f (n) = O(g(n)) Þ ($c > 0, n 0 > 0 Þ 0 ≤ f (n) ≤ c g(n), n ≥ n 0) O(g(n)) = (f (n) : $ c > 0, n 0 > 0 Þ 0 ≤ f (n) ≤ c g(n), n ≥ n 0 ) Example: 2n 2 = O(n 3)
Recursive algorithms, construction of an asymptotic estimate. Example Merge sort sort(А,p,r) //p - the beginning of the array, r – the end of the array T(n) if(p< r) //1 q=(p + r)/2; //Calculate the middle of array 1 sort(A,p,q); //sort the left side of T(n/2) sort(A,q+1,r); //sort the right side of T(n/2) merge(p,q,r); //merge two arrays into one n Analysis of comparison of time costs of algorithms performed to solve an instance of a certain problem, with large amounts of input data, is called asymptotic. The algorithm with the lower asymptotic complexity is the most efficient. In asymptotic analysis, algorithm complexity is a function that allows you to determine how quickly the running time of the algorithm increases with increasing data volume. The main growth estimates found in asymptotic analysis are: Let n– the amount of data. Then the growth of the algorithm function f(n) you can limit the functions g(n) asymptotically: For example, the time to clean a room depends linearly on the area of that same room (Θ( S)), i.e., with increasing area in n times, the cleaning time will also increase by n once. Looking up a name in the phone book will take linear time Ο
(n), if you use a linear search algorithm, or time that depends logarithmically on the number of records ( Ο
(log 2 ( n))), in case of using binary search. Of greatest interest to us is Ο
-function. Moreover, in subsequent chapters, the complexity of the algorithms will be given only for the asymptotic upper bound. Under the phrase “the complexity of the algorithm is Ο
(f(n))" it is implied that with an increase in the volume of input data n, the running time of the algorithm will increase no faster than some constant multiplied by f(n). Important rules of asymptotic analysis: O(9,1n) = O(n) O(5n*n) = O(5n)*O(n) = O(n)*O(n) = O(n*n) = O(n 2) O(5n/n) = O(5n)/O(n) = O(n)/O(n) = O(n/n) = O(1) O(n 5 +n 10) = O(n 10) Counting the number of operations is tedious and, importantly, not at all necessary. Based on the rules listed above, in order to determine the complexity of an algorithm, it is not necessary, as we did before, to count all operations; it is enough to know what complexity a particular algorithm design (operator or group of operators) has. Thus, an algorithm that does not contain loops and recursions has constant complexity O(1). Complexity of the loop executing n iterations is equal to O(n). The construction of two nested loops depending on the same variable n, has quadratic complexity O(n 2). Asymptotic notation If for the function T(n) there are constants c 1 > 0 and c 2 > 0 and such a number n 0 > 0 that the condition is satisfied, then we say that the execution time of the algorithm (program) asymptotically exactly corresponds to the function n 2. This fact is denoted as , where n– length of the algorithm input. Definition 1.
In general, if there are positive definite functions, then the notation means that there are constants c 1 > 0 and c 2 > 0 and so on n 0 > 0, which is for all . (The entry “” is read as “ef from en is theta from same from en”). If , then they say that is asymptotically exact estimate(asymptotically tight bound) for . In fact, this relationship is symmetrical, if: , then . Rice. 2. Illustration for the definition Note that there is designation the fact of some relationship between two functions, therefore, if , and therefore , is established, this does not mean at all that . Let us illustrate the symmetry property of the function. It can be shown that . According to the definition, positive constants must be specified from 1, from 2 and number n 0 so that the inequalities were carried out for everyone. Let us divide all parts of the inequality into n 2: It can be seen that to satisfy the second inequality it is sufficient to set c 2 = 1/2. The first will be executed if (for example) n 0 = 7 and c 1 =1/14. Let us show that indeed, let there be such c 2 and n 0, which is for everyone. But then for everyone, from which it follows that c 2 cannot be a constant, since it increases with increasing n, which contradicts the definition. Let us mention an important special case of using -notation: , which denotes a bounded function separated from zero by some positive constant for sufficiently large values of the argument. Asymptotic notation is often used within formulas. For example, a recurrence relation of the form means that the execution time of the algorithm for an input of length n determined by the execution time for the input sequence of ( n–1) elements and some function, about which it is only important for us to know that it is no less c 1 n and no more c 2 n for some positive from 1 And from 2 and big enough for everyone n, which by definition is denoted by . In other words, the running time of the program when the input length changes increases proportionally n, and in the algorithm this term in the expression corresponds to a fragment with an asymptotic estimate equal to n. Often asymptotic notations are not used quite formally, although their intended meaning is usually clear from the context. A typical example of the informal use of asymptotic notation is a chain of equalities of the form . The second of these equalities is understood as follows: whatever the function on the left side, the sum is . Searching for an asymptotically exact estimate for the sum, we can discard terms of lower order, which for large n become small compared to the main term. Note also that the coefficient of the leading term does not play a role (it can only affect the choice of constants With 1 and With 2). For example, consider the quadratic function, where a, b, c– some constants and a > 0.
Discarding the terms of lower orders and the coefficient of the highest term, we find that To verify this formally, we can put With 1 =a/ 4, c 2 =
7a/ 4i. In general, for any polynomial p(n) degrees d with a positive leading coefficient we have . 1.3.2 - and - designations In general, a record includes two estimates: upper and lower. They can be divided: Definition 2. Let there be functions and that take non-negative values for sufficiently large values of the argument. They say that if there is such a constant c> 0 and such a number n 0, which is for everyone (Fig. 3a). Definition 3. They say that if there is such a constant c> 0 and such a number n 0, which is for everyone (Fig. 3b). These entries read like this: “ef from en is o large from same from en,” “ef from en is omega large from same from en.” Theorem 1.For any two functions And the property holds if and only if and . Comment: For any two functions And property And are equivalent. (a) (b) Asymptotic notations can be used inside formulas. For example, we can write the expression meaning the amount h(1) +h(2) + … + h(n), Where h(×) – some function for which h(i)=O(i). It can be shown that this sum itself as a function of n There is O(n 2). 1.3.3 and designations The recording means that with growth n the relationship remains limited. If besides then we write (reads “ef from en is o small from same from en”). Formally speaking, if for every positive there is an n 0 such that for all . Thus, the notation assumes that and are non-negative for sufficiently large n. Approximately The notation is introduced in a similar way: they say that there is (“ef from en is omega small from same from en”), if for any positive e there is something like this n 0, that with everyone, and Obviously, it is equivalent Approximately Thus, there can be three main cases (there is also a fourth case when the limit does not exist, but it is quite rare in the real practice of analyzing algorithms): However, in practice, strict definitions are rarely used. There is a more convenient method for performing this assessment, based on a powerful mathematical apparatus specially created for calculating the limits of the ratio of the two functions under consideration, in particular the L'Hopital rule: and the Stirling formula for sufficiently large n: Example 1. Compare the orders of growth of functions f(n)=n(n– 1)/2 and g(n)=n 2 . Solution: because the limit is equal to a positive constant, both functions have the same order of growth, which is written as . Example 2. Compare the orders of growth of functions and . Since the limit is zero, the function has a lower order of growth than . That is . Example 3. Compare the orders of growth of functions and . Solution: using Sterling’s formula, we get: Therefore, although the function grows very quickly, the function grows even faster, which is written as . Please note that when using this form of notation, in contrast to the case of using limits, we cannot make an unambiguous conclusion that the order of growth of the function is higher than the function and not, say, equal to it, so “large” omega is used. Despite the fact that the time complexity function of an algorithm can be determined precisely in some cases, in most cases it is pointless to look for its exact value. The fact is that, firstly, the exact value of time complexity depends on the definition of elementary operations (for example, complexity can be measured in the number of arithmetic operations or operations on a Turing machine), and secondly, as the size of the input data increases, the contribution of constant factors and the terms of lower orders that appear in the expression for the exact operating time become extremely insignificant. Asymptotic complexity- consideration of large input data and assessment of the order of growth of the algorithm's operating time. Typically, an algorithm with lower asymptotic complexity is more efficient for all input data, except perhaps small data size. Asymptotic complexity estimate denoted by the Greek letter Θ (theta). f(n) = Θ(g(n)), if there exist c1, c2>0 and n0 such that c1*g(n)<=f(n)<=c2*g(n) , при n>n0. The function g(n) is an asymptotically accurate estimate of the complexity of the algorithm - the function f(n), the above inequality is called an asymptotic equality, and the notation Θ itself symbolizes the set of functions that grow “as quickly” as the function g(n) - i.e. e. up to multiplication by a constant. As follows from the above inequality, the estimate Θ is both an upper and a lower estimate of the complexity. It is not always possible to obtain an estimate in this form, so the upper and lower estimates are sometimes determined separately. ($APPTYPE CONSOLE) uses begin 4. Recursion with memorization (a transparent version of dynamic programming). An example of quick calculation of binomial coefficients using the formula C(n,m)=C(n-1,m)+C(n-1,m-1) There is a way to solve the problem of repeated calculations. It is obvious - you need to remember the found values so as not to calculate them again each time. Of course, this will require active use of memory. For example, a recursive algorithm for calculating Fibonacci numbers can easily be supplemented with three “lines”: create a global array FD consisting of zeros; after calculating the number F(n), place its value in FD[n]; at the beginning of the recursive procedure, check that FD[n] = 0 and, if so, return FD[n] as a result, and otherwise proceed to the recursive calculation of F(n). (Function in Pascal) function C(m, n:Byte):Longint; If (m=0) or (m=n) Else C:=C(m, n-1)+C(m-1, n-1) (Procedure in Pascal) Procedure C(m, n: Byte; Var R: Longint); Var R1, R2: Longint; If (m=0) or (m=n)
h(51) = h(49) = h(63) = i
Rice. 3. Upper (a) and lower (b) asymptotic estimates of the function
Upper Difficulty Score denoted by the Greek letter Ο (omicron), and is a set of functions that grow no faster than g(n).
f(n)= Ο(g(n)), if there are c>0 and n0 such that 0<=f(n)<=cg(n), при n>n0.
Lower Difficulty Score denoted by the Greek letter Ω (omega), and is the set of functions that grow no slower than g(n).
f(n)= Ω(g(n)), if there are c>0 and n0 such that 0<=cg(n)<=f(n), при n>n0.
As a consequence: an asymptotic estimate exists only if the lower and upper bounds for the complexity of the algorithm coincide. In the practice of analyzing algorithms, the complexity estimate is most often understood as the upper estimate of complexity. This is quite logical, since the most important thing is to estimate the time in which the algorithm is guaranteed to complete its work, and not the time within which it will definitely not complete.
SysUtils;
var n:Integer;
function result(n:integer):Integer; //formation of the world
var i:Integer;
begin
result:=0;
for i:= 2 to n div 2 do
if n mod i =0 then
result:=result+1;
end;
read(n); // your name
write(result(n));
readln;
readln;
end.
end.