文档介绍：第1章算法概述学****要点: ?理解算法的概念。?理解什么是程序,程序与算法的区别和内在联系。?掌握算法的计算复杂性概念。?掌握算法渐近复杂性的数学表述。?掌握用 C++ 语言描述算法的方法。算法(Algorithm) ?算法是指解决问题的一种方法或一个过程。?算法是若干指令的有穷序列,满足性质: ?(1) 输入:有外部提供的量作为算法的输入。?(2) 输出:算法产生至少一个量作为输出。?(3) 确定性:组成算法的每条指令是清晰,无歧义的。?(4) 有限性:算法中每条指令的执行次数是有限的,执行每条指令的时间也是有限的。程序(Program) ?程序是算法用某种程序设计语言的具体实现。?程序可以不满足算法的性质(4) 。?例如操作系统,是一个在无限循环中执行的程序,因而不是一个算法。?操作系统的各种任务可看成是单独的问题,每一个问题由操作系统中的一个子程序通过特定的算法来实现。该子程序得到输出结果后便终止。算法复杂性分析?算法复杂性 = 算法所需要的计算机资源?算法的时间复杂性 T(n); ?算法的空间复杂性 S(n)。?其中 n是问题的规模(输入大小)。算法的时间复杂性?(1)最坏情况下的时间复杂性? T max (n ) = max{ T (I) | size(I)= n } ?(2)最好情况下的时间复杂性? T min(n ) = min{ T (I) | size(I)= n } ?(3)平均情况下的时间复杂性? T avg(n ) = ?其中 I是问题的规模为 n的实例, p (I)是实例I出现的概率。??nI sizeITIp )()()( 算法渐近复杂性?T(n ) ?? , as n ?? ; ?(T(n ) - t(n ) )/ T(n ) ?0, as n ??; ?t(n)是T(n)的渐近性态,为算法的渐近复杂性。?在数学上, t(n)是T(n)的渐近表达式,是 T(n)略去低阶项留下的主项。它比 T(n ) 简单。第第2 2章章递归与分治策略递归与分治策略?将要求解的较大规模的问题分割成 k个更小规模的子问题。算法总体思想算法总体思想 n T(n/2) T(n/2) T(n/2) T(n/2) T(n) =?对这 k个子问题分别求解。如果子问题的规模仍然不够小,则再划分为 k个子问题, 如此递归的进行下去,直到问题规模足够小,很容易求出其解为止。算法总体思想?对这 k个子问题分别求解。如果子问题的规模仍然不够小,则再划分为 k个子问题, 如此递归的进行下去,直到问题规模足够小,很容易求出其解为止。 n T(n) = n/2 T(n/4) T(n/4) T(n/4) T(n/4) n/2 T(n/4) T(n/4) T(n/4) T(n/4) n/2 T(n/4) T(n/4) T(n/4) T(n/4) n/2 T(n/4) T(n/4) T(n/4) T(n/4) ?将求出的小规模的问题的解合并为一个更大规模的问题的解,自底向上逐步求出原来问题的解。算法总体思想?将求出的小规模的问题的解合并为一个更大规模的问题的解,自底向上逐步求出原来问题的解。 n T(n) = n/2 T(n/4) T(n/4) T(n/4) T(n/4) n/2 T(n/4) T(n/4) T(n/4) T(n/4) n/2 T(n/4) T(n/4) T(n/4) T(n/4) n/2 T(n/4) T(n/4) T(n/4) T(n/4)