南京理工大学算法设计与分析Algorithm Design and Analysis孙廷凯suntingkainjust.edu.cn南京理工大学课程内容 (32学时)常用的算法设计设计策略(包括分治策略、动态规划、贪心策略、回溯法、随机算法等)算法复杂度分析分析方法(计算迭代次数、使用递归方程、频度分析等)南京理工大学课程要求掌握常用的算法设计策略、算法复杂度分析方法授课方式：讲授考核方式：南京理工大学教材算法设计技巧与分析，M. H. Alsuwaiyel著, 电子工业出版社，吴伟昶等译，2004南京理工大学相关参考文献Algorithm Design Techniques and Analysis, M. H. Alsuwaiyel. (影印本). 电子工业出版社. 2003算法导论(第2版)，Thomas H. Cormen等著，潘金贵等译，机械工业出版社，2006.计算机算法设计与分析(第3版), 王晓东, 电子工业出版社, 2007.算法设计与分析，王红梅编著， 清华大学出版社， 2006.南京理工大学1 算法引论历史背景算法复杂度与渐近分析方法如何估计算法的复杂度算法复杂度分析的意义南京理工大学历史背景阶段1：二十世纪30年代，能否使用一个有效的过程来求解一个问题(相当于现在算法的概念)一直是人们所关注的。当时的焦点是将问题进行分类：可解或是不可解。关注问题是否可以求解的领域称为可计算理论(computability theory or theory of computation)。出现了一系列的计算模型，例如：calculus of Church、Post machines of Post、Turing machines of Turing、RAM model of computation。阶段2：随着数字计算机的出现，人们越来越关注于那些可求解的问题。一开始，人们满足于能够在一定的时间内解决一个特定的问题，而不去关注所需要的资源。慢慢地，人们需要考虑在有限资源的条件下高效地解决问题。这就导致了计算复杂度(computational complexity)这一新学科的诞生。在这个领域，主要是研究解决可求解问题时所需要的资源，主要是时间和空间复杂性。有时候，其他的资源也需要考虑，例如，通信代价、需要使用的处理器的个数(使用并行计算模型)等等。 南京理工大学引例：搜索问题给定已经排好序(不妨假设为非降序)的n个元素A1n ,现在要判定一个给定的元素x是否在此数组中出现。方法1：顺序搜索方法2：二分搜索南京理工大学二分搜索算法输入：非降序排列的数组A1n和元素x输出：如果x=Aj, 1 j n,则输出j,否则输出0.1. low1; high n; j02. while(low high) and (j=0)3. mid ( low+high)/24. if x=Amid then j mid5. else if xAmid then high mid-16. else low mid+17. end while8. return j南京理工大学分析最好情形：比较1次最坏情形：比较logn+1次每次循环都要抛弃一些元素，例如第二次循环时，剩余元素为A1mid-1或Amid+1n，不妨设为Amid+1n，则剩余的元素个数是n/2第j次while循环时，剩余元素的个数是n/2j-1或者找到x，或者程序在子序列长度达到1时终止搜索, 此时n/2j-1=1 1 n/2j-1 2 2j-1 n 2j logn 0 ，存在正整数n0 ，使得当n n0 时，有f (n) / g(n) ，则称函数f (n) 在n 充分大时的阶比g(n) 低，记为f (n) = o(g(n) 。 南京理工大学小结进行算法的时间复杂度分析，就是求其T(n)，并用O、或是以尽可能简单的形式进行表示。理想情况下，希望能够使用表示算法的时间复杂性。退而求其次，可以使用O或是。使用O时，希望估计的上界的阶越小越好。使用时，希望估计的下界的阶越大越好。南京理工大学算法耗费时间随问题规模的变化Algorithm1234 5Time function(ms)33n46n lg n13n23.4n32nInput size(n)Solution time100.00033 sec.0.0015 sec.0.0013 sec.0.0034 sec.0.001 sec.1000.0033 sec.0.03 sec.0.13 sec.3.4 sec.41016 yr.1,0000.033 sec.0.45 sec.13 sec.0.94 hr.10,0000.33 sec.6.1 sec.22 min.39 days100,0003.3 sec.1.3 min.1.5 days108 yr.Time allowedMaximum solvable input size (approx.)1 second30,0002,00028067201 minute1,800,00082,0002,20026026南京理工大学阶运算的几个实例= (1)= 解：因为所以(2)解: a. 因为有= b.又因为则有命题成立南京理工大学(3)解: 因为(不准确)a. b. 所以 换底公式 所以 亦即 1 2n1 2n+1南京理工大学(4)x南京理工大学估计算法的时间复杂度计算迭代次数使用递归方程频度分析南京理工大学计算迭代次数通常，程序的运行时间和程序的迭代次数成比例。因此计算程序的迭代次数就可以作为算法运行时间的指示器。这在很多算法中都可以得到应用，如查找、排序等等。南京理工大学计算迭代次数输入： n (n = 2k ， k 为某一正整数)输出：count1. count 0 2. while n 1 3. for j 1 to n4. count count+1 /执行一次耗费时间设为a5. end for6. n n/2 /执行一次耗费时间设为d 7. end while8. return count 分析：while 迭代的次数是k +1次(因为n1 可以写成n20, 运行过程n=2k20)，k = log n 。在每次while 循环里面for 依次执行n，n/2,n/4,1 次，所以，算法的时间复杂度为：南京理工大学思考？为什么在上面计算算法的时间复杂度时不考虑step 6 ,而只是考虑step 4呢？如果同时考虑 step 4和step 6，我们有：小结：使用计算迭代次数的技术来分析算法的时间复杂度时，只需要考虑最深层次的迭代。南京理工大学例：输入：正整数n输出：step 5 的执行次数1. count 02. for i 1 to n3. m n/i4. for j 1 to m5. count count+16. end for7. end for8. return count分析：Step5 的执行次数依次为： n, n/2, n/3, , n/n因为所以南京理工大学2 使用递归方程 输入：非降序排列的数组A1n和元素x输出：如果x=Aj, 1 j n,则输出j,否则输出0.1. low1; high n; j02. while(low high) and (j=0)3. mid ( low+high)/24. if x=Amid then j mid5. else if x10时，n310n2; 而n10时，n310n2，即复杂度为n3的算法更有效。在问题规模较小时，我们往往并不一味追求低复杂度的算法，而是更侧重于算法的简单性。当两个算法的渐近复杂度的阶相同时，必须进一步综合考察渐近复杂度表达式中的低阶及常数因子才能判别它们的优劣。例如：复杂度为n1ogn/l00 的算法显然比复杂度为l00n1ogn 的算法来得有效。