《2021年算法导论-第一章-导论PPT课件》由会员分享，可在线阅读，更多相关《2021年算法导论-第一章-导论PPT课件（26页珍藏版）》请在金锄头文库上搜索。
1、Ch1 导论12021Alogrithm算法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 ：实例-运算一个解（输出）全部的输入22021Application of algorithmn人类基
2、因组方案n互联网n路由问题：查找数据由源节点到达目的节点的路径n搜寻问题n制造业n电子商务32021The problem of sortingnInput: sequence of n natural numbersn Output: permutation such that a1a2an （重新排列） Example -Input: -Output: 42021Example of insertion sort52021Example of insertion sort62021Insertion sort72021Analysis of algorithm 算法分析-估运算法所需要的资
3、源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 im
4、plementation technology that will be used, including a model for the resources of that technology and their costs运算模型82021n We shall assume a generic one-processor, random-access machine (RAM) model of computation随机储备器作为运算模型n指令一条接一条执行，没有并发操作n指令作为一个原子操作被执行，指令包括算术操作，规律操作，数据移动和掌握操作n指令需要一个定量的执行时间nRAM容量足
5、够大nn Under RAM model: count fundamental operations运算基本操作数目Analysis of algorithm 算法分析-估运算法所需要的资源92021RAM model (RAM 模型)n为了在RAM模型上分析算法，我需要：nCombinatorics组合nProbability theory概率nAlgebra代数nThe ability to identify the most significant terms in a formula找出最重要项的才能102021Main fact impacting on running time (
6、影响运行时间的主要因素)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通常将运行时间表示为输入的函数112021Main fact impacting
7、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 guarantee122021Input size(输入规模)n输入规模依靠所争论
8、的问题n对很多运算问题，其输入规模就是输入项的个数，例如排序和运算傅里叶变换(DFT)，输入数组的元素个数n即为输入规模(Input size)n对另外一些问题，例如两个整数相乘，其输入规模是输入在二进制表示下的位数n有时候用二个数来表示输入，例如输入是一个图因此需要确定每个问题的输入规模132021Running time(运行时间)n运行时间是指执行的基本操作数（步数），基本操作独立于具体机器n假设每行代码花费的时间是常量Ci ，但每一行代码花费的时间可能不同142021Running time(运行时间)n Worst-case: (usually) n -T(n) = maximum
9、time of algorithm on any input of size n.n最坏情形下的运行时间，指的是size给定，任何输入实例的最长运行时间n Average-case: (sometimes)n -T(n) = expected time of algorithm over all inputs of size n.n -Need assumption of statistics distribution of inputs.n平均情形下的运行时间，指的是size给定，不同的实例分布的平均所需的运行时间n Best-case: (bogus)n -Cheat with a slo
10、w algorithm that works fast on some input.n最好情形下的运行时间，指的是size给定，输入实例的最短运行时间152021Running 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
11、 algorithms, worst-case occur fairly often最坏情形常常发生n 比如在数据库中查找一条信息，如该信息不在数据库中，就搜寻算法的最坏情形发生！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最坏情形是上界162021tj : the number of times th
12、e while loop test in line 5 is executed for the j value第5行中while循环所做的测试次数cost timesc1nc2n-10n-1c4n-1c5c6c7c8n-1Analysis of insertion sort172021n 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 so
13、rted最好情形是数组已经有序tj=1-The running time is a linear function of n线性函数Analysis of insertion sort182021n 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 sort192021Analysis of
14、insertion sortnThe average-case:与输入的概率分布有关，假设对全部的数据显现的概率相等，tj=(j+1)/2nThe running time is a quadratic function of n二次函数202021Order of growth增长率n在算法分析过程中，通过抽象来简化分析过程，忽视每个语句的实际开销，代之以抽象的尝试Ci“Asymptotic Analysis” （渐进分析）nIgnore not only the actual statement costs, but also the abstract costs Ci (using th
15、e constants a, b, and c是Ci的函数)n对运行时间的增长率（速度）感爱好，只考虑运行时间表达式中的最高次数项）（例如 an2）n忽视首次项的系数，例如 插入排序的最坏情形运行时间（又称为最坏情形时间复杂度）为 (n2)212021Order of growth增长率222021Order of growth增长率n几个常见运行时间增长率232021-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 constantsn(忽视低次项，高次项的常数系数)nExample: 3n3 + 90n2 5n + 6046 = (n3)242021Asymptotic performancen When n gets larger enough, a (n2) algorithm always beats a (n3) algorithm252021摸索题n Page 27, 2.2-1, 2.2-2262021
