算法的时间复杂度怎么计算啊？什么叫基本 *** 作的原 *** 作啊？

算法的时间复杂度就是 程序中所有语句的频度（该语句重复执行的次数）之和构成
即是由嵌套最深层次的语句频度决定的
例如：
for(int i=0;i<n;i++)
for(int j=0;j<m;j++)
for(int k=0;k<l;k++)
{ }
这里的时间复杂度O(n)=nml;

看循环的次数，比如for（k=1;k<=n;k=2)
{for(j=1;j<=n;j++)}
这种嵌套循环；首先第一个 k=1时候如果小于每次都是乘以2然后与n进行比较，那反过来只要进行log（2）n次，因为求的就是2的多少次方等于或者大于n，第二个的话就是1一直到n然后就是n。然后这个又是嵌套循环所以相乘就好了，这个时间复杂度度就是o（nlog（2）n）。这种主要是理解每一层循环的次数，然后嵌套就相乘，不是嵌套就取最大的那个循环。

1、先找出算法的基本 *** 作，然后根据相应的各语句确定它的执行次数，再找出T（n）的同数量级（它的同数量级有以下：1，Log2n ，n ，nLog2n ，n的平方，n的三次方，2的n次方，n！），找出后，f（n）=该数量级，若T(n)/f(n)求极限可得到一常数c，则时间复杂度T（n）=O（f（n））。

2、举例

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的三次方）

扩展资料

分类

按数量级递增排列，常见的时间复杂度有：常数阶O(1),对数阶O(  ),线性阶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 算法复杂度分为 时间复杂度和空间复杂度。
作用： 时间复杂度是度量算法执行的时间长短；而空间复杂度是度量算法所需存储空间的大小。
2 一般情况下，算法的基本 *** 作重复执行的次数是模块n的某一个函数f（n），因此，算法的时间复杂度记做：T（n）=O（f（n））
分析：随着模块n的增大，算法执行的时间的增长率和f（n）的增长率成正比，所以f（n）越小，算法的时间复杂度越低，算法的效率越高。
3 在计算时间复杂度的时候，先找出算法的基本 *** 作，然后根据相应的各语句确定它的执行次数，在找出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的三次方）
希望能解决您的问题。

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的三次方）

有模块、类和程序三类复杂度。模块复杂度包含了关于模块的复杂度信息；类复杂度是针对那些使用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数据，例如注释行和空行；协助指出难于理解的模块。

---