| Both sides previous revisionPrevious revisionNext revision | Previous revision |
| courses:cs211:winter2018:journals:boyese:chapter2 [2018/01/30 00:42] – [Section 2.5 : A More Complex Data Structure: Priority Queues] boyese | courses:cs211:winter2018:journals:boyese:chapter2 [2018/02/05 20:31] (current) – [Section 2.2 : Asymptotic Order of Growth] boyese |
|---|
| In the previous section, we defined efficiency based on an algorithm's worst-case running time on inputs of size n which grows at a rate that is at most proportional to some function f(n). Thus, f(n) is a bound on the running time of the algorithm. In this section, we seek to express the growth rate of running times and other functions in a way that is insensitive to constant factors and low-order terms.\\ | In the previous section, we defined efficiency based on an algorithm's worst-case running time on inputs of size n which grows at a rate that is at most proportional to some function f(n). Thus, f(n) is a bound on the running time of the algorithm. In this section, we seek to express the growth rate of running times and other functions in a way that is insensitive to constant factors and low-order terms.\\ |
| \\ | \\ |
| **Asymptotic Upper Bounds**\\ | ===Asymptotic Upper Bounds=== |
| Let T(n) be a function. Given some other function f(n), we say that T(n) is O(f(n)) if for sufficiently large n, the function T(n) is bounded above by a constant multiple of f(n), or T(n) = O(f(n)). Specifically, T(n) is O(f(n)) if there exist constants c > 0 and n<sub>0</sub> ≥ 0 so that for all n ≥ n<sub>0</sub>, we have T(n) ≤ c⋅f(n). In this case, we will say that T is asymptotically upper-bounded by f.\\ | Let T(n) be a function. Given some other function f(n), we say that T(n) is O(f(n)) if for sufficiently large n, the function T(n) is bounded above by a constant multiple of f(n), or T(n) = O(f(n)). Specifically, T(n) is O(f(n)) if there exist constants c > 0 and n<sub>0</sub> ≥ 0 so that for all n ≥ n<sub>0</sub>, we have T(n) ≤ c⋅f(n). In this case, we will say that T is asymptotically upper-bounded by f.\\ |
| \\ | \\ |
| Consider an algorithm whose running time has the form T(n) = pn<sup>2</sup> + qn + r for positive constants p, q, and r. We’d like to claim that any such function is O(n<sup>2</sup>). To see why, we notice that for all n ≥ 1, we have qn ≤ qn<sup>2</sup>, and r ≤ rn<sup>2</sup>. So we can write T(n) = pn<sup>2</sup> + qn + r ≤ pn<sup>2</sup> + qn<sup>2</sup> + rn<sup>2</sup> = (p + q + r)n<sup>2</sup> for all n ≥ 1. This inequality is exactly what the definition of O(⋅) requires: T(n) ≤ cn<sup>2</sup>, where c = p + q + r.\\ | Consider an algorithm whose running time has the form T(n) = pn<sup>2</sup> + qn + r for positive constants p, q, and r. We’d like to claim that any such function is O(n<sup>2</sup>). To see why, we notice that for all n ≥ 1, we have qn ≤ qn<sup>2</sup>, and r ≤ rn<sup>2</sup>. So we can write T(n) = pn<sup>2</sup> + qn + r ≤ pn<sup>2</sup> + qn<sup>2</sup> + rn<sup>2</sup> = (p + q + r)n<sup>2</sup> for all n ≥ 1. This inequality is exactly what the definition of O(⋅) requires: T(n) ≤ cn<sup>2</sup>, where c = p + q + r.\\ |
| |
| **Asymptotic Lower Bounds**\\ | ===Asymptotic Lower Bounds=== |
| We want to show that this upper bound is the best one possible. To do this, we want to express the notion that for arbitrarily large input sizes n, the function T(n) is at least a constant multiple of some specific function f(n). Thus, we say that T(n) is Ω(f(n)) if there exist constants ε > 0 and n<sub>0</sub> ≥ 0 so that for all n ≥ n<sub>0</sub>, we have T(n) ≥ ε⋅f(n). | We want to show that this upper bound is the best one possible. To do this, we want to express the notion that for arbitrarily large input sizes n, the function T(n) is at least a constant multiple of some specific function f(n). Thus, we say that T(n) is Ω(f(n)) if there exist constants ε > 0 and n<sub>0</sub> ≥ 0 so that for all n ≥ n<sub>0</sub>, we have T(n) ≥ ε⋅f(n). |
| |
| **Asymptotically Tight Bounds**\\ | ===Asymptotically Tight Bounds=== |
| If a function T(n) is both O(f(n)) and Ω(f(n)), we say that T(n) is Θ(f(n)). In this case, we say that f(n) is an asymptotically tight bound for T(n). For example, the analysis above shows that T(n) = pn<sup>2</sup> + qn + r is Θ(n<sup>2</sup>).\\ | If a function T(n) is both O(f(n)) and Ω(f(n)), we say that T(n) is Θ(f(n)). In this case, we say that f(n) is an asymptotically tight bound for T(n). For example, the analysis above shows that T(n) = pn<sup>2</sup> + qn + r is Θ(n<sup>2</sup>).\\ |
| \\ | \\ |
| **Properties of Asymptotic Growth Rates**\\ | ===Properties of Asymptotic Growth Rates=== |
| **//Transitivity//**\\ | **//Transitivity//**\\ |
| If a function f is asymptotically upper-bounded by a function g, and if g in turn is asymptotically upper-bounded by a function h, then f is asymptotically upper-bounded by h.\\ | If a function f is asymptotically upper-bounded by a function g, and if g in turn is asymptotically upper-bounded by a function h, then f is asymptotically upper-bounded by h.\\ |
| Suppose that f and g are two functions (taking non-negative values) such that g = O(f). Then f + g = Θ(f). In other words, f is an asymptotically tight bound for the combined function f + g.\\ | Suppose that f and g are two functions (taking non-negative values) such that g = O(f). Then f + g = Θ(f). In other words, f is an asymptotically tight bound for the combined function f + g.\\ |
| \\ | \\ |
| **Asymptotic Bounds for Some Common Functions**\\ | ===Asymptotic Bounds for Some Common Functions=== |
| **//Polynomials//**\\ | **//Polynomials//**\\ |
| Let f be a polynomial of degree d, in which the coefficient a<sub>d</sub> is positive. Then f = O(n<sup>d</sup>).\\ | Let f be a polynomial of degree d, in which the coefficient a<sub>d</sub> is positive. Then f = O(n<sup>d</sup>).\\ |
| In order to asymptotically analyze the running time of an algorithm, we don't necessarily have to program, compile, and execute it. Instead, we must think about how the data will be represented and manipulated in an implementation of the algorithm, so as to bound the number of computational steps it takes. In this representative example, we analyze the data structures needed to implement the Stable Matching Problem.\\ | In order to asymptotically analyze the running time of an algorithm, we don't necessarily have to program, compile, and execute it. Instead, we must think about how the data will be represented and manipulated in an implementation of the algorithm, so as to bound the number of computational steps it takes. In this representative example, we analyze the data structures needed to implement the Stable Matching Problem.\\ |
| \\ | \\ |
| **Arrays vs. Lists**\\ | ===Arrays vs. Lists=== |
| \\ | \\ |
| **//Arrays//**\\ | **//Arrays//**\\ |
| Given the advantages and disadvantages of arrays and lists, we may want to convert one format to the other depending on the specific input to a problem. In this case, it is easy to convert between the array and list representations in O(n) time.\\ | Given the advantages and disadvantages of arrays and lists, we may want to convert one format to the other depending on the specific input to a problem. In this case, it is easy to convert between the array and list representations in O(n) time.\\ |
| |
| **Implementing the Stable Matching Algorithm**\\ | ===Implementing the Stable Matching Algorithm=== |
| To ensure the run time of this algorithm is at most O(n<sup>2</sup>), we need to be able to do each of the four things in constant time.\\ | To ensure the run time of this algorithm is at most O(n<sup>2</sup>), we need to be able to do each of the four things in constant time.\\ |
| 1. Identify a free man. | 1. Identify a free man. |
| This section provides a survey of common running times such as O(n), O(n log n), and O(n<sup>2</sup>), and some of the typical approaches that lead to them. | This section provides a survey of common running times such as O(n), O(n log n), and O(n<sup>2</sup>), and some of the typical approaches that lead to them. |
| |
| **Linear Time**\\ | ===Linear Time=== |
| An algorithm that runs in O(n), or linear, time has the property that its running time is at most a constant factor times the size of the input. Examples of algorithms with linear time are **//computing the maximum//** and **//merging two sorted lists//**, which can also be computed as O(n<sup>2</sup>) time.\\ | An algorithm that runs in O(n), or linear, time has the property that its running time is at most a constant factor times the size of the input. Examples of algorithms with linear time are **//computing the maximum//** and **//merging two sorted lists//**, which can also be computed as O(n<sup>2</sup>) time.\\ |
| |
| |
| **O(n log n) Time**\\ | ===O(n log n) Time=== |
| O(n log n) is the running time of any algorithm that splits its input into two equal-sized pieces, solves each piece recursively, and then combines the two solutions in linear time. A well known example of this type of algorithm is sorting, in particular, **//Mergesort//**. There are many algorithms whose most expensive step is to sort the input, so O(n log n) is a relatively common running time.\\ | O(n log n) is the running time of any algorithm that splits its input into two equal-sized pieces, solves each piece recursively, and then combines the two solutions in linear time. A well known example of this type of algorithm is sorting, in particular, **//Mergesort//**. There are many algorithms whose most expensive step is to sort the input, so O(n log n) is a relatively common running time.\\ |
| |
| |
| **Quadratic Time**\\ | ===Quadratic Time=== |
| Performing a search over all pairs of input items and spending constant time per pair is a common way which a running time of O(n<sup>2</sup>) arises. Quadratic time also arises naturally from a pair of **//nested loops//**: An algorithm consists of a loop with O(n) iterations, and each iteration of the loop launches an internal loop that takes O(n) time. Multiplying these two factors of n together gives the running time. The brute force algorithm for finding the closest pair is a common example of this kind of algorithm.\\ | Performing a search over all pairs of input items and spending constant time per pair is a common way which a running time of O(n<sup>2</sup>) arises. Quadratic time also arises naturally from a pair of **//nested loops//**: An algorithm consists of a loop with O(n) iterations, and each iteration of the loop launches an internal loop that takes O(n) time. Multiplying these two factors of n together gives the running time. The brute force algorithm for finding the closest pair is a common example of this kind of algorithm.\\ |
| |
| |
| **Cubic Time**\\ | ===Cubic Time=== |
| More elaborate sets of nested loops often lead to algorithms that run in O(n<sup>3</sup>) time. For example, the algorithm for the problem "for pair of sets S<sub>i</sub> and S<sub>j</sub>, determine whether S<sub>i</sub> and S<sub>j</sub> have an element in common" has three nested for loops that each run in linear time. There are algorithms for this problem that improve on O(n<sup>3</sup>) running time, but they are complicated and it is not clear whether the improved algorithms are practical on inputs of reasonable size.\\ | More elaborate sets of nested loops often lead to algorithms that run in O(n<sup>3</sup>) time. For example, the algorithm for the problem "for pair of sets S<sub>i</sub> and S<sub>j</sub>, determine whether S<sub>i</sub> and S<sub>j</sub> have an element in common" has three nested for loops that each run in linear time. There are algorithms for this problem that improve on O(n<sup>3</sup>) running time, but they are complicated and it is not clear whether the improved algorithms are practical on inputs of reasonable size.\\ |
| |
| |
| **O(n<sup>k</sup>) Time**\\ | ===O(n^k) Time=== |
| We obtain a running time of O(n<sup>k</sup>) for any constant k when we search over all subsets of size k. The problem of finding independent sets in a graph has O(n<sup>k</sup>) time. For some fixed constant k, we want to know if a given n-node input graph G has an independent set of size k. Since we are treating k as a constant, this quantity is O(n<sup>k</sup>).\\ | We obtain a running time of O(n<sup>k</sup>) for any constant k when we search over all subsets of size k. The problem of finding independent sets in a graph has O(n<sup>k</sup>) time. For some fixed constant k, we want to know if a given n-node input graph G has an independent set of size k. Since we are treating k as a constant, this quantity is O(n<sup>k</sup>).\\ |
| |
| |
| **Beyond Polynomial Time**\\ | ===Beyond Polynomial Time=== |
| Two kinds of bounds that come up often are 2<sup>n</sup> and n!. For example, we are given a graph and want to find an independent set of maximum size. The outer loop in this algorithm will run for 2<sup>n</sup> iterations as it tries all these subsets. Inside the loop, we are checking all pairs from a set S that can be as large as n nodes, so each iteration of the loop takes at most O(n<sup>2</sup>) time. Multiplying these two together, we get a running time of O(n<sup>2</sup>2<sup>n</sup>). Thus we see that 2<sup>n</sup> arises naturally as a running time for a search algorithm that must consider all subsets. Search spaces of size n! tend to arise for one of two reasons. First, n! is the number of ways to match up n items with n other items. The function n! also arises in problems where the search space consists of all ways to arrange n items in order. A common example of this is the Traveling Salesman Problem: given a set of n cities, with distances between all pairs, what is the shortest tour that visits all cities?\\ | Two kinds of bounds that come up often are 2<sup>n</sup> and n!. For example, we are given a graph and want to find an independent set of maximum size. The outer loop in this algorithm will run for 2<sup>n</sup> iterations as it tries all these subsets. Inside the loop, we are checking all pairs from a set S that can be as large as n nodes, so each iteration of the loop takes at most O(n<sup>2</sup>) time. Multiplying these two together, we get a running time of O(n<sup>2</sup>2<sup>n</sup>). Thus we see that 2<sup>n</sup> arises naturally as a running time for a search algorithm that must consider all subsets. Search spaces of size n! tend to arise for one of two reasons. First, n! is the number of ways to match up n items with n other items. The function n! also arises in problems where the search space consists of all ways to arrange n items in order. A common example of this is the Traveling Salesman Problem: given a set of n cities, with distances between all pairs, what is the shortest tour that visits all cities?\\ |
| |
| |
| **Sublinear Time**\\ | ===Sublinear Time=== |
| There are cases where one encounters running times that are asymptotically smaller than linear. These situations tend to arise in a model of computation where the input can be "queried" indirectly rather than read completely, and the goal is to minimize the amount of querying that must be done. The best-known example of this is the **//binary search algorithm//**. The running time of binary search is O(log n), because of this successive shrinking of the search region. In general, O(log n) arises as a time bound whenever we’re dealing with an algorithm that does a constant amount of work in order to throw away a constant fraction of the input.\\ | There are cases where one encounters running times that are asymptotically smaller than linear. These situations tend to arise in a model of computation where the input can be "queried" indirectly rather than read completely, and the goal is to minimize the amount of querying that must be done. The best-known example of this is the **//binary search algorithm//**. The running time of binary search is O(log n), because of this successive shrinking of the search region. In general, O(log n) arises as a time bound whenever we’re dealing with an algorithm that does a constant amount of work in order to throw away a constant fraction of the input.\\ |
| |
| The priority queue is one of the most broadly useful sophisticated data structures. Here, it is a useful illustration of the analysis of a data structure that, unlike lists and arrays, must perform some nontrivial processing each time it is invoked. A priority queue is designed for applications in which elements have a priority value, or key, and each time we need to select an element from a set S, we want to take the one with highest priority. A priority queue is a data structure that maintains a set of elements S, where each element v ∈ S has an associated value key(v) that denotes the priority of element v; smaller keys represent higher priorities. Priority queues support the addition and deletion of elements from the set, and also the selection of the element with smallest key. With a priority queue that can perform insertion and the extraction of minima in O(log n) per operation, we can sort n numbers in O(n log n) time. \\ | The priority queue is one of the most broadly useful sophisticated data structures. Here, it is a useful illustration of the analysis of a data structure that, unlike lists and arrays, must perform some nontrivial processing each time it is invoked. A priority queue is designed for applications in which elements have a priority value, or key, and each time we need to select an element from a set S, we want to take the one with highest priority. A priority queue is a data structure that maintains a set of elements S, where each element v ∈ S has an associated value key(v) that denotes the priority of element v; smaller keys represent higher priorities. Priority queues support the addition and deletion of elements from the set, and also the selection of the element with smallest key. With a priority queue that can perform insertion and the extraction of minima in O(log n) per operation, we can sort n numbers in O(n log n) time. \\ |
| |
| **Theorem 2.11**. //A sequence of O(n) priority queue operations can be used to sort a set of n numbers.//\\ | **Theorem 2.11** //A sequence of O(n) priority queue operations can be used to sort a set of n numbers.//\\ |
| |
| **A Data Structure for Implementing a Priority Queue**\\ | ===A Data Structure for Implementing a Priority Queue=== |
| **//The Definition of a Heap//**\\ | **The Definition of a Heap**\\ |
| The heap data structure combines the benefits of a sorted array and list for purposes of this application. Conceptually, a heap is a balanced binary tree. The keys in such a binary tree are said to be in heap order if the key of any element is at least as large as the key of the element at its parent node in the tree. We can avoid using pointers to represent a heap if a bound N is known in advance on the total number of elements that will ever be in the heap at any one time. Such heaps can be maintained in an array H indexed by i = 1 ..... N. We will think of the heap nodes as corresponding to the positions in this array. H[1] is the root, and for any node at position i, the children are the nodes at positions leftChild(i) = 2i and rightChild(f) = 2i + 1.\\ | The heap data structure combines the benefits of a sorted array and list for purposes of this application. Conceptually, a heap is a balanced binary tree. The keys in such a binary tree are said to be in heap order if the key of any element is at least as large as the key of the element at its parent node in the tree. We can avoid using pointers to represent a heap if a bound N is known in advance on the total number of elements that will ever be in the heap at any one time. Such heaps can be maintained in an array H indexed by i = 1 ..... N. We will think of the heap nodes as corresponding to the positions in this array. H[1] is the root, and for any node at position i, the children are the nodes at positions leftChild(i) = 2i and rightChild(f) = 2i + 1.\\ |
| |
| **Implementing the Heap Operations**\\ | ===Implementing the Heap Operations=== |
| To add elements to the heap, we start by adding the new element v to the final position i = n + 1, by setting H[i] = v. Unfortunately, this does not maintain the heap property, as the key of element v may be smaller than the key of its parent. We must use the following algorithm, called //Heapify-up//: | To add elements to the heap, we start by adding the new element v to the final position i = n + 1, by setting H[i] = v. Unfortunately, this does not maintain the heap property, as the key of element v may be smaller than the key of its parent. We must use the following algorithm, called //Heapify-up//: |
| |
| |
| **Theorem 2.12** //The procedure Heapify-up(H, i) fixes the heap property in O(log i) time, assuming that the array H is almost a heap with the key of H[i] too small. Using Heapify-up we can insert a need element in a heap of n elements in O(log n) time.//\\ | **Theorem 2.12** //The procedure Heapify-up(H, i) fixes the heap property in O(log i) time, assuming that the array H is almost a heap with the key of H[i] too small. Using Heapify-up we can insert a need element in a heap of n elements in O(log n) time.//\\ |
| | |
| | To delete an element from the heap is a bit more complicated, and many applications of priority queues don’t require the deletion of arbitrary elements, but only the extraction of the minimum. In a heap, this corresponds to identifying the key at the root and then deleting it; we will refer to this operation as ExtractMin(H). Here we will implement a more general operation Delete(H, i), which will delete the element in position i. For a heap with n elements, after deleting the element H[i], the heap will have only n - 1 elements; and not only is the heap-order property violated, there is actually a "hole" at position i, since H[i] is now empty. To patch this hole in H, we move the element w in position n to position i. After doing this, H at least has the property that its n - 1 elements are in the first n - 1 positions, as required, but we may well still not have the heap-order property. The key of element w may be either too small or too big for the position i. If the key is too small, we can use Heapify-up. If the key is too large, we must use the following algorithm, called //Heapify-down//: |
| | |
| | <code> |
| | Heapify-down (H, i): |
| | Let n = length(H) |
| | If 2i > n then |
| | Terminate with H unchanged |
| | Else if 2i < n then |
| | Let left = 2i, and right = 2i + l |
| | Let j be the index that minimizes key [H [left]] and key [H [right]] |
| | Else if 2i = n then |
| | Let j = 2i |
| | Endif |
| | If key[H[j]] < key[H[i]] then |
| | swap the array entries H[i] and H[j] |
| | Heapify-down (H, j) |
| | Endif |
| | </code> |
| |
| **Theorem 2.13** //The procedure Heapify-down(H, i) fixes the heap property in O(log n) time, assuming that H is almost a heap with the key value of H[i] too big. Using Heapify-up or Heapify-dovn we can delete a new element in a heap of n elements in O(log n) time.//\\ | **Theorem 2.13** //The procedure Heapify-down(H, i) fixes the heap property in O(log n) time, assuming that H is almost a heap with the key value of H[i] too big. Using Heapify-up or Heapify-dovn we can delete a new element in a heap of n elements in O(log n) time.//\\ |
| |
| **Implementing Priority Queues With Heaps**\\ | ===Implementing Priority Queues With Heaps=== |
| | The heap data structure with the Heapify-down and Heapify-up operations can efficiently implement a priority queue that is constrained to hold at most N elements at any point in time. Here we summarize the operations we will use and their run times. |
| | |
| | * //StartHeap(N)// returns an empty heap H that is set up to store at most N elements. This operation takes **O(N)** time, as it involves initializing the array that will hold the heap. |
| | * //Insert(H, v)// inserts the item u into heap H. If the heap currently has n elements, this takes **O(log n)** time. |
| | * //FindMin(H)// identifies the minimum element in the heap H but does not remove it. This takes **O(1)** time. |
| | * //Delete(H, i)// deletes the element in heap position i. This is implemented in **O(log n)** time for heaps that have n elements. |
| | * //ExtractMin(H)// identifies and deletes an element with minimum key value from a heap. This is a combination of the preceding two operations, and so it takes **O(log n)** time. |
| | |
| | Other operations:\\ |
| | |
| | * //Delete(H, Position[v])// deletes the element v. Maintaining this array does not increase the overall running time, and so we can delete an element v from a heap with n nodes in **O(log n)** time. |
| | * //ChangeKey (H, v, α)// is used in some algorithms and changes the key value of element v to //key(v) = α//. To implement this operation in **O(log n)** time, we first need to be able to identify the position of element v in the array, which we do by using the array Position. Once we have identified the position of element v, we change the key and then apply Heapify-up or Heapify-down as appropriate. |
| | |
| | Again, as with previous sections, I felt it was helpful to extract the most important information from the text and organize it in a way that made sense to me. It always seems like there is a lot of extraneous information to me in each section, but I think this might be because I don't really learn anything by reading a textbook, and for this reason I rarely do. With the addition of having to extract the most important information along with reading it and hearing it in class has helped me to better pay attention to what's going on and organize the information in my head. I thought this section really didn't say much for how much it actually said, and I would give it a 6/10 for readability. |
| |
