算法分析与设计课件

1、1 The Role of Algorithms in Computing,1 what are algorithms? 2 why is the study of algorithms worthwhile? 3 what is the role of algorithms?,An algorithm is said to be correct if, for every input instance, it halts with the correct output,The problem of sorting,Input: sequence of numbers. Output: per

2、mutation such that a 1 a 2 a n . Example: 解释什么是实例？ Input: 8 2 4 9 3 6 Output: 2 3 4 6 8 9,Time Is Important,“Time is important for everybody, especially for the computer scientist who studies algorithms.” J. S. Yu,What kinds of problems are solved by algorithms? Levels of Hardness 1. There is no met

3、hod to solve the problem in finitely many steps. 2. Theoretically, there is an algorithm, but the running time increases too much with the size of input, even to the universe age（NPC problems）. 3. Among the good algorithms, there is still a hierarchy of running time.,多项式算法：把渐近复杂性与规模N的幂同阶的这类算法称为多项式算法

4、。 指数型算法：把渐近复杂性与规模N的指数同阶的这类算法称为指数型算法。 这两种算法在效率上有质的区别的内在原因是算法渐近复杂性的阶的区别。可见，算法的渐近复杂性的阶对于算法的效率有着决定性的意义。 多项式算法是有效的算法。很多问题都有多项式算法。但也有一些问题还未找到多项式算法，只找到指数型算法。,Homework,1.1-3, 1.1-4,1.2 Algorithms as a technology,Suppose computers were infinitely fast and computer memory was free. Would you have any reason t

5、o study algorithms? Compare the running time of insert sort and merge sort.,Why study algorithms andperformance?, Algorithms help us to understand scalability. Performance often draws the line between what is feasible and what is impossible. Algorithmic mathematics provides a language for talking ab

6、out program behavior., Performance is the currency of computing. The lessons of program performance generalize to other computing resources. Speed is fun!,2 Getting Started,Analysis of Algorithms Insertion Sort Merge Sort,The problem of sorting,Input: sequence of numbers. Output: permutation such th

7、at a 1 a 2 a n . Example: Input: 8 2 4 9 3 6 Output: 2 3 4 6 8 9,An Example: Insertion Sort,InsertionSort(A, n) for i = 2 to n key = Aij = i - 1;while (j 0) and (Aj key) Aj+1 = Ajj = j - 1Aj+1 = key ,An Example: Insertion Sort,InsertionSort(A, n) for i = 2 to n key = Aij = i - 1;while (j 0) and (Aj

8、key) Aj+1 = Ajj = j - 1Aj+1 = key ,30,10,40,20,1,2,3,4,i = j = key = Aj = Aj+1 = ,An Example: Insertion Sort,InsertionSort(A, n) for i = 2 to n key = Aij = i - 1;while (j 0) and (Aj key) Aj+1 = Ajj = j - 1Aj+1 = key ,30,10,40,20,1,2,3,4,i = 2j = 1key = 10Aj = 30 Aj+1 = 10,An Example: Insertion Sort,

9、InsertionSort(A, n) for i = 2 to n key = Aij = i - 1;while (j 0) and (Aj key) Aj+1 = Ajj = j - 1Aj+1 = key ,30,30,40,20,1,2,3,4,i = 2j = 1key = 10Aj = 30 Aj+1 = 30,An Example: Insertion Sort,InsertionSort(A, n) for i = 2 to n key = Aij = i - 1;while (j 0) and (Aj key) Aj+1 = Ajj = j - 1Aj+1 = key ,3

10、0,30,40,20,1,2,3,4,i = 2j = 1key = 10Aj = 30 Aj+1 = 30,An Example: Insertion Sort,InsertionSort(A, n) for i = 2 to n key = Aij = i - 1;while (j 0) and (Aj key) Aj+1 = Ajj = j - 1Aj+1 = key ,30,30,40,20,1,2,3,4,i = 2j = 0key = 10Aj = Aj+1 = 30,An Example: Insertion Sort,InsertionSort(A, n) for i = 2

