Differences
This shows you the differences between two versions of the page.
Both sides previous revisionPrevious revisionNext revision | Previous revision | ||
courses:cs211:winter2011:journals:chen:chapter_2 [2011/01/24 23:19] – [2.3 Implementing the Stable Matching Algorithm Using Lists and Arrays] zhongc | courses:cs211:winter2011:journals:chen:chapter_2 [2011/01/25 01:52] (current) – [2.3 Implementing the Stable Matching Algorithm Using Lists and Arrays] zhongc | ||
---|---|---|---|
Line 53: | Line 53: | ||
+ | Interesting/ | ||
+ | ===== 2.4 A Survey of Common Running Times ===== | ||
+ | Summary | ||
+ | When trying to analyze a new algorithm, it helps to have a rough sense of | ||
+ | the " | ||
+ | So this section covers some of the common types of running times that we are going to keep refering back to later. | ||
+ | **Linear time: O(N)** | ||
+ | An example would be iterating through a collection and perform some constant operation on each elment of that collection. | ||
+ | Examples: | ||
+ | * Computing the max of a list. | ||
+ | * Merging the two sorted list. Only have to go through the two lists once to get it done. | ||
+ | |||
+ | |||
+ | |||
+ | **O(NlogN) Time** | ||
+ | Examples | ||
+ | * Mergesort --- divide into logN pieces of small problems and for each one perform the merge which takes N. | ||
+ | * Time stamp problem | ||
+ | |||
+ | **Quadratic Time O(N²)** | ||
+ | Exaples: | ||
+ | * Matching problem. | ||
+ | * calculating distances between any given points. | ||
+ | |||
+ | **Cubic Time O(N³**) | ||
+ | For each set Si ,For each other set Sj, For each element p of Si, Determine whether p also belongs to Sj. | ||
+ | |||
+ | **O(N^k) Time** | ||
+ | Independent set of size k. Given a graph,are there k nodes such that no two are joined by an edge? | ||
+ | |||
+ | Note: Summary of running times. P20 slide 1/19 | ||
+ | |||
+ | |||
+ | Interesting/ | ||
+ | ===== 2.5 A More Complex Data Structure: | ||
+ | Motivation: | ||
+ | **After overcoming higher-level obstacles, | ||
+ | lower-level implementation details | ||
+ | can improve runtime.** | ||
+ | |||
+ | Summary | ||
+ | Priority Queue revisited: | ||
+ | |||
+ | Maintains a set of elements S | ||
+ | • Each element v ∈ S has a key(v) for its priority | ||
+ | Smaller keys represent higher priorities | ||
+ | Supported operations | ||
+ | • Add, delete elements | ||
+ | • Select element with smallest key | ||
+ | |||
+ | Implementing data structures: for sorting | ||
+ | If we use unsorted lists: N² -why? | ||
+ | |||
+ | If we use array: logn*N² | ||
+ | |||
+ | If we use heaps: NlogN | ||
+ | |||
+ | Implementation of Heaps: | ||
+ | Know the implementation of the **Heapify-up** and **Heapify-down** with an array based implementation. | ||
+ | |||
+ | Interesting/ | ||
+ |