算法导论-第一章-导论.ppt

1、Ch1 导论,Alogrithm算法,A well-defined computational procedure that takes some value, or set of values, as input and produces some value, or set of values, as output. （良定义的计算过程，良定义指的是满足五个要素:有穷性、确定性、可行性、有输入和输出，计算过程指的是一系列的计算步骤）,Algorithm,Note ：实例-计算一个解（输出）所有的输入,Application of algorithm,人类基因组计划 互联网 路由问题：寻找数

2、据由源节点到达目的节点的路径 搜索问题 制造业 电子商务,The problem of sorting,Input: sequence of n natural numbers Output: permutation such that a1a2an （重新排列）,Example -Input: -Output: ,Example of insertion sort,Example of insertion sort,Insertion sort,Analysis of algorithm 算法分析-估计算法所需要的资源,Analysis an algorithm: predicting th

3、e resources, including memory, communication bandwidth, or computer hardware and so on, that the algorithm requires,But most often we want to measure the computational time of an algorithm计算时间,Before we can analyze an algorithm, we must have a model of the implementation technology that will be used

4、, including a model for the resources of that technology and their costs计算模型,We shall assume a generic one-processor, random-access machine (RAM) model of computation随机存储器作为计算模型 指令一条接一条执行，没有并发操作 指令作为一个原子操作被执行，指令包括算术操作、逻辑操作、数据移动和控制操作 指令需要一个定量的执行时间 RAM容量足够大 ,Under RAM model: count fundamental operatio

5、ns计算基本操作数目,Analysis of algorithm 算法分析-估计算法所需要的资源,RAM model (RAM 模型),为了在RAM模型上分析算法，我需要： Combinatorics组合 Probability theory概率 Algebra代数 The ability to identify the most significant terms in a formula找出最重要项的能力,Main fact impacting on running time (影响运行时间的主要因素),Numbers of inputs输入规模 The distribution of i

6、nput, some (not all) algorithms can take different amounts of time to sort two different input sequence of the same size输入构成 Usually describe the running time of a program as a function of the input size通常将运行时间表示为输入的函数,Main fact impacting on running time (影响运行时间的主要因素),The running time of an algorith

7、m may depending on how the algorithm is implemented as well as what kind of data structure is used有时候运行时间和算法采用的数据结构有关系 Generally, we seek upper bounds on the running time, because everybody likes a guarantee,Input size(输入规模),输入规模依赖所研究的问题 对许多计算问题，其输入规模就是输入项的个数，例如排序和计算傅里叶变换(DFT)，输入数组的元素个数n即为输入规模(Input

8、 size) 对另外一些问题，例如两个整数相乘，其输入规模是输入在二进制表示下的位数 有时候用二个数来表示输入，例如输入是一个图,因此需要确定每个问题的输入规模,Running time(运行时间),运行时间是指执行的基本操作数（步数），基本操作独立于具体机器 假设每行代码花费的时间是常量Ci ，但每一行代码花费的时间可能不同,Running time(运行时间),Worst-case: (usually) -T(n) = maximum time of algorithm on any input of size n. 最坏情况下的运行时间，指的是size给定，任何输入实例的最长运行时间,A

9、verage-case: (sometimes) -T(n) = expected time of algorithm over all inputs of size n. -Need assumption of statistics distribution of inputs. 平均情况下的运行时间，指的是size给定，不同的实例分布的平均所需的运行时间,Best-case: (bogus) -Cheat with a slow algorithm that works fast on some input. 最好情况下的运行时间，指的是size给定，输入实例的最短运行时间,Running

10、 time(运行时间),The average running time is usually very hard to compute, we usually strive to analyze the worst case running time. The average case is often roughly as bad as the worst case平均情况难以分析，经常分析最坏情况 For some algorithms, worst-case occur fairly often最坏情况经常发生 比如在数据库中寻找一条信息，若该信息不在数据库中，则搜索算法的最坏情况发生

11、！ The worst case running time is an upper bound on the running time for any input, it is usually fairly easy to analyze and often close to the average or real running time最坏情况是上界,tj : the number of times the while loop test in line 5 is executed for the j value第5行中while循环所做的测试次数,cost times,c1,n,c2,n

12、-1,0,n-1,c4,n-1,c5,c6,c7,c8,n-1,Analysis of insertion sort,To compute T(n), the running time of Insertion-sort, we sum the products of the cost and times columns, obtaining,The best-case if the array is already sorted最好情况是数组已经有序tj=1,-The running time is a linear function of n线性函数,Analysis of inserti

13、on sort,The worst-case results if the array is in reverse sorted order- that is, in decreasing order最坏情况是数组是逆序tj=j,The running time is a quadratic function of n二次函数,Analysis of insertion sort,Analysis of insertion sort,The average-case:与输入的概率分布有关，假设对所有的数据出现的概率相等，tj=(j+1)/2,The running time is a quad

14、ratic function of n二次函数,Order of growth增长率,在算法分析过程中，通过抽象来简化分析过程，忽略每个语句的实际开销，代之以抽象的尝试Ci,“Asymptotic Analysis” （渐进分析）,Ignore not only the actual statement costs, but also the abstract costs Ci (using the constants a, b, and c是Ci的函数),对运行时间的增长率（速度）感兴趣，只考虑运行时间表达式中的最高次数项）（例如 an2）,忽略首次项的系数，例如 插入排序的最坏情况运行时间（又称为最坏情况时间复杂度）为 (n2),Order of growth增长率,Order of growth增长率,几个常见运行时间增长率,-notation,Math: (g(n) = f(n): There exist positive constants c1, c2, and n0 0 such that 0c1g(n) f(n)c2g(n) for all nn0,Engine