算法的时间复杂度和空间复杂度-总结 - mmmelody的博客 - CSDN博客
算法的时间复杂度和空间复杂度-总结
计算机原理
算法的时间复杂度和空间复杂度-总结
&&&&&&& 通常，对于一个给定的算法，我们要做 两项分析。第一是从数学上证明算法的正确性，这一步主要用到形式化证明的方法及相关推理模式，如循环不变式、数学归纳法等。而在证明算法是正确的基础上，第二部就是分析算法的时间复杂度。算法的时间复杂度反映了程序执行时间随输入规模增长而增长的量级，在很大程度上能很好反映出算法的优劣与否。因此，作为程序员，掌握基本的算法时间复杂度分析方法是很有必要的。
&&&&&& 算法执行时间需通过依据该算法编制的程序在计算机上运行时所消耗的时间来度量。而度量一个程序的执行时间通常有两种方法。
一、事后统计的方法
&&&&&&&&这种方法可行，但不是一个好的方法。该方法有两个缺陷：一是要想对设计的算法的运行性能进行评测，必须先依据算法编制相应的程序并实际运行；二是所得时间的统计量依赖于计算机的硬件、软件等环境因素，有时容易掩盖算法本身的优势。
二、事前分析估算的方法
&&&&&&& 因事后统计方法更多的依赖于计算机的硬件、软件等环境因素，有时容易掩盖算法本身的优劣。因此人们常常采用事前分析估算的方法。
在编写程序前，依据统计方法对算法进行估算。一个用高级语言编写的程序在计算机上运行时所消耗的时间取决于下列因素：
&&&&&&(1).&算法采用的策略、方法；(2).&编译产生的代码质量；(3).&问题的输入规模；(4).&&机器执行指令的速度。
&&&&&一个算法是由控制结构（顺序、分支和循环3种）和原操作（指固有数据类型的操作）构成的，则算法时间取决于两者的综合效果。为了便于比较同一个问题的不同算法，通常的做法是，从算法中选取一种对于所研究的问题（或算法类型）来说是基本操作的原操作，以该基本操作的重复执行的次数作为算法的时间量度。
1、时间复杂度&
（1）时间频度&一个算法执行所耗费的时间，从理论上是不能算出来的，必须上机运行测试才能知道。但我们不可能也没有必要对每个算法都上机测试，只需知道哪个算法花费的时间多，哪个算法花费的时间少就可以了。并且一个算法花费的时间与算法中语句的执行次数成正比例，哪个算法中语句执行次数多，它花费时间就多。一个算法中的语句执行次数称为语句频度或时间频度。记为T(n)。
（2）时间复杂度&在刚才提到的时间频度中，n称为问题的规模，当n不断变化时，时间频度T(n)也会不断变化。但有时我们想知道它变化时呈现什么规律。为此，我们引入时间复杂度概念。 一般情况下，算法中基本操作重复执行的次数是问题规模n的某个函数，用T(n)表示，若有某个辅助函数f(n),使得当n趋近于无穷大时，T(n)/f(n)的极限值为不等于零的常数，则称f(n)是T(n)的同数量级函数。记作T(n)=Ｏ(f(n)),称Ｏ(f(n))&为算法的渐进时间复杂度，简称时间复杂度。
&&&&&&&另外，上面公式中用到的 Landau符号其实是由德国数论学家保罗·巴赫曼（Paul Bachmann）在其1892年的著作《解析数论》首先引入，由另一位德国数论学家艾德蒙·朗道（Edmund Landau）推广。Landau符号的作用在于用简单的函数来描述复杂函数行为，给出一个上或下（确）界。在计算算法复杂度时一般只用到大O符号，Landau符号体系中的小o符号、Θ符号等等比较不常用。这里的O，最初是用大写希腊字母，但现在都用大写英语字母O；小o符号也是用小写英语字母o，Θ符号则维持大写希腊字母Θ。
&&&&&& &T (n) = Ο(f (n))&表示存在一个常数C，使得在当n趋于正无穷时总有&T (n) ≤ C * f(n)。简单来说，就是T(n)在n趋于正无穷时最大也就跟f(n)差不多大。也就是说当n趋于正无穷时T (n)的上界是C * f(n)。其虽然对f(n)没有规定，但是一般都是取尽可能简单的函数。例如，O(2n2+n
+1) = O (3n2+n+3) = O (7n2&+
n) =&O (&n2&)&，一般都只用O(n2)表示就可以了。注意到大O符号里隐藏着一个常数C，所以f(n)里一般不加系数。如果把T(n)当做一棵树，那么O(f(n))所表达的就是树干，只关心其中的主干，其他的细枝末节全都抛弃不管。
&&&&&&& 在各种不同算法中，若算法中语句执行次数为一个常数，则时间复杂度为O(1),另外，在时间频度不相同时，时间复杂度有可能相同，如T(n)=n2+3n+4与T(n)=4n2+2n+1它们的频度不同，但时间复杂度相同，都为O(n2)。
按数量级递增排列，常见的时间复杂度有：常数阶O(1),对数阶O(log2n),线性阶O(n),&线性对数阶O(nlog2n),平方阶O(n2)，立方阶O(n3),...，
k次方阶O(nk),指数阶O(2n)。随着问题规模n的不断增大，上述时间复杂度不断增大，算法的执行效率越低。
&&&从图中可见，我们应该尽可能选用多项式阶O(nk)的算法，而不希望用指数阶的算法。
&&&&& 常见的算法时间复杂度由小到大依次为：Ο(1)＜Ο(log2n)＜Ο(n)＜Ο(nlog2n)＜Ο(n2)＜Ο(n3)＜…＜Ο(2n)＜Ο(n!)
&&&&&& 一般情况下，对一个问题（或一类算法）只需选择一种基本操作来讨论算法的时间复杂度即可，有时也需要同时考虑几种基本操作，甚至可以对不同的操作赋予不同的权值，以反映执行不同操作所需的相对时间，这种做法便于综合比较解决同一问题的两种完全不同的算法。
（3）求解算法的时间复杂度的具体步骤是：
　　⑴ 找出算法中的基本语句；
　　算法中执行次数最多的那条语句就是基本语句，通常是最内层循环的循环体。
　　⑵ 计算基本语句的执行次数的数量级；
　　只需计算基本语句执行次数的数量级，这就意味着只要保证基本语句执行次数的函数中的最高次幂正确即可，可以忽略所有低次幂和最高次幂的系数。这样能够简化算法分析，并且使注意力集中在最重要的一点上：增长率。
　　⑶ 用大Ο记号表示算法的时间性能。
　　将基本语句执行次数的数量级放入大Ο记号中。
　　如果算法中包含嵌套的循环，则基本语句通常是最内层的循环体，如果算法中包含并列的循环，则将并列循环的时间复杂度相加。例如：
　　第一个for循环的时间复杂度为Ο(n)，第二个for循环的时间复杂度为Ο(n2)，则整个算法的时间复杂度为Ο(n+n2)=Ο(n2)。
　　Ο(1)表示基本语句的执行次数是一个常数，一般来说，只要算法中不存在循环语句，其时间复杂度就是Ο(1)。其中Ο(log2n)、Ο(n)、
Ο(nlog2n)、Ο(n2)和Ο(n3)称为多项式时间，而Ο(2n)和Ο(n!)称为指数时间。计算机科学家普遍认为前者（即多项式时间复杂度的算法）是有效算法，把这类问题称为P（Polynomial,多项式）类问题，而把后者（即指数时间复杂度的算法）称为NP（Non-Deterministic
Polynomial, 非确定多项式）问题。
&&&&&&& 一般来说多项式级的复杂度是可以接受的，很多问题都有多项式级的解——也就是说，这样的问题，对于一个规模是n的输入，在n^k的时间内得到结果，称为P问题。有些问题要复杂些，没有多项式时间的解，但是可以在多项式时间里验证某个猜测是不是正确。比如问是不是质数？如果要直接入手的话，那么要把小于的平方根的所有素数都拿出来，看看能不能整除。还好欧拉告诉我们，这个数等于641和6700417的乘积，不是素数，很好验证的，顺便麻烦转告费马他的猜想不成立。大数分解、Hamilton回路之类的问题，都是可以多项式时间内验证一个“解”是否正确，这类问题叫做NP问题。
（4）在计算算法时间复杂度时有以下几个简单的程序分析法则:
(1).对于一些简单的输入输出语句或赋值语句,近似认为需要O(1)时间
(2).对于顺序结构,需要依次执行一系列语句所用的时间可采用大O下&求和法则&
求和法则:是指若算法的2个部分时间复杂度分别为 T1(n)=O(f(n))和 T2(n)=O(g(n)),则 T1(n)+T2(n)=O(max(f(n), g(n)))
特别地,若T1(m)=O(f(m)), T2(n)=O(g(n)),则 T1(m)+T2(n)=O(f(m) + g(n))
(3).对于选择结构,如if语句,它的主要时间耗费是在执行then字句或else字句所用的时间,需注意的是检验条件也需要O(1)时间
(4).对于循环结构,循环语句的运行时间主要体现在多次迭代中执行循环体以及检验循环条件的时间耗费,一般可用大O下&乘法法则&
乘法法则: 是指若算法的2个部分时间复杂度分别为 T1(n)=O(f(n))和 T2(n)=O(g(n)),则 T1*T2=O(f(n)*g(n))
(5).对于复杂的算法,可以将它分成几个容易估算的部分,然后利用求和法则和乘法法则技术整个算法的时间复杂度
另外还有以下2个运算法则:(1) 若g(n)=O(f(n)),则O(f(n))+ O(g(n))= O(f(n))；(2) O(Cf(n)) = O(f(n)),其中C是一个正常数
&（5）下面分别对几个常见的时间复杂度进行示例说明：
&&&&&&& Temp=i; i=j; j=&&&&&&&&&&&&&&&&&&&&
以上三条单个语句的频度均为1，该程序段的执行时间是一个与问题规模n无关的常数。算法的时间复杂度为常数阶，记作T(n)=O(1)。注意：如果算法的执行时间不随着问题规模n的增加而增长，即使算法中有上千条语句，其执行时间也不过是一个较大的常数。此类算法的时间复杂度是O(1)。
(2)、O(n2)
2.1. 交换i和j的内容
解：因为Θ(2n2+n+1)=n2（Θ即：去低阶项，去掉常数项，去掉高阶项的常参得到），所以T(n)=
解： 语句1的频度是n-1
&&&&&&&&& 语句2的频度是(n-1)*(2n+1)=2n2-n-1
&&&&&&&&& f(n)=2n2-n-1+(n-1)=2n2-2；
&&&&&&& 又Θ(2n2-2)=n2
&&&&&&&&& 该程序的时间复杂度T(n)=O(n2).&&
　　一般情况下，对步进循环语句只需考虑循环体中语句的执行次数，忽略该语句中步长加1、终值判别、控制转移等成分，当有若干个循环语句时，算法的时间复杂度是由嵌套层数最多的循环语句中最内层语句的频度f(n)决定的。&&&&&
(3)、O(n)&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&
解： 语句1的频度：2,&&&&&&&&
&&&&&&&&&& 语句2的频度： n,&&&&&&&&
&&&&&&&&& 语句3的频度： n-1,&&&&&&&&
&&&&&&&&& 语句4的频度：n-1,&&&&
&&&&&&&&& 语句5的频度：n-1,&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&
&&&&&&&&& T(n)=2+n+3(n-1)=4n-1=O(n).
(4)、O(log2n)
解： 语句1的频度是1,&&
&&&&&&&&& 设语句2的频度是f(n),&& 则：2^f(n)&=n;f(n)&=log2n&&&&
&&&&&&&&& 取最大值f(n)=log2n,
&&&&&&&&& T(n)=O(log2n&)
(5)、O(n3)&
解：当i=m, j=k的时候,内层循环的次数为k当i=m时, j 可以取 0,1,...,m-1 , 所以这里最内循环共进行了0+1+...+m-1=(m-1)m/2次所以,i从0取到n, 则循环共进行了: 0+(1-1)*1/2+...+(n-1)n/2=n(n+1)(n-1)/6所以时间复杂度为O(n3).
（5）常用的算法的时间复杂度和空间复杂度
一个经验规则：其中c是一个常量，如果一个算法的复杂度为c 、&log2n&、n 、 n*log2n&,那么这个算法时间效率比较高
，如果是2n&,3n&,n!，那么稍微大一些的n就会令这个算法不能动了，居于中间的几个则差强人意。
&&&&&&&算法时间复杂度分析是一个很重要的问题，任何一个程序员都应该熟练掌握其概念和基本方法，而且要善于从数学层面上探寻其本质，才能准确理解其内涵。
2、算法的空间复杂度
&&&&&&& 类似于时间复杂度的讨论，一个算法的空间复杂度(Space Complexity)S(n)定义为该算法所耗费的存储空间，它也是问题规模n的函数。渐近空间复杂度也常常简称为空间复杂度。
空间复杂度(Space Complexity)是对一个算法在运行过程中临时占用存储空间大小的量度。一个算法在计算机存储器上所占用的存储空间，包括存储算法本身所占用的存储空间，算法的输入输出数据所占用的存储空间和算法在运行过程中临时占用的存储空间这三个方面。算法的输入输出数据所占用的存储空间是由要解决的问题决定的，是通过参数表由调用函数传递而来的，它不随本算法的不同而改变。存储算法本身所占用的存储空间与算法书写的长短成正比，要压缩这方面的存储空间，就必须编写出较短的算法。算法在运行过程中临时占用的存储空间随算法的不同而异，有的算法只需要占用少量的临时工作单元，而且不随问题规模的大小而改变，我们称这种算法是“就地\&进行的，是节省存储的算法，如这一节介绍过的几个算法都是如此；有的算法需要占用的临时工作单元数与解决问题的规模n有关，它随着n的增大而增大，当n较大时，将占用较多的存储单元，例如将在第九章介绍的快速排序和归并排序算法就属于这种情况。
如当一个算法的空间复杂度为一个常量，即不随被处理数据量n的大小而改变时，可表示为O(1)；当一个算法的空间复杂度与以2为底的n的对数成正比时，可表示为0(10g2n)；当一个算法的空I司复杂度与n成线性比例关系时，可表示为0(n).若形参为数组，则只需要为它分配一个存储由实参传送来的一个地址指针的空间，即一个机器字长空间；若形参为引用方式，则也只需要为其分配存储一个地址的空间，用它来存储对应实参变量的地址，以便由系统自动引用实参变量。
原文链接：
我的热门文章您所在位置： &
&nbsp&&nbsp&nbsp&&nbsp
时间复杂度的几种计算方法.pdf 3页
本文档一共被下载：
次 ,您可全文免费在线阅读后下载本文档。
下载提示
1.本站不保证该用户上传的文档完整性，不预览、不比对内容而直接下载产生的反悔问题本站不予受理。
2.该文档所得收入(下载+内容+预览三)归上传者、原创者。
3.登录后可充值，立即自动返金币，充值渠道很便利
需要金币：100 &&
时间复杂度的几种计算方法,时间复杂度的计算方法,时间复杂度计算方法,时间复杂度的计算,时间复杂度计算,算法时间复杂度计算,如何计算时间复杂度,怎么计算时间复杂度,算法复杂度的计算方法,递归时间复杂度的计算
你可能关注的文档：
··········
··········
E-mail: eduf@
Computer Knowledge and Technology
电脑知识与技术
Computer Knowledge and Technology 电脑知识与技术
Vol.7, No.19, July 2011.
Tel:+86-551-5690963
时间复杂度的几种计算方法
刘怀愚，朱昌杰，李璟
（淮北师范大学计算机科学与技术学院，安徽淮北 235000 ）
摘要：算法的时间复杂度是反映算法优劣的重要指标，是《数据结构》 的重要理论基础，是学习和教学过程中贯穿始终的主要线索。
但是由于概念的抽象和计算方法的繁琐，使算法时间复杂度成为最难理解和掌握的问题之一。 在总结教学经验的基础上，该文提出
几种常用的时间复杂度计算方法，使对该知识点的教学和学习变得系统和简单。
关键词：数据结构；时间复杂度；渐进时间复杂度；迭代法
中图分类号：
文献标识码：
文章编号：
11)19-4636-03
Several Calculation Methods of Time Complexity
LIU Huai-yu, ZHU Chang-jie, LI Jing
(Schoof of Computer Science and Technology, Huaibei Normal University, Huaibei 235000, China)
Time complexity is an important index in algorithm in terms of reflecting the quality of the algorithm. Time complexity is also
an important theoretical basis in Data Structure, thus is regarded as a major clue throughout learning and teaching process. However, due to
the abstractness of the concept and the tedious calculation method, time complexity of the algorithm becomes a most difficult issue to un-
experiences,
complexity with the aim of simplifying the teaching and learning of the knowledge point in a systematic approach.
Key words: D Time C Asymptotic Time C Iteration method
正在加载中，请稍后...2193人阅读
算法学习（7）
算法复杂度是在《数据结构》这门课程的第一章里出现的，因为它稍微涉及到一些数学问题，所以很多同学感觉很难，加上这个概念也不是那么具体，更让许多同学复习起来无从下手，下面我们就这个问题给各位考生进行分析。
首先了解一下几个概念。一个是时间复杂度，一个是渐近时间复杂度。前者是某个算法的时间耗费，它是该算法所求解问题规模n的函数，而后者是指当问题规模趋向无穷大时，该算法时间复杂度的数量级。&
当我们评价一个算法的时间性能时，主要标准就是算法的渐近时间复杂度，因此，在算法分析时，往往对两者不予区分，经常是将渐近时间复杂度T(n)=O(f(n))简称为时间复杂度，其中的f(n)一般是算法中频度最大的语句频度。
此外，算法中语句的频度不仅与问题规模有关，还与输入实例中各元素的取值相关。但是我们总是考虑在最坏的情况下的时间复杂度。以保证算法的运行时间不会比它更长。
常见的时间复杂度，按数量级递增排列依次为：常数阶O(1)、对数阶O(log2n)、线性阶O(n)、线性对数阶O(nlog2n)、平方阶O(n^2)、立方阶O(n^3)、k次方阶O(n^k)、指数阶O(2^n)。
下面我们通过例子加以说明，让大家碰到问题时知道如何去解决。
1、设三个函数f,g,h分别为 f(n)=100n^3+n^2+1000 , g(n)=25n^3+5000n^2 , h(n)=n^1.5+5000nlgn&
请判断下列关系是否成立：
（1） f(n)=O(g(n))&
（2） g(n)=O(f(n))&
（3） h(n)=O(n^1.5)
（4） h(n)=O(nlgn)
这里我们复习一下渐近时间复杂度的表示法T(n)=O(f(n))，这里的&O&是数学符号，它的严格定义是&若T(n)和f(n)是定义在正整数集合上的两个函数，则T(n)=O(f(n))表示存在正的常数C和n0 ,使得当n≥n0时都满足0≤T(n)≤C?f(n)。&用容易理解的话说就是这两个函数当整型自变量n趋向于无穷大时，两者的比值是一个不等于0的常数。这么一来，就好计算了吧。&
◆ (1)成立。题中由于两个函数的最高次项都是n^3,因此当n→∞时，两个函数的比值是一个常数，所以这个关系式是成立的。&
◆ （2）成立。与上同理。
◆ （3）成立。与上同理。
◆ （4）不成立。由于当n→∞时n^1.5比nlgn递增的快，所以h(n)与nlgn的比值不是常数，故不成立。
2、设n为正整数，利用大&O&记号，将下列程序段的执行时间表示为n的函数。
(1) i=1; k=0&
while(i&n)
{ k=k+10*i;i++;
解答：T(n)=n-1， T(n)=O(n)， 这个函数是按线性阶递增的。
(2) x=n; // n&1&
while (x&=(y+1)*(y+1))
y++;
解答：T(n)=n1/2 ，T(n)=O(n1/2)， 最坏的情况是y=0，那么循环的次数是n1/2次，这是一个按平方根阶递增的函数。
(3) x=91; y=100;&
while(y&0)
{x=x-10;y--;}
else x++;
解答： T(n)=O(1)， 这个程序看起来有点吓人，总共循环运行了1000次，但是我们看到n没有? 没。这段程序的运行是和n无关的，就算它再循环一万年，我们也不管他，只是一个常数阶的函数。
1、算法的时间性能分析
（1）算法耗费的时间和语句频度
　　 一个算法所耗费的时间=算法中每条语句的执行时间之和
每条语句的执行时间=语句的执行次数(即频度(Frequency Count))×语句执行一次所需时间
&&&&算法转换为程序后，每条语句执行一次所需的时间取决于机器的指令性能、速度以及编译所产生的代码质量等难以确定的因素。
&&&&若要独立于机器的软、硬件系统来分析算法的时间耗费，则设每条语句执行一次所需的时间均是单位时间，一个算法的时间耗费就是该算法中所有语句的频度之和。
求两个n阶方阵的乘积&C=A×B,其算法如下:
# define n 100 // n&可根据需要定义,这里假定为100
void MatrixMultiply(int A[a]，int B [n][n]，int C[n][n])
{ //右边列为各语句的频度
int i ,j ,k;
(1) for(i=0; i＜n;j++) n+1
(2)&&&& for (j=0;j＜n;j++) { n(n+1)
(3)&&&&&& C[i][j]=0; n2
(4)&&&&&& for (k=0; k＜n; k++) n2(n+1)
(5)&&&&&&&& C[i][j]=C[i][j]+A[i][k]*B[k][j]; n3
&&&&&&&& }
&&&&该算法中所有语句的频度之和(即算法的时间耗费)为：
&&&&&&&&&& T(n)=2n3+3n2+2n+1 (1.1)
　　 语句(1)的循环控制变量i要增加到n，测试到i=n成立才会终止。故它的频度是n+1。但是它的循环体却只能执行n次。语句(2)作为语句(1)循环体内的语句应该执行n次，但语句(2)本身要执行n+1次，所以语句(2)的频度是n(n+1)。同理可得语句(3)，(4)和(5)的频度分别是n2，n2(n+1)和n3。&
　　 算法MatrixMultiply的时间耗费T(n)是矩阵阶数n的函数。
（2）问题规模和算法的时间复杂度
&&&&算法求解问题的输入量称为问题的规模(Size),一般用一个整数表示。
矩阵乘积问题的规模是矩阵的阶数。
一个图论问题的规模则是图中的顶点数或边数。
　　 一个算法的时间复杂度(Time Complexity,&也称时间复杂性)T(n)是该算法的时间耗费，是该算法所求解问题规模n的函数。当问题的规模n趋向无穷大时，时间复杂度T(n)的数量级(阶)称为算法的渐进时间复杂度。
算法MatrixMultidy的时间复杂度T(n)如(1.1)式所示，当n趋向无穷大时，显然有
　　 这表明，当n充分大时，T(n)和n3之比是一个不等于零的常数。即T(n)和n3是同阶的，或者说T(n)和n3的数量级相同。记作T(n)=O(n3)是算法MatrixMultiply的渐近时间复杂度。
（3）渐进时间复杂度评价算法时间性能
　　主要用算法时间复杂度的数量级(即算法的渐近时间复杂度)评价一个算法的时间性能。
算法MatrixMultiply的时间复杂度一般为T(n)=O(n3)，f(n)=n3是该算法中语句(5)的频度。下面再举例说明如何求算法的时间复杂度。
交换i和j的内容。
&&&&& Temp=i;
&&&&& i=j;
　　以上三条单个语句的频度均为1，该程序段的执行时间是一个与问题规模n无关的常数。算法的时间复杂度为常数阶，记作T(n)=O(1)。
注意：如果算法的执行时间不随着问题规模n的增加而增长，即使算法中有上千条语句，其执行时间也不过是一个较大的常数。此类算法的时间复杂度是O(1)。
变量计数之一：
(1) x=0;y=0;
(2) for(k-1;k&=n;k++)
(3)&&&& x++;
(4) for(i=1;i&=n;i++)
(5)&&&&&& for(j=1;j&=n;j++)
(6)&&&&&&&& y++;
　　一般情况下，对步进循环语句只需考虑循环体中语句的执行次数，忽略该语句中步长加1、终值判别、控制转移等成分。因此，以上程序段中频度最大的语句是(6)，其频度为f(n)=n2，所以该程序段的时间复杂度为T(n)=O(n2)。
　　当有若干个循环语句时，算法的时间复杂度是由嵌套层数最多的循环语句中最内层语句的频度f(n)决定的。
变量计数之二：
(2) for(i=1;i&=n;i++)
(3)&&&&&& for(j=1;j&=i;j++)
(4)&&&&&&&&&& for(k=1;k&=j;k++)
(5)&&&&&&&&&&&&&& x++;
　　该程序段中频度最大的语句是(5)，内循环的执行次数虽然与问题规模n没有直接关系，但是却与外层循环的变量取值有关，而最外层循环的次数直接与n有关，因此可以从内层循环向外层分析语句(5)的执行次数：
则该程序段的时间复杂度为T(n)=O(n3/6+低次项)=O(n3)。
（4）算法的时间复杂度不仅仅依赖于问题的规模，还与输入实例的初始状态有关。
在数值A[0..n-1]中查找给定值K的算法大致如下：
&&&&&&&&& (3)&&&& i--;
&&&&& (4)&
&&&&此算法中的语句(3)的频度不仅与问题规模n有关，还与输入实例中A的各元素取值及K的取值有关:
①若A中没有与K相等的元素，则语句(3)的频度f(n)=n；
②若A的最后一个元素等于K,则语句(3)的频度f(n)是常数0。&
&&相关文章推荐
* 以上用户言论只代表其个人观点，不代表CSDN网站的观点或立场
访问：148626次
积分：3768
积分：3768
排名：第8931名
原创：199篇
转载：244篇
(17)(4)(3)(2)(8)(29)(39)(17)(2)(15)(43)(9)(18)(8)(5)(85)(28)(47)(2)(3)(5)(9)(9)(17)(19)
(window.slotbydup = window.slotbydup || []).push({
id: '4740881',
container: s,
size: '200,200',
display: 'inlay-fix'算法_百度百科
声明：百科词条人人可编辑，词条创建和修改均免费，绝不存在官方及代理商付费代编，请勿上当受骗。
[suàn fǎ]
算法（Algorithm）是指解题方案的准确而完整的描述，是一系列解决问题的清晰，算法代表着用系统的方法描述解决问题的策略机制。也就是说，能够对一定规范的，在有限时间内获得所要求的输出。如果一个算法有缺陷，或不适合于某个问题，执行这个算法将不会解决这个问题。不同的算法可能用不同的时间、空间或效率来完成同样的任务。一个算法的优劣可以用与来衡量。算法中的指令描述的是一个，当其时能从一个初始状态和（可能为空的）初始输入开始，经过一系列有限而清晰定义的状态，最终产生输出并停止于一个终态。一个状态到另一个状态的转移不一定是确定的。在内的一些算法，包含了一些随机。形式化算法的概念部分源自尝试解决提出的，并在其后尝试定义有效计算性或者有效方法中成形。这些尝试包括、Jacques Herbrand和分别于1930年、1934年和1935年提出的，于1936年提出的，1936年Emil Leon Post的Formulation 1和1937年提出的。即使在当前，依然常有直觉想法难以定义为形式化算法的情况。
一个算法应该具有以下五个重要的特征：
算法有穷性
（Finiteness）
算法的有穷性是指算法必须能在执行有限个步骤之后终止；
算法确切性
(Definiteness)
算法的每一步骤必须有确切的定义；
算法输入项
一个算法有0个或多个输入，以刻画运算对象的初始情况，所谓0个输入是指算法本身定出了初始条件；
算法输出项
一个算法有一个或多个输出，以反映对输入数据加工后的结果。没有输出的算法是毫无意义的；
算法可行性
(Effectiveness)
算法中执行的任何计算步骤都是可以被分解为基本的可执行的操作步，即每个计算步都可以在有限时间内完成（也称之为有效性）。
一，数据对象的运算和操作：计算机可以执行的基本操作是以指令的形式描述的。一个计算机系统能执行的所有指令的集合，成为该计算机系统的指令系统。一个计算机的基本运算和操作有如下四类：[1]
1，：加减乘除等运算
2，：或、且、非等运算
3，：大于、小于、等于、不等于等运算
4，：输入、输出、赋值等运算[1]
二，算法的控制结构：一个算法的功能结构不仅取决于所选用的操作，而且还与各操作之间的执行顺序有关。[1]
同一问题可用不同算法解决，而一个算法的质量优劣将影响到算法乃至程序的效率。的目的在于选择合适算法和改进算法。一个算法的评价主要从和来考虑。
算法时间复杂度
算法的时间复杂度是指执行算法所需要的计算工作量。一般来说，计算机算法是问题规模n 的函数f(n)，算法的时间复杂度也因此记做。
T(n)=Ο(f(n))
因此，问题的规模n 越大，算法执行的时间的增长率与f(n) 的增长率正相关，称作（Asymptotic Time Complexity）。
算法空间复杂度
算法的空间复杂度是指算法需要消耗的内存空间。其计算和表示方法与时间类似，一般都用复杂度的渐近性来表示。同时间复杂度相比，空间复杂度的分析要简单得多。
算法正确性
算法的正确性是评价一个算法优劣的最重要的标准。
算法可读性
算法的可读性是指一个算法可供人们阅读的容易程度。[1]
算法健壮性
健壮性是指一个算法对不合理数据输入的反应能力和处理能力，也称为容错性。[1]
算法递推法
递推是中的一种常用算法。它是按照一定的规律来计算序列中的每个项，通常是通过计算机前面的一些项来得出序列中的指定项的值。其思想是把一个复杂的的计算过程转化为的多次，该算法利用了计算机速度快和的机器特点。
算法递归法
程序调用自身的编程技巧称为（recursion）。一个过程或在其定义或说明中有直接或间接调用自身的一种方法，它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解，递归策略只需少量的程序就可描述出解题过程所需要的多次重复计算，大大地减少了程序的代码量。递归的能力在于用有限的来定义对象的。一般来说，递归需要有、递归前进段和递归返回段。当边界条件不满足时，递归前进；当边界条件满足时，递归返回。
(1) 递归就是在过程或里调用自身;
(2) 在使用递归策略时，必须有一个明确的递归结束条件，称为递归出口。
算法穷举法
，或称为法，其基本思路是：对于要解决的问题，列举出它的所有可能的情况，逐个判断有哪些是符合问题所要求的条件，从而得到问题的解。它也常用于对于的，即将密码进行逐个推算直到找出真正的密码为止。例如一个已知是四位并且全部由数字组成的密码，其可能共有10000种组合，因此最多尝试10000次就能找到正确的密码。理论上利用这种方法可以破解任何一种密码，问题只在于如何缩短试误时间。因此有些人运用计算机来增加效率，有些人辅以字典来缩小组合的范围。
算法贪心算法
是一种对某些求最优解问题的更、更迅速的设计技术。
用贪心法设计算法的特点是一步一步地进行，常以当前情况为基础根据某个优化测度作最优选择，而不考虑各种可能的整体情况，它省去了为找要穷尽所有可能而必须耗费的大量时间，它采用自顶向下,以迭代的方法做出相继的贪心选择,每做一次贪心选择就将所求问题简化为一个规模更小的子问题, 通过每一步贪心选择,可得到问题的一个最优解，虽然每一步上都要保证能获得局部最优解，但由此产生的全局解有时不一定是最优的，所以贪婪法不要回溯。
是一种改进了的分级处理方法，其核心是根据题意选取一种量度标准，然后将这多个输入排成这种量度标准所要求的顺序，按这种顺序一次输入一个量，如果这个输入和当前已构成在这种量度意义下的部分最佳解加在一起不能产生一个，则不把此输入加到这部分解中。这种能够得到某种量度意义下最优解的分级处理方法称为贪婪算法。
对于一个给定的问题，往往可能有好几种量度标准。初看起来，这些量度标准似乎都是可取的，但实际上，用其中的大多数量度标准作贪婪处理所得到该量度意义下的最优解并不是问题的最优解，而是次优解。因此，选择能产生问题最优解的最优量度标准是使用贪婪算法的核心。
一般情况下，要选出最优量度标准并不是一件容易的事，但对某问题能选择出最优量度标准后，用贪婪算法求解则特别有效。
算法分治法
是把一个复杂的问题分成两个或更多的相同或相似的子问题，再把子问题分成更小的子问题……直到最后子问题可以简单的直接求解，原问题的解即子问题的解的合并。
分治法所能解决的问题一般具有以下几个特征：
(1) 该问题的规模缩小到一定的程度就可以容易地解决；
(2) 该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质；
(3) 利用该问题分解出的子问题的解可以合并为该问题的解；
(4) 该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子子问题。
算法动态规划法
是一种在数学和中使用的，用于求解包含重叠子问题的最优化问题的方法。其基本思想是，将原问题分解为相似的子问题，在求解的过程中通过子问题的解求出原问题的解。动态规划的思想是多种算法的基础，被广泛应用于计算机科学和工程领域。
动态规划程序设计是对解最优化问题的一种途径、一种方法，而不是一种特殊算法。不象前面所述的那些搜索或数值计算那样，具有一个标准的数学表达式和明确清晰的解题方法。动态规划程序设计往往是针对一种，由于各种问题的性质不同，确定最优解的条件也互不相同，因而动态规划的设计方法对不同的问题，有各具特色的解题方法，而不存在一种万能的动态规划算法，可以解决各类最优化问题。因此读者在学习时，除了要对基本概念和方法正确理解外，必须具体问题具体分析处理，以丰富的想象力去建立模型，用创造性的技巧去求解。
算法迭代法
也称，是一种不断用变量的旧值新值的过程，跟迭代法相对应的是直接法（或者称为一次解法），即一次性解决问题。迭代法又分为精确迭代和近似迭代。“”和“”属于近似迭代法。迭代算法是用计算机解决问题的一种基本方法。它利用计算机运算速度快、适合做重复性操作的特点，让计算机对一组指令（或一定步骤）进行重复执行，在每次执行这组指令（或这些步骤）时，都从变量的原值推出它的一个新值。
算法分支界限法
是一个用途十分广泛的算法，运用这种算法的技巧性很强，不同类型的问题解法也各不相同。
分支定界法的基本思想是对有的的所有（数目有限）空间进行搜索。该算法在具体执行时，把全部可行的不断分割为越来越小的（称为分支），并为每个子集内的解的值计算一个下界或（称为定界）。在每次分支后，对凡是界限超出已知可行解值那些子集不再做进一步分支，这样，解的许多子集（即搜索树上的许多结点）就可以不予考虑了，从而缩小了搜索范围。这一过程一直进行到找出为止，该可行解的值不大于任何子集的界限。因此这种算法一般可以求得。
与一样，这种方法也是用来为问题设计求解算法的，所不同的是它在问题的整个可能解空间搜索，所设计出来的算法虽其比高，但它的优点是与类似，都能保证求出问题的最佳解，而且这种方法不是盲目的穷举搜索，而是在搜索过程中通过，可以中途停止对某些不可能得到最优解的子空间进一步搜索（类似于人工智能中的剪枝），故它比穷举法更高。
算法回溯法
回溯法（探索与回溯法）是一种选优搜索法，按选优条件向前搜索，以达到目标。但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术为回溯法，而满足回溯条件的某个的点称为“回溯点”。
其基本思想是，在包含问题的所有解的解空间树中，按照深度优先搜索的策略，从根结点出发深度探索解空间树。当探索到某一结点时，要先判断该结点是否包含问题的解，如果包含，就从该结点出发继续探索下去，如果该结点不包含问题的解，则逐层向其祖先结点回溯。（其实回溯法就是对隐式图的深度优先搜索算法）。 若用回溯法求问题的所有解时，要回溯到根，且根结点的所有可行的子树都要已被搜索遍才结束。 而若使用回溯法求任一个解时，只要搜索到问题的一个解就可以结束。
算法描述方式
描述算法的方法有多种，常用的有自然语言、结构化、和等，其中最普遍的是流程图。
算法可大致分为基本算法、数据结构的算法、与代数算法、计算几何的算法、的算法、以及、、、检索算法、随机化算法、并行算法，厄米变形模型，随机森林算法。
算法可以宏泛的分为三类：
一，有限的，确定性算法 这类算法在有限的一段时间内终止。他们可能要花很长时间来执行指定的任务，但仍将在一定的时间内终止。这类算法得出的结果常取决于输入值。
二，有限的，非确定算法 这类算法在有限的时间内终止。然而，对于一个（或一些）给定的数值，算法的结果并不是唯一的或确定的。
三，无限的算法 是那些由于没有定义终止定义条件，或定义的条件无法由输入的数据满足而不终止运行的算法。通常，无限算法的产生是由于未能确定的定义终止条件。
“算法”即演算法的大陆中文名称出自《》；而英文名称Algorithm 来自于9世纪波斯数学家al-Khwarizmi，因为al-Khwarizmi在数学上提出了算法这个概念。“算法”原为&algorism&，意思是阿拉伯数字的运算法则，在18世纪演变为&algorithm&。被人们认为是史上第一个算法。 第一次编写程序是Ada Byron于1842年为巴贝奇分析机编写求解的程序，因此Ada Byron被大多数人认为是世界上第一位。因为查尔斯·巴贝奇(Charles Babbage)未能完成他的巴贝奇分析机，这个算法未能在巴贝奇分析机上执行。 因为&well-defined procedure&缺少数学上精确的定义，19世纪和20世纪早期的数学家、学家在定义算法上出现了困难。20世纪的英国数学家提出了著名的图灵论题，并提出一种假想的计算机的抽象模型，这个模型被称为。图灵机的出现解决了算法定义的难题，图灵的思想对算法的发展起到了重要作用。
经典的算法有很多，如，，。
随着计算机的发展，算法在计算机方面已有广泛的发展及应用，如用算法，来进行头部姿势的估计，用遗传算法来解决弹药装载问题，信息在网络传输中的应用，并行算法在中的应用等。
钟志永 姚珺．大学计算机应用基础．重庆：重庆大学出版社，2012：213-214
中国电子学会（Chinese Instit...
提供资源类型：内容}