北京邮电大学 计算机学院 离散数学 3.1- Algorithms.ppt

* * College of Computer Science Technology, BUPT Smallest elements “float” up to the top of the list, like bubbles in a container of liquid. Bubble Sort 30 31 1 32 33 2 34 3 30 1 31 32 2 33 3 34 1 30 31 2 32 3 33 34 1 30 2 31 3 32 33 34 1 2 30 3 31 32 33 34 1 2 3 30 31 32 33 34 * * College of Computer Science Technology, BUPT Insertion Sort Algorithm English description of algorithm: For each item in the input list, “Insert” it into the correct place in the sorted output list generated so far. Like so: Use linear or binary search to find the location where the new item should be inserted. Then, shift the items from that position onwards down by one position. Put the new item in the hole remaining. * * College of Computer Science Technology, BUPT Greedy algorithm Example 6 Consider the problem of making n cents change with quarters, dimes, nickels, and pennies, and using the least total number of coins. We can devise a greedy algorithm for making change for n cents by making a locally optimal choice at each step Lemma 1 If n is a positive integer, then n cents in change using quarters, dimes, nickels, and pennies using the fewest coins possible has at most two dimes, at most one nickel, at most four pennies, and cannot have two dimes and a nickel. The amount of change in dimes, nickels,and pennies cannot exceed 24 cents. * * College of Computer Science Technology, BUPT Theorem 1 The greedy algorithm (Algorithm 6) produces change using the fewest coins possible. * * College of Computer Science Technology, BUPT * * College of Computer Science Technology, BUPT Review §3.1: Algorithms Characteristics of algorithms. Pseudocode. Examples: Max algorithm, primality-testing, linear search binary search algorithms. Sorting. Intuitively we see that binary search is much faster than linear search, but how do we analyze the efficiency of algorithms formally? Use methods of algorithmic complexity, which utilize the order-of-growth concepts from §3.2 * * College of Comp