资源描述：
《算法设计与分析讲义》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。
1、第一章算法概述1、1算法与程序算法：是由若干条指令组成的的有穷序列，且满足下述儿条性质输入：有零个或多个外部量作为算法的输入。输出：算法产生至少一个量作为输出。确定性：组成算法的每条指令淸晰、无歧义。有限性：算法中每条指令的执行次数有限，执行每条指令的时间也有限。程序：是算法用某种程序设计语言的具体实现。程序可以不满足算法的性质(4)即有限性。1、2算法复杂性分析算法复杂性：是算法运行所需要的计算机资源的量，需要时间资源的量称为时间复杂性，需要的空间资源的量称为空间复杂性。这个量应该只依赖于算法要解的问题的规模、算法的输入和算法本身的函数。算法复杂性的函数表示：如果分别用
2、N、I和A表示算法要解问题的规模、算法的输入和算法本身，而且用C表示复杂性，那么，应该有C=F(N,I,A)o一般把时间复杂性和空间复杂性分开，并分别用T和S来表示，则有：T=T(N,I)和S=S(N,I)o(通常，让A隐含在复杂性函数名当中)我们只考虑三种情况下的吋I'可复杂度：最坏情况下：T証冈=曾T(NJ)=max工®阳(N.I)=£佔(N,门=疋乩圧鸟,=12-1最好情况下：T^(N)二mmT(NJ)=n)ni£亿(NJ)=fg(NJ)=f(N,I)胆2圧Q*2=12=1平均情况下:J(N)二工p⑴丁(N、D=工卩/ePv2=1其中Dn是规模为N的合法输入的集合；
3、I*是Dn中使T(N,I*)达到Tmax(N)的合法输入；是中使T(N,)达到Tmin(N)的合法输入；而P(l)是在算法的应用中出现输入I的槪率。算法复杂性在渐近意义下的阶：渐近意义下的记号：O、Q、8、o设f(N)和g(N)是定义在正数集上的正函数。0的定义：如果存在正的常数C和自然数No,使得当N'No时有f(N)£Cg(N),则称函数f(N)当N充分大时上有界，且g(N)是它的一个上界，记为f(N)二0(g(N))。即f(N)的阶不高于g(N)的阶。根据0的定义，容易证明它有如下运算规则：(1)O(f)+O(g)=O(max(f,g));(2)O(f)+O(g)=
4、O(Rg);(3)O(f>O(g)=O(fg);(4)如果g(N)=O(f(N)),则O(f)+O(g)=O(f)；(5)O(Cf(N))=O(f(N)),其中C是一个正的常数；⑹f=O(f)。Q的定义:如果存在正的常数C和自然数No,使得当N>二No时有f(N)>=Cg(N),则称函数f(N)当N充分大时下有界，且g(N)是它的一个下界，记为f(7)=Q(g(N))。即f(N)的阶不低于g(N)的阶。0的定义：对于任意给定的e>0,都存在正整数No,使得当屮N0时有f(N)/Cg(N)£e,则称函数f(N)当N充分大时的阶比g(7)低，记为f(N)二0(g(N))。。的
5、定义：定义f(N)=0(g(N))当且仅当f(N)=O(g(N))且f(N)二Q(g(N))。此吋称f(N)与g(N)同阶。例如,4NlogN+7二0(3N2+4NlogN+7)。第2章递归与分治策略算法总思路：将一个难以直接解决的大问题，分割成一些规模较小的相同问题，分而治之。对这k个子问题分别求解。如果子问题的规模仍然不够小，则再划分为k个子问题，如此递归的进行下去，直到问题规模足够小，很容易求出其解为止。将求出的小规模的问题的解合并为一个更大规模的问题的解，自底向上逐步求出原来问题的解。将求出的小规模的问题的解合并为一个更大规模的问题的解，自底向上逐步求出原来问题的
6、解。2、1递归的概念直接或间接地调用自身的算法称为递归算法。用函数自身给出定义的函数称为递归函数。由分治法产生的子问题往往是原问题的较小模式，这就为使用递归技术提供了方便。在这种情况下，反复应用分治手段，可以使子问题与原问题类型一致而其规模却不断缩小，最终使子问题缩小到很容易直接求出其解。这自然导致递归过程的产生。例1：阶乘函数分治与递归像一对李生兄弟，经常同时应用在算法设计之中，并由此产生许多高效算法。IJ17?=0边界条件［〃(〃一1)!72>0递归方程边界条件与递归方程是递归函数的二个要素，递归函数只有具备了这两个要素，才能在有限次计算后得出结果。递归函数intFa
7、ctorial(intn){if(n==0)return1;returnn*Factorial(n-1);}例2：Fibonacci数列无穷数列1,1,2,3,5,8,13,21,34,55,…，被称为Fibonacci数列。它可以递归地定义为：n=0[n=lp—边界条件斤>1递归方程1F（斤）=<1F（77-l）+F（n-2）第n个Fibonacci数可递归地计算如下：publicstaticintfibonacci(intn){if(n<=1)return1;returnfibonacci(n~l)+fibonacci(n
