算法复杂度的介绍,见百科:
http://baike.baidu.com/view/7527.htm
时间复杂度
时间频度
一个算法执行所耗费的时间,从理论上是不能算出来的,必须上机运行测试才能知道。但我们不可能也没有必要对每个算法都上机测试,只需知道哪个算法花费的时间多,哪个算法花费的时间少就可以了。并且一个算法花费的时间与算法中语句的执行次数成正比例,哪个算法中语句执行次数多,它花费时间就多。一个算法中的语句执行次数称为语句频度或时间频度。记为T(n)。
计算方法
1. 一般情况下,算法的基本操作重复执行的次数是模块n的某一个函数f(n),因此,算法的时间复杂度记做:T(n)=O(f(n))
分析:随着模块n的增大,算法执行的时间的增长率和f(n)的增长率成正比,所以f(n)越小,算法的时间复杂度越低,算法的效率越高。
2. 在计算时间复杂度的时候,先找出算法的基本操作,然后根据相应的各语句确定它的执行次数,再找出T(n)的同数量级(它的同数量级有以下:1,Log2n ,n ,nLog2n ,n的平方,n的三次方,2的n次方,n!),找出后,f(n)=该数量级,若T(n)/f(n)求极限可得到一常数c,则时间复杂度T(n)=O(f(n))
例:算法:
for(i=1;i<=n;++i)
{
for(j=1;j<=n;++j)
{
c[ i ][ j ]=0; //该步骤属于基本操作 ,执行次数:n的平方 次
for(k=1;k<=n;++k)
c[ i ][ j ]+=a[ i ][ k ]*b[ k ][ j ]; //该步骤属于基本操作 ,执行次数:n的三次方 次
}
}
则有 T(n)= n的平方+n的三次方,根据上面括号里的同数量级,我们可以确定 n的三次方 为T(n)的同数量级
则有f(n)= n的三次方,然后根据T(n)/f(n)求极限可得到常数c
则该算法的 时间复杂度:T(n)=O(n^3) 注:n^3即是n的3次方。
3.在pascal中比较容易理解,容易计算的方法是:看看有几重for循环,只有一重则时间复杂度为O(n),二重则为O(n^2),依此类推,如果有二分则为O(logn),二分例如快速幂、二分查找,如果一个for循环套一个二分,那么时间复杂度则为O(nlogn)。
分类
按数量级递增排列,常见的时间复杂度有:
常数阶O(1),对数阶O(log2n),线性阶O(n),
线性对数阶O(nlog2n),平方阶O(n^2),立方阶O(n^3),...,
k次方阶O(n^k), 指数阶O(2^n) 。随着问题规模n的不断增大,上述时间复杂度不断增大,算法的执行效率越低。
关于对其的理解
《数据结构(C语言版)》------严蔚敏 吴伟民编著 第15页有句话"整个算法的执行时间与基本操作重复执行的次数成正比。"
基本操作重复执行的次数是问题规模n的某个函数f(n),于是算法的时间量度可以记为:T(n) = O( f(n) )
如果按照这么推断,T(n)应该表示的是算法的时间量度,也就是算法执行的时间。
而该页对“语句频度”也有定义:指的是该语句重复执行的次数。
如果是基本操作所在语句重复执行的次数,那么就该是f(n)。
上边的n都表示的问题规模。
以下来自百度知道:
对于这些算法
(1) for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
s++;
(2) for(i=1;i<=n;i++)
for(j=i;j<=n;j++)
s++;
(3) for(i=1;i<=n;i++)
for(j=1;j<=i;j++)
s++;
(4) i=1;k=0;
while(i<=n-1){
k+=10*i;
i++;
}
(5) for(i=1;i<=n;i++)
for(j=1;j<=i;j++)
for(k=1;k<=j;k++)
x=x+1;
对应的时间复杂度为:
1.时间复杂度O(n^2)
2.时间复杂度O(n^2)
3.时间复杂度O(n^2)
4.时间复杂度O(n)
5.时间复杂度O(n^3)
一般来说,时间复杂度是总运算次数表达式中受n的变化影响最大的那一项(不含系数)
比如:一般总运算次数表达式类似于这样:
a*2^n+b*n^3+c*n^2+d*n*lg(n)+e*n+f
a<>0时,时间复杂度就是O(2^n);
a=0,b<>0 =>O(n^3);
a,b=0,c<>0 =>O(n^2)依此类推
那么,总运算次数又是如何计算出的呢?
一般来说,我们经常使用for循环,就像刚才五个题,我们就以它们为例
1.循环了n*n次,当然是O(n^2)
2.循环了(n+n-1+n-2+...+1)≈(n^2)/2,因为时间复杂度是不考虑系数的,所以也是O(n^2)
3.循环了(1+2+3+...+n)≈(n^2)/2,当然也是O(n^2)
4.循环了n-1≈n次,所以是O(n)
5.循环了(1^2+2^2+3^2+...+n^2)=n(n+1)(2n+1)/6(这个公式要记住哦)≈(n^3)/3,不考虑系数,自然是O(n^3)
另外,在时间复杂度中,log(2,n)(以2为底)与lg(n)(以10为底)是等价的,因为对数换底公式:
log(a,b)=log(c,b)/log(c,a)
所以,log(2,n)=log(2,10)*lg(n),忽略掉系数,二者当然是等价的
还不是太理解
在一个具体的程序中,程序的复杂度是如何计算的?
算法的复杂性
算法的复杂性是算法效率的度量,是评价算法优劣的重要依据。一个算法的复杂性的高低体现在运行该算法所需要的计算机资源的多少上面,所需的资源越多,我们就说该算法的复杂性越高;反之,所需的资源越低,则该算法的复杂性越低。
计算机的资源,最重要的是时间和空间(即存储器)资源。因而,算法的复杂性有时间复杂性和空间复杂性之分。
不言而喻,对于任意给定的问题,设计出复杂性尽可能低的算法是我们在设计算法时追求的一个重要目标;另一方面,当给定的问题已有多种算法时,选择其中复杂性最低者,是我们在选用算法适应遵循的一个重要准则。因此,算法的复杂性分析对算法的设计或选用有着重要的指导意义和实用价值。
简言之,在算法学习过程中,我们必须首先学会对算法的分析,以确定或判断算法的优劣。
1.时间复杂性:
例1:设一程序段如下(为讨论方便,每行前加一行号)
(1) for i:=1 to n do
(2) for j:=1 to n do
(3) x:=x+1
......
试问在程序运行中各步执行的次数各为多少?
解答:
行号 次数(频度)
(1) n+1
(2) n*(n+1)
(3) n*n
可见,这段程序总的执行次数是:f(n)=2n2+2n+1。在这里,n可以表示问题的规模,当n趋向无穷大时,如果 f(n)的值很小,则算法优。作为初学者,我们可以用f(n)的数量级O来粗略地判断算法的时间复杂性,如上例中的时间复杂性可粗略地表示为T(n)=O(n2)。
2.空间复杂性:
例2:将一一维数组的数据(n个)逆序存放到原数组中,下面是实现该问题的两种算法:
算法1:for i:=1 to n do
b[i]:=a[n-i+1];
for i:=1 to n do
a[i]:=b[i];
算法2:for i:=1 to n div 2 do
begin
t:=a[i];a[i]:=a[n-i-1];a[n-i-1]:=t
end;
算法1的时间复杂度为2n,空间复杂度为2n
算法2的时间复杂度为3*n/2,空间复杂度为n+1
显然算法2比算法1优,这两种算法的空间复杂度可粗略地表示为S(n)=O(n)
信息学比赛中,经常是:只要不超过内存,尽可能用空间换时间。
用什么软件来计算算法的复杂度??
你可以自己写软件算,否则就手算,其实很简单,每条语句用1时间,for (int i=0;i<n;i++)这样的for复杂度就是n,两个这样的就是o(n^2),一般就把程序某部分最大的算法复杂度看作总共的复杂度,就比如一个for(int i=0;i<n;i++)和一个双重循环和一个每层搜2个节点,n层的DFS同在一个程序里,且是并列,那么这可复杂度一般情况可以看作O(2^n),如果时间要求非常严格,那么在算的时候也可以算上n^2,但一般可以忽略,因为数据大时n^2比起2^n是很小的,n比起n^2又是很小的。看到代码复杂度就出来了,有兴趣可以做一个字符串处理,用程序出你代码的复杂度,不过没什么必要了。
软件复杂度的复杂度的种类
有模块、类和程序三类复杂度。模块复杂度包含了关于模块的复杂度信息;类复杂度是针对那些使用McCabe面向对象特性的程序,它包含了关于类的复杂度信息;程序复杂度包含了关于程序的复杂度信息。
集成复杂度报告
对应于三种复杂度的是三种复杂度报告。如果一个报告的复杂度信息不只一种,那么就把这些复杂度信息组合成新的报告。
集成复杂度信息只收集一个部件及其下级的信息。例如:如果一个程序级报告包含一个类复杂度,那么只报告组成程序的类的信息,而不包含类组成的信息。 McCabe复杂度是对软件结构进行严格的算术分析得来的,实质上是对程序拓扑结构复杂性的度量,明确指出了任务复杂部分。McCabe复杂度包括:圈复杂度、基本复杂度、模块设计复杂度、设计复杂度、集成复杂度、行数、规范化复杂度、全局数据复杂度、局部数据复杂度、病态数据复杂度。
McCabe复杂度的用途
在软件工程中,有三种使用McCabe复杂性度量的方式。
作为测试的辅助工具。McCabe复杂性度量的结果等于通过一个子程序的路径数,因而需要设计同样多的测试案例以覆盖所有的路径。如果测试案例数小于复杂性数,则有三种情况一是需要更多的测试;二是某些判断点可以去掉;三是某些判断点可用插入式代码替换。
作为程序设计和管理指南。在软件开发中,需要一种简单的方式指出可能出问题的子程序。保持子程序简单的通用方法是设置一个长度限制,例如50行或2页,但这实际上是在缺乏测试简明性的有效方法时无可奈何的替代方法。不少人认为McCabe度量就是这样一种简明性度量。但是要注意,McCabe度量数大的程序,不见得结构化就不好。例如,Case语句是良结构的,但可能有很大的McCabe度量数(依赖于语句中的分支数),这可能是由于问题和解决方案所固有的复杂性所决定的。使用者应当自己决定如何使用McCabe度量所提供的信息。
作为网络复杂性度量的一种方法。Hall和Preiser提出了一种组合网络复杂性度量,用于度量可能由多个程序员组按模块化原理建立的大型软件系统的复杂性。他们提出的组合度量公式为
式中 C1,...,Ck是各个模块的复杂性;CN是网络复杂性;W1和W2为权值。
McCabe复杂度即可用于度量各个模块的复杂性,也可用于度量网络复杂性。 圈复杂度是用来衡量一个模块判定结构的复杂程度,数量上表现为独立路径的条数,即合理的预防错误所需测试的最少路径条数,圈复杂度大说明程序代码可能质量低且难于测试和维护,经验表明,程序的可能错误和高的圈复杂度有着很大关系。
独立路径组成的集合称为基本路径集合,独立路径数就是指基本路径集合中路径的数量。基本路径集合不是唯一的,独立路径数也就不唯一。因此,圈复杂度是最大独立路径数。
计算方法
节点是程序中代码的最小单元,边代表节点间的程序流。如果一个模块流程图有e条边n个节点,它的圈复杂度V(G)=e-n+2,典型的V(G)max=10。图1中示例的圈复杂度是2。
优点
避免软件中的错误倾向;指出极复杂模块,这样的模块也许可以进一步细化;度量测试计划,确定测试重点;在开发过程中通过限制程序逻辑,指导测试过程;指出将要测试的区域;帮助测试人员确定测试和维护对象;与所用的高级程序设计语言类型无关。
应用
圈复杂度指出为了确保软件质量应该检测的最少基本路径的数目。在实际中,测试每一条路经是不现实的,测试难度随着路径的增加而增加。但测试基本路径对衡量代码复杂度的合理性是很必要的。McCabe & Associates建议圈复杂度到10,因为高的圈复杂度使测试变得更加复杂而且增大了软件错误产生的概率。
提示:
圈复杂度度量是测量在一个软件模块中的分支数目,在所有的开发周期中都要使用。
圈复杂度度量以软件的结构流程图为基础。控制流程图描述了软件模块的逻辑结构。一个模块在典型的语言中是一个函数或子程序,有一个入口和一个出口,也可以通过调用/返回机制设计模块。软件模块的每个执行路径,都有与从模块的控制流程图中的入口到出口的节点相符合的路径。
“Cyclomatic”来源于非直接连接基本测试周期的数目,更重要的是,也通过直接相连的图表给出独立路径的数目。通过图表的相关性,一个节点可到达另一个节点。
圈复杂度度量也可作为模块基本流程图路径的数目,其重点在于模块线形组合后,所产生的路径数目是最小的。
对圈复杂度的限制
现在有许多好方法可以用来限制圈复杂度。过于复杂的模块容易出错,难于理解、测试、更正,所以应当在软件开发的各个阶段有意识地限制复杂度,许多开发者已经成功地实现把对软件复杂度的限制作为软件项目的一部分,尽管在确切的数目上略微有些争议。最初支持的数目是10,现在支持数目可达15。但是,只应当在条件较好的情况下使数目大于10,例如开发者非常有经验,设计合乎正式标准,使用现代化的程序语言、结构程序、代码预排和先进的测试计划。换句话说,开发团队可以选择超过10的限制数目,但是必须根据经验进行一些取舍,把精力花在比较复杂的模块上。 基本复杂度是用来衡量程序非结构化程度的,非结构成分降低了程序的质量,增加了代码的维护难度,使程序难于理解。因此,基本复杂度高意味着非结构化程度高,难以模块化和维护。实际上,消除了一个错误有时会引起其他的错误。
计算方法
将圈复杂度图中的结构化部分简化成一个点,计算简化以后流程图的圈复杂度就是基本复杂度。
优点
衡量非结构化程度;反映代码的质量;预测代码维护量,辅助模块划分;与所用的高级程序设计语言类型无关。
应用
当基本复杂度为1,这个模块是充分结构化的;当基本复杂度大于1而小于圈复杂度,这个模块是部分结构化的;当基本复杂度等于圈复杂度,这个模块是完全非结构化的。
Module Design Complexity (iv(G))模块设计复杂度
模块设计复杂度是用来衡量模块判定结构,即模块和其他模块的调用关系。软件模块设计复杂度高意味模块耦合度高,这将导致模块难于隔离、维护和复用。
计算方法
模块设计复杂度是从模块流程图中移去那些不包含调用子模块的判定和循环结构后得出的圈复杂度,因此模块设计复杂度不能大于圈复杂度,通常是远小于圈复杂度。
优点
衡量模块对其下层模块的支配作用;衡量一个模块到其子模块进行集成测试的最小数量;定位可能多余的代码;以复杂的计算逻辑和设计来区分模块;是设计复杂度(S0)和集成复杂度(S1)计算的基础;与所用的高级程序设计语言类型无关。 设计复杂度以数量来衡量程序模块之间的相互作用关系,它提供了系统级模块设计复杂度的概况,有助于衡量进行自底向上集成测试的效果,而且提供了全面衡量程序设计规格和复杂度的数据,不反映独立模块的内部情况。高设计复杂度的系统意味着系统各部分之间有着复杂的相互关系,这样系统将难以维护。
S0是程序中所有模块设计复杂度之和,计算公式如下:
优点
可应用于完整的软件,也可应用于任何子系统;衡量代码的质量;指出一个模块整体的复杂度,反映了每个模块和其内部模块的控制关系;揭示了程序中模块调用的复杂度;有助于集成复杂度的计算。 集成复杂度是为了防止错误所必须进行的集成测试的数量表示,另一种说法是程序中独立线性子树的数目,一棵子树是一个有返回的调用序列。就像圈复杂度是测试路径的数目,而集成复杂度是程序或其子系统的独立线性子树。
计算方法
一个程序的集成复杂度和一个模块的圈复杂度是非常相似的,必须计算对程序进行完全测试所需集成测试的数目。S1的计算公式:
S1=S0-N+1
N是程序中模块的数目。
优点
有助于集成测试的实施;量化集成测试工作且反映了系统设计复杂度;有助于从整体上隔离系统复杂度。
Number of Lines (nl)行数
行数是模块中总的行数,包括代码和注释。
优点:
计算简单;与所用的高级程序设计语言类型无关;指出了模块的行数(即模块的规模),规模小的模块易于理解和维护。 规范化复杂度是圈复杂度除以行数。
计算方法
nv=v(G)/nl
优点
与所用的高级程序设计语言类型无关;定义那些有着显著判定逻辑密度的模块,这些模块相对于其他常见规范模块需要做更多的维护工作。 全局数据复杂度(需有McCabe Data)量化了模块结构和全局数据变量的关系,它说明了模块对外部数据的依赖程度,同时度量了全局数据的测试工作,也描述了模块之间的耦合关系,能反映潜在的维护问题。
对于如何跟踪全局数据使用情况的更多信息,可以参考《McCabe Data in Using McCabe IQ Add-Ons》。 局部数据复杂度(需有McCabe Data)量化了模块结构和用户局部数据变量的关系,同时度量了局部数据的测试工作。
我们能够使用McCabe Data的数据字典选择单独的数据元素,指出每个数据元素具体的数据类型。局部数据复杂度还提供了其他的数据选择准则,量化了每个模块中相应数据对模块控制结构的影响。
关于数据字典的更多信息,参考文档《McCabe Data in Using McCabe IQ Add-Ons.》。 病态数据复杂度衡量一个模块包含的完全非结构化成份的程度,标出向循环内部跳入的问题代码,而这些部分具有最大的风险度,通常需要重新设计。
计算方法
所有的非结构部分除去向循环内跳入的结构,转化为线结构,病态复杂度就等于简化以后流程图的圈复杂度。
优点
与所用的高级程序设计语言类型无关;指出了可靠性的问题,降低了维护风险;帮助识别极不可靠的软件。
(Halstead 复杂度)
McCabe QA能够为所选择的语言产生Halstead Metrics复杂度。Halstead复杂度是以程序中出现的运算符和运算元为计数对象,以它们出现的次数作为计数目标(直接测量指标),然后据以计算出程序容量、工作量。
优点
不要求对程序结构进行深层次分析;能够预测错误率;预测维护工作量;有利于项目规划,衡量所有程序的复杂度;计算方法简单;与所用的高级程序设计语言类型无关;众多研究结构研究表明Halstead复杂度对于预测程序工作计划和程序的Bug非常有用。
Line Count复杂度描述了Line Count复杂度并列出了它们的优点
Line Count Metrics(Line Count复杂度)
优点
软件物理规模的度量;定义了具体的Line Count数据,例如注释行和空行;协助指出难于理解的模块。
数据结构中运算时间复杂度是怎么计算的!
1)时间频度
一个算法执行所耗费的时间,从理论上是不能算出来的,必须上机运行测试才能知道。但我们不可能也没有必要对每个算法都上机测试,只需知道哪个算法花费的时间多,哪个算法花费的时间少就可以了。并且一个算法花费的时间与算法中语句的执行次数成正比例,哪个算法中语句执行次数多,它花费时间就多。一个算法中的语句执行次数称为语句频度或时间频度。记为T(n)。
(2)时间复杂度
在刚才提到的时间频度中,n称为问题的规模,当n不断变化时,时间频度T(n)也会不断变化。但有时我们想知道它变化时呈现什么规律。为此,我们引入时间复杂度概念。
一般情况下,算法中基本操作重复执行的次数是问题规模n的某个函数,用T(n)表示,若有某个辅助函数f(n),使得当n趋近于无穷大时,T(n)/f(n)的极限值为不等于零的常数,则称f(n)是T(n)的同数量级函数。记作T(n)=O(f(n)),称O(f(n)) 为算法的渐进时间复杂度,简称时间复杂度。
在各种不同算法中,若算法中语句执行次数为一个常数,则时间复杂度为O(1),另外,在时间频度不相同时,时间复杂度有可能相同,如T(n)=n^2+3n+4与T(n)=4n^2+2n+1它们的频度不同,但时间复杂度相同,都为O(n^2)。
按数量级递增排列,常见的时间复杂度有:
常数阶O(1),对数阶O(log(2)n),线性阶O(n),
线性对数阶O(nlog(2)n),平方阶O(n^2),立方阶O(n^3),...,
k次方阶O(n^k),指数阶O(2^n)。随着问题规模n的不断增大,上述时间复杂度不断增大,算法的执行效率越低。
(3)算法的时间复杂度
若要比较不同的算法的时间效率,受限要确定一个度量标准,最直接的办法就是将计算法转化为程序,在计算机上运行,通过计算机内部的计时
功能获得精确的时间,然后进行比较。但该方法受计算机的硬件、软件等因素的影响,会掩盖算法本身的优劣,所以一般采用事先分析估算的算法,
即撇开计算机软硬件等因素,只考虑问题的规模(一般用用自然数n表示),认为一个特定的算法的时间复杂度,只采取于问题的规模,或者说它是
问题的规模的函数。
为了方便比较,通常的做法是,从算法选取一种对于所研究的问题(或算法模型)来说是基本运算的操作,以其重复执行的次数作为评价算法时间
复杂度的标准。该基本操作多数情况下是由算法最深层环内的语句表示的,基本操作的执行次数实际上就是相应语句的执行次数。
一般 T(n)=O(f(n))
O(1)<O(log2n)<O(n)<O(n log2 n)<O(n^2)<O(n^3)<O(2^n)所以要选择时间复杂度量级低的算法。
时间复杂度如何计算
在查找的场合是计算平均的情况
在排序的场合是计算最差的情况
结果只是n的量级
如何计算时间复杂度
1. 一般情况下,算法的基本操作重复执行的次数是模块n的某一个函数f(n),因此,算法的时间复杂度记做:T(n)=O(f(n))
分析:随着模块n的增大,算法执行的时间的增长率和f(n)的增长率成正比,所以f(n)越小,算法的时间复杂度越低,算法的效率越高。
2. 在计算时间复杂度的时候,先找出算法的基本操作,然后根据相应的各语句确定它的执行次数,再找出T(n)的同数量级(它的同数量级有以下:1,Log2n ,n ,nLog2n ,n的平方,n的三次方,2的n次方,n!),找出后,f(n)=该数量级,若T(n)/f(n)求极限可得到一常数c,则时间复杂度T(n)=O(f(n))
例:算法:
for(i=1;i<=n;++i)
{
for(j=1;j<=n;++j)
{
c[ i ][ j ]=0; //该步骤属于基本操作 执行次数:n的平方 次
for(k=1;k<=n;++k)
c[ i ][ j ]+=a[ i ][ k ]*b[ k ][ j ]; //该步骤属于基本操作 执行次数:n的三次方 次
}
}
则有 T(n)= n的平方+n的三次方,根据上面括号里的同数量级,我们可以确定 n的三次方 为T(n)的同数量级
则有f(n)= n的三次方,然后根据T(n)/f(n)求极限可得到常数c
则该算法的 时间复杂度:T(n)=O(n的三次方)
转载请注明出处51数据库 » 软件复杂度计算方法 程序中的时间复杂度是怎么计算的