《1-算法与复杂性分析.ppt》由会员分享，可在线阅读，更多相关《1-算法与复杂性分析.ppt（66页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、计算机算法设计与分析计算机算法设计与分析算法与复杂性分析算法与复杂性分析姜大志姜大志汕头大学计算机系汕头大学计算机系计计 算算 机机 系系算法(Algorithm)算法是指解决问题的一种方法或一个过程。算法是若干指令的有穷序列，满足性质：(1)输入输入：有外部提供的量作为算法的输入。(2)输出输出：算法产生至少一个量作为输出。(3)确定性确定性：组成算法的每条指令是清晰，无歧义的。(4)有限性（有穷性）有限性（有穷性）：算法中每条指令的执行次数是有限的，执行每条指令的时间也是有限的。(5)可行性可行性：算法中执行的任何计算步都是可以被分解为基本的可执行的操作步，即每个计算步都可以在有限时间内完
2、成；（也称之为有效性）22022/12/25计计 算算 机机 系系程序(Program)程序是算法用某种程序设计语言的具体实现。程序可以不满足算法的性质(4)。例如操作系统，是一个在无限循环中执行的程序，因而不是一个算法。操作系统的各种任务可看成是单独的问题，每一个问题由操作系统中的一个子程序通过特定的算法来实现。该子程序得到输出结果后便终止。2022/12/253计计 算算 机机 系系问题求解(ProblemSolving)证明正确性分析算法设计程序理解问题精确解或近似解选择数据结构算法设计策略设计算法2022/12/254计计 算算 机机 系系构建模型模型的构建是理解问题的结果；模型：是对
3、实体的特征及变化规律的一种表示或抽象，即是把对象实体通过适当的过滤，用适当的表现规则描绘出的简洁的模仿品。2022/12/255模型的分类模型的分类（1）实体模型1、模拟模型2、事物模型（2）符号模型1、数学模型2、结构模型3、模仿模型4、科学符号5、描述模型理解问题和模型理解问题和模型构建是问题求解构建是问题求解的关键！的关键！计计 算算 机机 系系关于均值关于均值2/3的猜想的猜想在这个游戏中，要求所有参与者在不知道其他人选择的情况下，每人给出一个0到100之间的数字，所给出的数字最接近平均值2/3的那个人将会是获胜者。2022/12/256你将如何获胜？你将如何获胜？计计 算算 机机 系
4、系模型的构建1按照理性人的假设，参与者们应该会先排除不可能的数字。例如超过67的数字就不可能，因为当大家都选100时，平均值的三分之二才不过66。这样一来，每个人的选择又变成了在0到66之间选一个数，此时大于44的数字又变得没有意义了，接下来又是一个类似的循环直到最后，所有理性人的选择应该都为0。但是我相信在座并不是所有参与者都会遵照理性人的思路来思考这个问题，我假设有三分之一的人是任意的给出一数字，那么这三分之一人的均值的三分之二应该接近33，另外三分之一的人我们假定是进行这理性推理，选择的均值为0，最后三分之一我们我们考虑到存在一群和我有一样思维模式的人，认为一部分人理性一部分人不理性，那
5、么他会选择两者均值的2/3，所以他会取值11，在对这三种人的均值的猜想下求均值的2/3,得到我的猜想为10.2022/12/257计计 算算 机机 系系模型的构建2首先采用二八定律进行人群的划分，假设80%的人会在0到100之间随机选择一个数，那么可得80%的均值的2/3为33。还有20%的人是极度理性的人，他们选择平均数将在33左右间选择，设定为2838，这种人在28到38之间随机选择一个数。通过计算模拟后得出总体均值的2/3为31左右。程序见附件。2022/12/258计计 算算 机机 系系反思一个模型到底有多重要？一个模型到底有多重要？模型中最重要的组成部分是什么？模型中最重要的组成部分
6、是什么？你还能够构建哪些模型？你还能够构建哪些模型？2022/12/259计计 算算 机机 系系算法复杂性分析算法复杂性=算法所需要的计算机资源算法的时间复杂性T(n)；算法的空间复杂性S(n)。其中n是问题的规模（输入大小）。2022/12/2510计计 算算 机机 系系算法的时间复杂性算法的时间复杂性（1）最坏情况最坏情况下的时间复杂性 Tmax(n)=maxT(I)|size(I)=n（2）最好情况最好情况下的时间复杂性 Tmin(n)=minT(I)|size(I)=n（3）平均情况平均情况下的时间复杂性 Tavg(n)=其中I是问题的规模为n的实例，p(I)是实例I出现的概率。202
7、2/12/2511计计 算算 机机 系系算法渐近复杂性算法渐近复杂性T(n),asn;(T(n)-t(n)/T(n)0，asn;t(n)是T(n)的渐近性态，为算法的渐近复杂性。在数学上，t(n)是T(n)的渐近表达式，是T(n)略去低阶项留下的主项。它比T(n)简单。2022/12/2512计计 算算 机机 系系渐近分析的记号渐近分析的记号在下面的讨论中，对所有n，f(n)0，g(n)0。（1）渐近上界记号渐近上界记号OO(g(n)=f(n)|存在正常数c和n0使得对所有nn0有：0f(n)cg(n)（2）渐近下界记号渐近下界记号(g(n)=f(n)|存在正常数c和n0使得对所有nn0有：0
8、cg(n)f(n)2022/12/2513计计 算算 机机 系系（3）非紧上界记号非紧上界记号o o(g(n)=f(n)|对于任何正常数c0，存在正数和n00使得对所有nn0有：0f(n)0，存在正数和n00使得对所有nn0有：0cg(n)f(n)等价于 f(n)/g(n)，asn。f(n)(g(n)g(n)o(f(n)2022/12/2514计计 算算 机机 系系（5）紧渐近界记号紧渐近界记号(g(n)=f(n)|存在正常数c1,c2和n0使得对所有nn0有：c1g(n)f(n)c2g(n)定理定理1：(g(n)=O(g(n)(g(n)2022/12/2515计计 算算 机机 系系渐近分析记
9、号在等式和不等式中的意义渐近分析记号在等式和不等式中的意义f(n)=(g(n)的确切意义是：f(n)(g(n)。一般情况下，等式和不等式中的渐近记号(g(n)表示(g(n)中的某个函数。确切定义：有时可以直接从计算n趋于无穷时的极限得到一个紧渐近的界。基本上，当n趋于无穷时如果函数f(n)和g(n)之比趋于一个正常数，那么f(n)=(g(n)。2022/12/2516计计 算算 机机 系系渐近分析记号的若干性质渐近分析记号的若干性质（1）传递性：）传递性：f(n)=(g(n)，g(n)=(h(n)f(n)=(h(n)；f(n)=O(g(n)，g(n)=O(h(n)f(n)=O(h(n)；f(n
10、)=(g(n)，g(n)=(h(n)f(n)=(h(n)；f(n)=o(g(n)，g(n)=o(h(n)f(n)=o(h(n)；f(n)=(g(n)，g(n)=(h(n)f(n)=(h(n)；2022/12/2517计计 算算 机机 系系（2）反身性：）反身性：f(n)=(f(n)；f(n)=O(f(n)；f(n)=(f(n).（3）对称性：）对称性：f(n)=(g(n)g(n)=(f(n).（4）互对称性：）互对称性：f(n)=O(g(n)g(n)=(f(n)；f(n)=o(g(n)g(n)=(f(n)；2022/12/2518计计 算算 机机 系系（5）算术运算：）算术运算：O(f(n)+
11、O(g(n)=O(maxf(n),g(n)；O(f(n)+O(g(n)=O(f(n)+g(n)；O(f(n)*O(g(n)=O(f(n)*g(n)；O(cf(n)=O(f(n)；g(n)=O(f(n)O(f(n)+O(g(n)=O(f(n)。2022/12/2519计计 算算 机机 系系规则O(f(n)+O(g(n)=O(maxf(n),g(n)的证明：证明：对于任意f1(n)O(f(n)，存在正常数c1和自然数n1，使得对所有nn1，有f1(n)c1f(n)。类似地，对于任意g1(n)O(g(n)，存在正常数c2和自然数n2，使得对所有nn2，有g1(n)c2g(n)。令c3=maxc1,c
12、2，n3=maxn1,n2，h(n)=maxf(n),g(n)。则对所有的n n3，有f1(n)+g1(n)c1f(n)+c2g(n)c3f(n)+c3g(n)=c3(f(n)+g(n)c32maxf(n),g(n)=2c3h(n)=O(maxf(n),g(n).2022/12/2520计计 算算 机机 系系算法分析技术评价一个算法的代价，主要看执行算法时所需要占用的计算机空间的大小和计算过程需要花费的计算机CPU时间的多少。算法复杂性=算法所需要的计算机资源算法的分析主要包含时间和空间两个方面。2022/12/2521计计 算算 机机 系系算法的空间复杂性根据算法执行过程中对存储空间的使用方
13、式，可以把对算法空间代价分析分成两种：静态分析静态分析和动态分析动态分析。2022/12/2522计计 算算 机机 系系静态分析一个算法静态使用的存储空间，称为静态空间。静态分析的方法比较容易，只要求出算法中使用的所有变量的空间，再折合成多少空间存储单位空间存储单位即可。2022/12/2523计计 算算 机机 系系动态分析一个算法在执行过程中，必须以动态方式分配的存储空间是指在算法执行过程中才能分配的空间称为动态空间。2022/12/2524动态空间的确定主要由两种情况构成：（1）函数的递归；（2）执行动态分配函数计计 算算 机机 系系函数的递归调用对于递归函数而言，由于每次调用需要分配不同
14、的运行空间，所以递归函数的空间代价，不能简单地采用静态分析方法。2022/12/2525计计 算算 机机 系系执行动态分配函数一个函数（或过程）如果使用了malloc和free函数，malloc和free所开辟、释放的空间只能在算法执行过程中加以确定，这些空间属于动态空间。2022/12/2526计计 算算 机机 系系执行分配函数的两种情况没有使用free函数动态空间代价为O(k)，k为使用malloc的次数（包括在循环和递归调用中动态执行的次数）。2022/12/2527计计 算算 机机 系系执行分配函数的两种情况2022/12/2528使用使用free函数函数设free使用次数为j。令：0
15、，pi（i=1.j）为第i-1次使用free和次使用free之间执行malloc的次数。用公式i=i-1+pi-1可以计算出在第i-1次使用free和第i次使用free（i=1.j）之间使用的最大动态空间数。再定义j如下：于是整个算法使用的动态空间代价为：计计 算算 机机 系系算法分析中常见的复杂性函数2022/12/2529计计 算算 机机 系系算法时间效率的度量分析2022/12/2530常见函数的增长率计计 算算 机机 系系小规模数据2022/12/2531计计 算算 机机 系系中等规模数据2022/12/2532计计 算算 机机 系系时间代价分析clog2Nnn*Log2Nn2n32n
16、3nn!算法的执行时间绝大部分花在循环和递归上。2022/12/2533计计 算算 机机 系系算法分析方法2022/12/2534例：顺序搜索算法例：顺序搜索算法templateintseqSearch(Type*a,intn,Typek)for(inti=0;in;i+)if(ai=k)returni;return-1;计计 算算 机机 系系算法分析2022/12/2535（1）Tmax(n)=maxT(I)|size(I)=n=O(n)（2）Tmin(n)=minT(I)|size(I)=n=O(1)（3）在平均情况下，假设：(a)搜索成功的概率为p(0p1)；(b)在数组的每个位置i(0
17、i n)搜索成功的概率相同，均为p/n。计计 算算 机机 系系算法分析的基本原则2022/12/2536非递归算法：非递归算法：（1）for/while循环循环体内计算时间*循环次数；（2）嵌套循环循环体内计算时间*所有循环次数；（3）顺序语句各语句计算时间相加；（4）if-else语句if语句计算时间和else语句计算时间的较大者。计计 算算 机机 系系2022/12/2537templatevoidinsertion_sort(Type*a,intn)/插入排序插入排序Typekey;/costtimesfor(inti=1;i=0&ajkey)/c4sumoftiaj+1=aj;/c5s
18、umof(ti-1)j-;/c6sumog(ti-1)aj+1=key;/c7n-1计计 算算 机机 系系在最好情况下，ti=1,for1i n;在最坏情况下，tii+1,for1i 1时，可以把问题分解成a（a=1）个子问题的递归计算，每个子问题的规模是原来问题的b(b=1)分之一；分解问题和合并子问题解的花费为d(n)。整个问题的时间代价可以表示为下面一类递归方程的计算：计计 算算 机机 系系递归扩展过程如下：2022/12/2543计计 算算 机机 系系2022/12/2544设k，则又设d(x)为“积性函数”：d(x*y)=d(x)*d(y)计计 算算 机机 系系则有：2022/12/
19、2545计计 算算 机机 系系以下分三种情况讨论：（1）d(b)，则2022/12/2546计计 算算 机机 系系（2）d(b)，则2022/12/2547计计 算算 机机 系系（3）d(b)，则2022/12/2548计计 算算 机机 系系求快速排序快速排序法的时间代价。此算法的递归方程可表示为：T(n)T(n/2)n，这里，d(x)是积性函数。因为d(b)，所以2022/12/2549计计 算算 机机 系系讨论题你正在对不同的玻璃样品做强度测试以确定他们从多高的高度掉下来而仍旧不碎。对某类特定的瓶子如下设计这样一个实验。你有一个具有n个横档的阶梯，并且你想找出最高的横档，能使一个瓶子的样品
20、那哪里下落而不被摔破。你如何做？你如何做？2022/12/2550计计 算算 机机 系系解答二分搜索方法。时间复杂度为Log(n),但是缺点是你可能摔破一大堆的瓶子。如果主要目标是保护瓶子，从第一个横档开始让瓶子下落，然后第二个横档，每次向上爬一个高度知道瓶子摔破为止，这种方式只需要一个瓶子，但是可能的时间复杂度是n。时间复杂度和摔破瓶子之间是个不可调和的矛盾。假设只给你2个瓶子，描述一种找到最高安全横档的策略。2022/12/2551计计 算算 机机 系系作业构建一个模型求解3分之2猜想并用计算机程序实现。2022/12/2552计计 算算 机机 系系算法设计技术1分治法分治法(Divide
21、 and Conquer)是把一个规模为的问题分成两个或多个较小的与原问题类型相同的子问题，通过对子问题的求解，并把子问题的解合并起来从而构造出整个问题的解，即对问题分而治之分而治之。如果子问题的规模仍然相当大，可以对此子问题重复地应用分治策略。2022/12/2553计计 算算 机机 系系分治法实例二分法检索就是我们所学过的应用分治策略的典型的例子。快速排序算法，合并排序算法、梵塔问题等都可以用分治策略求解。快速排序算法每趟把一个元素放入排完序后它所应在的位置，这个位置把原表分成了两个宏观有序的子表；合并排序算法是把规模为的问题分成规模为n/2的两个子问题；梵塔问题分原问题为两个规模为n-1
22、的子问题。2022/12/2554计计 算算 机机 系系算法设计技术2贪心法：贪心法是一种不追求最优解，只希望得到较为满意解的方法。贪心法常以当前情况为基础作最优选择，而不考虑各种可能的整体情况，所以贪心法不要回溯。求着色问题近似解的贪心法贪心法(greedy)。基本思想为：先用一种颜色给尽可能多的结点上色，然后再用另一种颜色在未着色的结点中给尽可能多的结点上色，如此反复直到所有结点都被着色为止。Dijkstra的最短路径算法：求从源点到其它各结点的最短路径，它总是从那些最短路径还不知道的结点中挑选一个到源点最近的结点。2022/12/2555计计 算算 机机 系系算法设计技术3动态规划法有些
23、问题常常在分解时会产生大量的子问题，同时子问题界限不清，互相交叉，因而可能重复多次解同一个子问题。解决这种重复的方法：可以在得到每个子问题的解（包括其子子问题的解）时，把解保留在一个表格中，遇到相同的子问题时，就从表中找出来直接使用。这种方法就是动态规划法动态规划法（DynamicProgramming）2022/12/2556计计 算算 机机 系系动态规划法优势问题的规模越大，用动态规划法的好处就越明显地体现出来。填完整个表，得到题目所求，花的时间要大大快于不填表递归的求解所花的时间。2022/12/2557计计 算算 机机 系系例题-求组合数组合数有这样的一个递推式：每次求解可将其分为两个
24、子问题和。把按递推式分解得到下图的二叉树结构2022/12/2558计计 算算 机机 系系2022/12/2559首先，将的位置上以及0的位置上元素皆填为1。填某一中间表目时，只要把它右边表目的元素与右下方表目的元素之和填入即可。这样，很快就能求出10。计计 算算 机机 系系动态规划法与贪心法区别区别区别1动态规划法先求子问题的解，然后通过求解子问题构造原问题的解；而贪心算法是直接地解原问题。区别区别2动态规划法通过对若干局部最优解的比较，去掉了次优解，从而产生了更高一层次的局部最优解。相当于对较低层次的局部最优解进行贪心的选择而得到高一级的局部最优解，因而最终产生一个最高层次的局部最优解。而
25、贪心法每阶段只作一个挑选，各阶段的解一经选出就固定不变了，后阶段的局部最优是基于前阶段的挑选，所以往往只能求出次优解。2022/12/2560计计 算算 机机 系系动态规划法与分治法比较共同点共同点是:把一个大问题分解为若干较小的子问题，通过求解子问题而得到原问题的解。不同点不同点是：分治法每次分解的子问题数目比较少，子问题之间界限清楚，处理的过程通常是自顶向下自顶向下进行；动态规划法分解的子问题可能比较多，而且子问题相互包含，为了重用已经计算的结果，要把计算的中间结果全部保存起来，通常是自底向上自底向上进行。2022/12/2561计计 算算 机机 系系算法设计技术4回溯法有一类问题，要求找
26、到一个满足某些条件的最优解，如果进行彻底的搜索，要进行大量的比较，要以大量的运算时间为代价。回回溯溯法法（backtracking）求助于回溯技巧，常常可以大大地减少实际的搜索数目。2022/12/2562计计 算算 机机 系系回溯法本质由于回溯方法的本质是用深度优先的方法在解的空间树中搜索。所以在算法中都需要建立一个栈，用来保存搜索的路径。一旦产生的部分解序列不合要求，就要从栈中找到回溯的前一个位置，继续试探。2022/12/2563计计 算算 机机 系系算法设计技术5分枝界限法分枝界限法（branchandbound）也是一种在表示问题解空间的树上进行系统搜索的方法。所不同的是，回溯法使用
27、了深度优先策略，而分枝界限法一般采用广度优先策略，同时还采用最大收益（或最小损耗）策略来控制搜索的分枝。2022/12/2564计计 算算 机机 系系小结算法的分析主要包含时间和空间两个方面，空间代价分析分成两种情形：静态分析和动态分析。静态空间分析中，值得注意的是数组（静态数组），动态空间的确定主要考虑两种情况：函数的递归调用和空间的动态分配/回收。算法的执行时间绝大部分花在循环和递归上，循环的时间代价一般可以用加法规则和乘法规则估算；对于递归算法，一般可以解递归方程计算。2022/12/2565计计 算算 机机 系系分治法通过把问题化为较小的问题来解决原问题，从而简化或减少了原问题的复杂度；贪心法通过分阶段地挑选最优解，较快地得到整体的较好解，在问题要求不太严格的情况下，可以用这个较优解替代需要穷举所有情况才能得到的最优解；动态规划法用填表的方法保存了计算的中间结果，从而避免了大量重复的计算；回溯法跳过大量无须测试的元组，很快地得到需要的解。分枝界限法是在系统搜索问题解的空间时，加入上下界的条件检查以达到有效剪枝的目的。2022/12/2566