11、to n key = Aij = i - 1;while (j 0) and (Aj key) Aj+1 = Ajj = j - 1Aj+1 = key ,30,30,40,20,1,2,3,4,i = 2j = 0key = 10Aj = Aj+1 = 30,An Example: Insertion Sort,InsertionSort(A, n) for i = 2 to n key = Aij = i - 1;while (j 0) and (Aj key) Aj+1 = Ajj = j - 1Aj+1 = key ,10,30,40,20,1,2,3,4,i = 2j = 0key

12、= 10Aj = Aj+1 = 10,An Example: Insertion Sort,InsertionSort(A, n) for i = 2 to n key = Aij = i - 1;while (j 0) and (Aj key) Aj+1 = Ajj = j - 1Aj+1 = key ,10,30,40,20,1,2,3,4,i = 3j = 0key = 10Aj = Aj+1 = 10,An Example: Insertion Sort,InsertionSort(A, n) for i = 2 to n key = Aij = i - 1;while (j 0) a

13、nd (Aj key) Aj+1 = Ajj = j - 1Aj+1 = key ,10,30,40,20,1,2,3,4,i = 3j = 0key = 40Aj = Aj+1 = 10,An Example: Insertion Sort,InsertionSort(A, n) for i = 2 to n key = Aij = i - 1;while (j 0) and (Aj key) Aj+1 = Ajj = j - 1Aj+1 = key ,10,30,40,20,1,2,3,4,i = 3j = 0key = 40Aj = Aj+1 = 10,An Example: Inser

14、tion Sort,InsertionSort(A, n) for i = 2 to n key = Aij = i - 1;while (j 0) and (Aj key) Aj+1 = Ajj = j - 1Aj+1 = key ,10,30,40,20,1,2,3,4,i = 3j = 2key = 40Aj = 30 Aj+1 = 40,An Example: Insertion Sort,InsertionSort(A, n) for i = 2 to n key = Aij = i - 1;while (j 0) and (Aj key) Aj+1 = Ajj = j - 1Aj+

15、1 = key ,10,30,40,20,1,2,3,4,i = 3j = 2key = 40Aj = 30 Aj+1 = 40,An Example: Insertion Sort,InsertionSort(A, n) for i = 2 to n key = Aij = i - 1;while (j 0) and (Aj key) Aj+1 = Ajj = j - 1Aj+1 = key ,10,30,40,20,1,2,3,4,i = 3j = 2key = 40Aj = 30 Aj+1 = 40,An Example: Insertion Sort,InsertionSort(A,

16、n) for i = 2 to n key = Aij = i - 1;while (j 0) and (Aj key) Aj+1 = Ajj = j - 1Aj+1 = key ,10,30,40,20,1,2,3,4,i = 4j = 2key = 40Aj = 30 Aj+1 = 40,An Example: Insertion Sort,InsertionSort(A, n) for i = 2 to n key = Aij = i - 1;while (j 0) and (Aj key) Aj+1 = Ajj = j - 1Aj+1 = key ,10,30,40,20,1,2,3,

17、4,i = 4j = 2key = 20Aj = 30 Aj+1 = 40,An Example: Insertion Sort,InsertionSort(A, n) for i = 2 to n key = Aij = i - 1;while (j 0) and (Aj key) Aj+1 = Ajj = j - 1Aj+1 = key ,10,30,40,20,1,2,3,4,i = 4j = 2key = 20Aj = 30 Aj+1 = 40,An Example: Insertion Sort,InsertionSort(A, n) for i = 2 to n key = Aij

18、 = i - 1;while (j 0) and (Aj key) Aj+1 = Ajj = j - 1Aj+1 = key ,10,30,40,20,1,2,3,4,i = 4j = 3key = 20Aj = 40 Aj+1 = 20,An Example: Insertion Sort,InsertionSort(A, n) for i = 2 to n key = Aij = i - 1;while (j 0) and (Aj key) Aj+1 = Ajj = j - 1Aj+1 = key ,10,30,40,20,1,2,3,4,i = 4j = 3key = 20Aj = 40

