算法导论导论.pptx

Ch1 导论Alogrithm算法nA well-defined computational procedure that takes some value,or set of values,as input and produces some value,or set of values,as output.（良定义良定义的的计算过程计算过程，良定义指的是，良定义指的是满足五个要素满足五个要素:有穷性、确定性、可行性、有输入和输出，计有穷性、确定性、可行性、有输入和输出，计算过程指的是一系列的计算步骤）算过程指的是一系列的计算步骤）InputAlgorithmOutputNote：实例-计算一个解（输出）所有的输入Application of algorithmn人类基因组计划n互联网n路由问题：寻找数据由源节点到达目的节点的路径n搜索问题n制造业n电子商务The problem of sortingnInput:sequence of n natural numbersn Output:permutation such that a1a2an（重新排列）Example -Input:-Output:Example of insertion sortExample of insertion sortInsertion sortAnalysis of algorithm 算法分析-估计算法所需要的资源n Analysis an algorithm:predicting the resources,including memory,communication bandwidth,or computer hardware and so on,that the algorithm requiresn But most often we want to measure the computational time of an algorithm计算时间计算时间n Before we can analyze an algorithm,we must have a model of the implementation technology that will be used,including a model for the resources of that technology and their costs计算模型计算模型n We shall assume a generic one-processor,random-access machine(RAM)model of computation随机存储器作为计算模型n指令一条接一条执行，没有并发操作n指令作为一个原子操作被执行，指令包括算术操作、逻辑操作、数据移动和控制操作n指令需要一个定量的执行时间nRAM容量足够大nn Under RAM model:count fundamental operations计算基本操作数目计算基本操作数目Analysis of algorithm 算法分析-估计算法所需要的资源RAM model(RAM 模型)n为了在RAM模型上分析算法，我需要：nCombinatorics组合nProbability theory概率nAlgebra代数nThe ability to identify the most significant terms in a formula找出最重要项的能力Main fact impacting on running time(影响运行时间的主要因素)nNumbers of inputs输入规模nThe distribution of input,some(not all)algorithms can take different amounts of time to sort two different input sequence of the same size输入构成nUsually describe the running time of a program as a function of the input size通常将运行时间表示为输入的函数Main fact impacting on running time(影响运行时间的主要因素)nThe running time of an algorithm may depending on how the algorithm is implemented as well as what kind of data structure is used有时候运行时间和算法采用的数据结构有关系nGenerally,we seek upper bounds on the running time,because everybody likes a guaranteeInput size(输入规模)n输入规模依赖所研究的问题n对许多计算问题，其输入规模就是输入项的个数，例如排序和计算傅里叶变换(DFT)，输入数组的元素个数n即为输入规模(Input size)n对另外一些问题，例如两个整数相乘，其输入规模是输入在二进制表示下的位数n有时候用二个数来表示输入，例如输入是一个图因此需要确定每个问题的输入规模Running time(运行时间)n运行时间是指执行的基本操作数（步数），基本操作独立于具体机器n假设每行代码花费的时间是常量Ci，但每一行代码花费的时间可能不同Running time(运行时间)n Worst-case:(usually)-T(n)=maximum time of algorithm on any input of size n.最坏情况下的运行时间，指的是最坏情况下的运行时间，指的是size给定，任何输入实例的最给定，任何输入实例的最长运行时间长运行时间n Average-case:(sometimes)-T(n)=expected time of algorithm over all inputs of size n.-Need assumption of statistics distribution of inputs.平均情况下的运行时间，指的是平均情况下的运行时间，指的是size给定，不同的实例分布给定，不同的实例分布的平均所需的运行时间的平均所需的运行时间n Best-case:(bogus)-Cheat with a slow algorithm that works fast on some input.最好情况下的运行时间，指的是最好情况下的运行时间，指的是size给定，输入实例的最短给定，输入实例的最短运行时间运行时间Running time(运行时间)nThe 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平均情况难以分析，经常分析最坏情况nFor some algorithms,worst-case occur fairly often最坏情况经常发生 比如在数据库中寻找一条信息，若该信息不在数据库中，则搜索算法的最坏情况发生！nThe 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 timesc1nc2n-10n-1c4n-1c5c6c7c8n-1Analysis of insertion sortn To compute T(n),the running time of Insertion-sort,we sum the products of the cost and times columns,obtainingn The best-case if the array is already sorted最好情况是数组最好情况是数组已经有序已经有序tj=1-The running time is a linear function of n线性函数线性函数Analysis of insertion sortn The worst-case results if the array is in reverse sorted order-that is,in decreasing order最坏情况是最坏情况是数组是逆序数组是逆序tj=jnThe running time is a quadratic function of n二次二次函数函数Analysis of insertion sortAnalysis of insertion sortnThe average-case:与输入的概率分布有关，假设与输入的概率分布有关，假设对所有的数据出现的概率相等，对所有的数据出现的概率相等，tj=(j+1)/2nThe running time is a quadratic function of n二次二次函数函数Order of growth增长率n在算法分析过程中，通过抽象来简化分析过程，忽略每个语句的实际开销，代之以抽象的尝试Ci“Asymptotic Analysis”（渐进分析）（渐进分析）nIgnore not only the actual statement costs,but also the abstract costs Ci(using the constants a,b,and c是Ci的函数)n对运行时间的增长率（速度）感兴趣，只考虑运行时间表达式中的最高次数项）（例如 an2）n忽略首次项的系数，例如 插入排序的最坏情况运行时间（又称为最坏情况时间复杂度）为(n2)Order of growth增长率Order of growth增长率n几个常见运行时间增长率-notationn Math:(g(n)=f(n):There exist positive constants c1,c2,and n0 0 such that 0c1g(n)f(n)c2g(n)for all nn0n Engineering:nDrop low-order terms;ignore leading constants(忽略低次项、高次项的常数系数忽略低次项、高次项的常数系数)nExample:3n3+90n2 5n+6046=(n3)Asymptotic performancen When n gets larger enough,a(n2)algorithm always beats a(n3)algorithm思考题n Page 27,2.2-1,2.2-2