搜索
算法技术教研组谷方明东北师大附中1.算法的定义算法是对特定问题求解步骤的一种描述；它是指令的有限序列，其中每一条指令表示一个或多个操作。算法常用的描述方式有自然语言、流程图和程序等东北师大附中算法的特性1.有穷性一个算法必须在执行有穷步之后结束，并且每一步都在有穷时间内完成。2.确定性算法中的每一条指令必须有确切的含义，不存在二义性；算法只有一个入口和一个出口。3.可行性算法描述的操作都可以通过已实现的基本运算执行有限次来实现。4.输入一个算法有零个或多个输入，输入取自于某个特定的对象集合。5.输出一个算法有一个或多个输出，输出是同输入有着某些特定关系的量。东北师大附中2.算法的评价标准对于同一个问题，往往能够设计出许多不同的算法。对算法优劣的评定称为“算法评价”。算法评价主要有四个方面1.正确性正确性设计和评价一个算法的首要条件。一个正确的算法是指在合理的输入数据下，能在有限的运行时间内得到正确的结果（对OI而言）。2.简单性算法简单有利于阅读，也使得证明算法正确性容易，还有利于程序的编写、修改和调试。但是，算法简单往往并不有效。对于问题求解，我们更注意有效性，有效性比简单性更重要。3.效率：时间复杂性算法的效率指的是算法执行的时间。效率越高越有效。4.存储量需求：空间复杂性存储量需求指算法执行过程中所需要的最大存储空间。东北师大附中3算法效率的度量——时间复杂度事后统计计算机内部都有计时功能，有的甚至可精确到毫秒级，不同算法的程序可通过一组或若干组相同的统计数据以分辨优劣。缺点：1.需编制程序2.依赖计算机软硬件等环境因素，有时容易掩盖算法本身的优劣。事先分析从算法中选取一种对于所研究的问题（或算法类型）来说是基本运算的原操作（一般是算法中最耗时的操作），以该基本操作重复执行的次数作为算法的时间度量，称为算法的时间复杂度。例如：一个算法以加法为原操作，时间复杂度是108，则这个算法在计算机上执行约1秒（现在的计算机每秒约执行108次基本指令：加减比较等，即CPU参数：100MIPS）东北师大附中例：直接查找intfind(inta[],intn,intkey){for(inti=1;i=n;i++)if(a[i]==key)returnI;return0;}东北师大附中算法中基本操作重复执行的次还随问题的输入数据集不同而不同。最好时间复杂度：基本操作重复执行的最少次数最坏时间复杂度：基本操作重复执行的最多次数平均时间复杂度：基本操作重复执行的平均次数（难求）上例中最好时间复杂度：当key==a[1]，执行1次比较最坏时间复杂度：当key==a[n]，执行n次比较平均时间复杂度：当key==a[i]，执行i次比较；key不在a中，执行n次比较12)(11*11*...11*211*1*nnnnnnnnnpniii等设每种情况出现概率相东北师大附中算法的时间复杂度只依赖于问题的规模（通常用整数量n表示），或者说，是问题规模的函数，记为T(n)。渐进时间复杂度定义：如果存在两个正常数c和n0，对于所有的n≧n0，有︱f(n)︳≦c｜g(n)︳则记作f(n)=O(g(n))若算法的时间复杂度可记作T(n)=O(f(n))则称O(f(n))为算法的渐近时间复杂度，f(n)为算法的阶。算法的渐近时间复杂度表示的是当n趋于无穷时的算法的执行情况，也被简称为时间复杂度。东北师大附中例１：for(I=1，I=n;++I)for(j=1;j=n;++j){c[I][j]=0;for(k=1;k=n;++k)c[I][j]+=a[I][k]*b[k][j];}东北师大附中例1分析：以乘法为基本操作（乘除比加减耗时），由于是一个三重循环，每个循环从1到n，则总次数为:n×n×n=n3所以,时间复杂度为T(n)=O(n3)东北师大附中频度：是指该语句重复执行的次数例２{++x;s=0;}将x自增看成是基本操作，则语句频度为１，即时间复杂度为Ｏ(1)如果将s=0也看成是基本操作，则语句频度为２，其时间复杂度仍为Ｏ(1)，即常量阶。例３、for(I=1;I=n;++I){++x;s+=x;}语句频度为：2n,其时间复杂度为：O(n)，即时间复杂度为线性阶。东北师大附中例４for(I=1;I=n;++I)for(j=1;j=n;++j){++x;s+=x;}语句频度为：2n2其时间复杂度为：O(n2)即时间复杂度为平方阶。定理：若A(n)=amnm+am-1nm-1+…+a1n+a0是一个m次多项式，则A(n)=O(nm)东北师大附中例５for(i=2;i=n;++I)for(j=2;j=i-1;++j){++x;a[i，j]=x;}语句频度为：1+2+3+…+n-2=(1+n-2)×(n-2)/2=(n-1)(n-2)/2=n2-3n+2∴时间复杂度为O(n2)即此算法的时间复杂度为平方阶.一个算法时间为O(1)的算法，它的基本运算执行的次数是固定的。因此，总的时间由一个常数（即零次多项式）来限界。而一个时间为O(n2)的算法则由一个二次多项式来限界。东北师大附中以下六种计算算法时间的多项式是最常用的。其关系为：O(1)O(logn)O(n)O(nlogn)O(n2)O(n3)指数时间的关系为：O(2n)O(n!)O(nn)当n取得很大时，指数时间算法和多项式时间算法在所需时间上非常悬殊。因此，只要有人能将现有指数时间算法中的任何一个算法化简为多项式时间算法，那就取得了一个伟大的成就。东北师大附中NP=P?东北师大附中任一在非确定图灵机上多项式时间内完成的算法能否在确定图灵机上用多项式时间内完成？NPC问题（27个）旅行商问题（TravelingSalemanProblem，TSP）又译为旅行推销员问题、货郎担问题，简称为TSP问题，是最基本的路线问题，该问题是在寻求单一旅行者由起点出发，通过所有给定的需求点之后，最后再回到原点的最小路径成本。计算机科学的核心问题之一Hilbert的23个未解数学难题千禧年7大数学难题（100万美金）东北师大附中4算法的存储空间需求空间复杂度:算法所需存储空间的度量记作:S(n)=O(f(n))其中n为问题的规模(或大小)空间复杂度理论与时间复杂度类似东北师大附中课程内容算法分析正确性分析时空效率分析算法设计枚举法递推法递归法贪心法分治法动态规划模拟法