计算机算法导论_第2章.ppt

Introduction to Algorithms 计算机算法导论,20072008年第一学期,Quiz(10 minutes),Question Suppose we are comparing implementations of insertion sort and merge sort on the same machine. For inputs of size n, insertion sort runs in 8n2 steps, while merge sort runs in 64nlgn steps. For which values of n does insertion sort beat merge sort? What is the smallest value of n such that an algorithm whose running time is 100n2 runs faster than an algorithm whose running time is 2n on the same machine?,2、Getting Started,Question Introducing the insertion sort algorithm to solve the solving problem Analyzing its running time Designing the algorithm by the divide-and-conquer approach,2.1、Insertion sort,Problem,Input: sequence of numbers. Output: permutation such that a1 a2 an . Example: Input: 8 2 4 9 3 6 Output: 2 3 4 6 8 9,Pseudocode,Difference between pseudocode and real code,Pseudocode is more clear and concise Sometimes, in English Pseudocode is not typically concerned with issue of software engineering,Pseudocode conventions,Indentation indicates block structure The looping constructs while, for and repeat and the conditional constructs if, then and else have interpretations similar to those in Pascal The “ ” indicates a comment A multiple assignment Varibles are local to the given procedure A1j Field objects indicates compound data, A variable representing an array or object is treated as a pointer, and NIL pointer Parameters are passed to a procedure by value The boolean operators is short circuiting,Pseudcode,2.1、Insertion sort,1.1、Algorithms,Correct and incorrect algorthms The specification of an algorthm In english A computer program A hareware design,Loop invariants,Initialization: It is true prior to the first iteration of the loop Maintenance: If it is true before an iteration, it remains true before the next iteration Termination: When the loop terminates, the invariant can helps show that the algorithm is correct,The correctness of insertion sort,Initialization: The loop invariant holds before the first loop iteration, j=2. Maintenance: Each iteration maintains the loop invariant. Termination: When the loop terminates, the entire array is sorted, which means that the algorithm is correct,2.2、Analyzing algorithms,Analyzing algorithms,Analyzing algorithms means predicting the resources that the algorithm requires. Such as, Computational time Memory Communication bandwidth Computer hardware,RAM(random-access machine) model,Instructions: Arithmetic (add, subtract, multiply, divide,) Data movement (load, store, copy,) Control (conditional and unconditional brand, return,) A grey area, such as exponentiation Data types: Integer Floating point,Running time,The running time depends on the input: an already sorted sequence is easier to sort. Parameterize the running time by the size of the input, since short sequences are easier to sort than long ones. Generally, we seek upper bounds on the running time, because everybody likes a guarantee.,Pseudocode,Kinds of analyses,Worst-case: (usually) T(n) = maximum time of algorithm on any input of size n. Average-case: (sometimes) T(n) = expected time of algorithm over all inputs of size n. Need assumption of statistical distribution of inputs. Best-case: (bogus) Cheat with a slow algorithm that works fast on some input.,Kinds of analyses,Worst-case: (usually) Best-case: (bogus),Worst-case and average-case analysis,2.3 Designing algorithms,The divide-and-conquer approach,The divide-and-conquer approach,Example,Merge,Machine-independent time,What is insertion sorts worst-case time? It depends on the speed of ou