19、 Aj+1 = 20,An Example: Insertion Sort,InsertionSort(A, n) for i = 2 to n key = Aij = i - 1;while (j 0) and (Aj key) Aj+1 = Ajj = j - 1Aj+1 = key ,10,30,40,40,1,2,3,4,i = 4j = 3key = 20Aj = 40 Aj+1 = 40,An Example: Insertion Sort,InsertionSort(A, n) for i = 2 to n key = Aij = i - 1;while (j 0) and (A

20、j key) Aj+1 = Ajj = j - 1Aj+1 = key ,10,30,40,40,1,2,3,4,i = 4j = 3key = 20Aj = 40 Aj+1 = 40,An Example: Insertion Sort,InsertionSort(A, n) for i = 2 to n key = Aij = i - 1;while (j 0) and (Aj key) Aj+1 = Ajj = j - 1Aj+1 = key ,10,30,40,40,1,2,3,4,i = 4j = 3key = 20Aj = 40 Aj+1 = 40,An Example: Inse

21、rtion Sort,InsertionSort(A, n) for i = 2 to n key = Aij = i - 1;while (j 0) and (Aj key) Aj+1 = Ajj = j - 1Aj+1 = key ,10,30,40,40,1,2,3,4,i = 4j = 2key = 20Aj = 30 Aj+1 = 40,An Example: Insertion Sort,InsertionSort(A, n) for i = 2 to n key = Aij = i - 1;while (j 0) and (Aj key) Aj+1 = Ajj = j - 1Aj

22、+1 = key ,10,30,40,40,1,2,3,4,i = 4j = 2key = 20Aj = 30 Aj+1 = 40,An Example: Insertion Sort,InsertionSort(A, n) for i = 2 to n key = Aij = i - 1;while (j 0) and (Aj key) Aj+1 = Ajj = j - 1Aj+1 = key ,10,30,30,40,1,2,3,4,i = 4j = 2key = 20Aj = 30 Aj+1 = 30,An Example: Insertion Sort,InsertionSort(A,

23、 n) for i = 2 to n key = Aij = i - 1;while (j 0) and (Aj key) Aj+1 = Ajj = j - 1Aj+1 = key ,10,30,30,40,1,2,3,4,i = 4j = 2key = 20Aj = 30 Aj+1 = 30,An Example: Insertion Sort,InsertionSort(A, n) for i = 2 to n key = Aij = i - 1;while (j 0) and (Aj key) Aj+1 = Ajj = j - 1Aj+1 = key ,10,30,30,40,1,2,3

24、,4,i = 4j = 1key = 20Aj = 10 Aj+1 = 30,An Example: Insertion Sort,InsertionSort(A, n) for i = 2 to n key = Aij = i - 1;while (j 0) and (Aj key) Aj+1 = Ajj = j - 1Aj+1 = key ,10,30,30,40,1,2,3,4,i = 4j = 1key = 20Aj = 10 Aj+1 = 30,An Example: Insertion Sort,InsertionSort(A, n) for i = 2 to n key = Ai

25、j = i - 1;while (j 0) and (Aj key) Aj+1 = Ajj = j - 1Aj+1 = key ,10,20,30,40,1,2,3,4,i = 4j = 1key = 20Aj = 10 Aj+1 = 20,An Example: Insertion Sort,InsertionSort(A, n) for i = 2 to n key = Aij = i - 1;while (j 0) and (Aj key) Aj+1 = Ajj = j - 1Aj+1 = key ,10,20,30,40,1,2,3,4,i = 4j = 1key = 20Aj = 1

26、0 Aj+1 = 20,Done!,Animating Insertion Sort,Try it out with random, ascending, and descending inputs Homework:2.1-1, 2.1-2, 2.1-3,2.2 Analyzing algorithm, 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

27、 short sequences are easier to sort than long ones. Generally, we seek upper bounds on the running time, because everybody likes a guarantee.,时间复杂性和空间复杂性,P25-26详细讲解,Kinds of analyses,Worst-case: (usually) T(n) = maximum time of algorithm on any input of size n. Average-case: (sometimes) T(n) = expec

28、ted time of algorithm over all inputs of size n. Need assumption of statistical distribution of inputs.,P26,Best-case: (bogus) Cheat with a slow algorithm that works fast on some input.,Machine-independent time,What is insertion sorts worst-case time? It depends on the speed of our computer: relative speed (on the same machine), absolute speed (on different machines). BIG IDEA: Ignore machine-dependent constants. Look at growth of T(n) as n .,Inserti