各位老铁们好，相信很多人对时间复杂度的计算 *** 都不是特别的了解，因此呢，今天就来为大家分享下关于时间复杂度的计算 *** 以及时间复杂度与空间复杂度的关系的问题知识，还望可以帮助大家，解决大家的一些困惑，下面一起来看看吧！
本文目录
一、[算法技术]算法的时间复杂度
算法的时间复杂度是衡量一个算法效率的基本 *** 。在阅读其他算法教程书的时候，对于算法的时间复杂度的讲解不免有些生涩，难以理解。进而无法在实际应用中很好的对算法进行衡量。
《大话数据结构》一书在一开始也针对算法的时间复杂度进行了说明。这里的讲解就非常明确，言简意赅，很容易理解。下面通过《大话数据结构》阅读笔记的方式，通过原因该书的一些简单的例子和说明来解释一下算法的时间复杂度和它的计算 *** 。
首先从基本定义下手，来了解一下什么是“算法的时间复杂度”，《大话数据结构》一书中对算法的时间复杂度定义如下：
“算法语句总的执行次数 T(n)是关于问题规模 n的函数，进而分析 T(n)随 n的变化情况并确定 T(n)的数量级。算法的时间复 杂度，也就是算法的时间度量，记作：T(n)= O(f(n))它表示随问题规模 n的增大，算法执行时间的增长率和f(n)的增长率 相同，称作算法的渐进时间复杂度，简称为时间复杂度。其中 f(n)是问题规模 n的某个函数。”
光从定义来理解算法的时间复杂度还是比较难的，我们再结合一个简单的例子来说明。计算 1+ 2+ 3+ 4+......+ 100=？这样的问题想必大家都遇到过，这里我们通过 C语言用最简单的 *** 实现一下这个问题的算法。
int sum= 0, n= 100; //执行了 1次
for(int i= 1; i= n; i++){ //执行了 n+ 1次
sum+= i; //执行了 n次
printf(" sum=%d", sum); //执行了 1次
从代码附加的注释可以看到所有代码都执行了多少次。那么这写代码语句执行次数的总和就可以理解为是该算法计算出结果所需要的时间。所以说，上述结算 1+ 2+ 3+ 4+......+ 100=？的算法所用的时间（算法语句执行的总次数）为：
而当 n不断增大，比如我们这次所要计算的不是 1+ 2+ 3+ 4+......+ 100=？而是 1+ 2+ 3+ 4+......+ n=？其中 n是一个十分大的数字，那么由此可见，上述算法的执行总次数（所需时间）会随着 n的增大而增加，但是在 for循环以外的语句并不受 n的规模影响（永远都只执行一次）。所以我们可以将上述算法的执行总次数简单的记做：
这样我们就得到了我们设计的计算 1+ 2+ 3+ 4+......+ 100=？的算法的时间复杂度，我们把它记作：
对于同一个问题，解法通常是不唯一的。比如 1+ 2+ 3+ 4+......+ 100=？这个问题，还有其他的不少算法。我们再来看一个数学家高斯解决这个问题的算法（想必大家都很熟悉这个故事）。
SUM= 100+ 99+ 98+ 97+......+ 1
SUM+ SUM= 2*SUM= 101+ 101+ 101+....+ 101 正好 100个 101
同样我们将这个解法翻译成 C语言代码：
int n= 100, sum= 0; //执行 1次
sum=(n*(n+ 1))/2; //执行 1次
printf("sum=%d", sum); //执行 1次
这样我们针对同一个 1+ 2+ 3+ 4+......+ 100=？问题，不同的算法又的到了一个算法的时间复杂度：
O(3) 一般记作 O(1)我们后续给出原因。
从感官上我们就不难看出，从算法的效率上看，O(3) O(n)的，所以高斯的算法更快，更优秀（是更优秀的吗？）。
这种用个大写的 O来代表算法的时间复杂度的记法有个专业的名字叫“大O阶”记法。那么通过对上述的例子进行总结，我们给出算法的时间复杂度（大O阶）的计算 *** 。
1、用常数 1取代运行时间中的所有加法常数。
2、在修改后的运行次数函数中，只保留更高阶项。
3、如果更高阶项存在且不是 1，则去除与这个项相乘的常数。
下面我们在通过一个有不少 for循环的例子按照上面给出的推导“大O阶”的 *** 来计算一下算法的时间复杂度。先看一下下面的这个例子的代码，也是用 C语言写的，在注释上我们仍然对执行次数进行说明。
int n= 100000; //执行了 1次
for(int i= 0; i n; i++){ //执行了 n+ 1次
for(int j= 0; j n; j++){ //执行了 n*(n+1)次
printf("i=%d, j=%d\n", i, j); //执行了 n*n次
for(int i= 0; i n; i++){ //执行了 n+ 1次
printf("i=%d", i); //执行了 n次
printf("Done"); //执行了 1次
上面的代码严格的说不能称之为一个算法，毕竟它很“无聊而且莫名其妙”（毕竟算法是为了解决问题而设计的嘛），先不论这个“算法”能解决什么问题，我们看一下它的“大O阶”如何推导，还是先计算一下它的执行总次数：
执行总次数= 1+(n+ 1)+ n*(n+ 1)+ n*n+(n+ 1)+ 1= 2n^2+ 3n+ 3 这里 n^2表示 n的 2次方。
按照上面推导“大O阶”的步骤我们先来之一步：“用常数 1取代运行时间中的所有加法常数”，则上面的算式变为：
执行总次数= 2n^2+ 3n+ 1 这里 n^2表示 n的2次方
第二步：“在修改后的运行次数函数中，只保留更高阶项”。这里的更高阶是 n的二次方，所以算式变为：
执行总次数= 2n^2 这里 n^2表示 n的2次方
第三步：“如果更高阶项存在且不是 1，则去除与这个项相乘的常数”。这里 n的二次方不是 1所以要去除这个项的相乘常数，算式变为：
执行总次数= n^2 这里 n^2表示 n的2次方
因此最后我们得到上面那段代码的算法时间复杂度表示为： O( n^2) 这里 n^2表示 n的2次方。
至此，我们对什么是“算法的时间复杂度”和“算法的时间复杂度”表示法“大O阶”的推导 *** 进行了简单的说明。当然要想在日后的实际工作中快速准确的推导出各种算法的“大O阶”我们还需要进行大量的联系，毕竟熟能生巧嘛。最后我们在把常见的算法时间复杂度以及他们在效率上的高低顺序记录在这里，是大家对算法的效率有个直观的认识。
O(1)常数阶 O(logn)对数阶 O(n)线性阶 O(nlogn) O(n^2)平方阶 O(n^3){ O(2^n) O(n!) O(n^n)}
最后三项我用大括号把他们括起来是想要告诉大家。如果日后大家设计的算法推导出的“大O阶”是大括号中的这几位，那么趁早放弃这个算法，在去研究新的算法出来吧。因为大括号中的这几位即便是在 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））。
{c[ i ][ j ]=0;//该步骤属于基本操作执行次数：n的平方次
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)。
三、算法的时间复杂度如何计算
1、求解算法的时间复杂度的具体步骤是：
2、算法中执行次数最多的那条语句就是基本语句，通常是最内层循环的循环体。
3、⑵计算基本语句的执行次数的数量级；
4、只需计算基本语句执行次数的数量级，这就意味着只要保证基本语句执行次数的函数中的更高次幂正确即可，可以忽略所有低次幂和更高次幂的系数。这样能够简化算法分析，并且使注意力集中在最重要的一点上：增长率。
5、⑶用大Ο记号表示算法的时间性能。
6、将基本语句执行次数的数量级放入大Ο记号中。
7、如果算法中包含嵌套的循环，则基本语句通常是最内层的循环体，如果算法中包含并列的循环，则将并列循环的时间复杂度相加。例如：
8、之一个for循环的时间复杂度为Ο(n)，第二个for循环的时间复杂度为Ο(n2)，则整个算法的时间复杂度为Ο(n+n2)=Ο(n2)。
9、常见的算法时间复杂度由小到大依次为：
10、Ο(1)＜Ο(log2n)＜Ο(n)＜Ο(nlog2n)＜Ο(n2)＜Ο(n3)＜…＜Ο(2n)＜Ο(n!)
11、Ο(1)表示基本语句的执行次数是一个常数，一般来说，只要算法中不存在循环语句，其时间复杂度就是Ο(1)。Ο(log2n)、Ο(n)、Ο(nlog2n)、Ο(n2)和Ο(n3)称为多项式时间，而Ο(2n)和Ο(n!)称为指数时间。计算机科学家普遍认为前者是有效算法，把这类问题称为P类问题，而把后者称为NP问题。
12、这只能基本的计算时间复杂度，具体的运行还会与硬件有关。
13、参考博客地址：
四、时间复杂度怎么算例题
这是一个简单的"累乘"问题，用递归算法也能解决。
fact(3)-----fact(2)-----fact(1)------fact(2)-----fact(3)
递归算法在运行中不断调用自身降低规模的过程，当规模降为1，即递归到fact(1)时，满足停止条件停止递归，开始回溯(返回调用算法)并计算，从fact(1)=1计算返回到fact(2);计算2*fact(1)=2返回到fact(3)；计算3*fact(2)=6，结束递归。
每一次递归调用，都用一个特殊的数据结构"栈"记录当前算法的执行状态，特别地设置地址栈，用来记录当前算法的执行位置，以备回溯时正常返回。递归模块的形式参数是普通变量，每次递归调用得到的值都是不同的，他们也是由"栈"来存储。
一般递归调用有以下几种形式(其中a1、a2、b1、b2、k1、k2为常数)。
<1>直接简单递归调用：f(n){...a1*f((n-k1)/b1);...};
<2>直接复杂递归调用：f(n){...a1*f((n-k1)/b1);a2*f((n-k2)/b2);...};
<3>间接递归调用：f(n){...a1*f((n-k1)/b1);...}，
g(n){...a2*f((n-k2)/b2);...}。
递归算法的分析 *** 比较多，最常用的便是迭代法。
迭代法的基本步骤是先将递归算法简化为对应的递归方程，然后通过反复迭代，将递归方程的右端变换成一个级数，最后求级数的和，再估计和的渐进阶。
算法的递归方程为：T(n)=T(n-1)+O(1);
这个例子的时间复杂性是线性的。
T(n)=2T(n/2)+2,且假设n=2的k次方。
=2的(k-1)次方*T(n/2的(i-1)次方)+$(i:1~(k-1))2的i次方
这个例子的时间复杂性也是线性的。
T(n)=2T(n/2)+O(n),且假设n=2的k次方。
一般地，当递归方程为T(n)=aT(n/c)+O(n),T(n)的解为：
O(nlog2n)(a=c&&c>1)//以2为底
O(nlogca)(a>c&&c>1)//n的(logca)次方，以c为底
上面介绍的3种递归调用形式，比较常用的是之一种情况，第二种形式也有时出现，而第三种形式(间接递归调用)使用的较少，且算法分析
比较复杂。下面举个第二种形式的递归调用例子。
<4>递归方程为：T(n)=T(n/3)+T(2n/3)+n
为了更好的理解，先画出递归过程相应的递归树：
...............................
累计递归树各层的非递归项的值，每一层和都等于n，从根到叶的最长路径是：
n-->(2/3)n-->(4/9)n-->(12/27)n-->...-->1
于是T(n)<=(K+1)*n=n(log(2/3)n+1)
由此例子表明，对于第二种递归形式调用，借助于递归树，用迭代法进行算法分析是简单易行的。
五、时间复杂度(计算 *** ,如果计算,及其解释)
时间复杂度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））
c[ i ][ j ]=0;//该步骤属于基本操作执行次数：n的平方次
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的三次方）
好了，文章到这里就结束啦，如果本次分享的时间复杂度的计算 *** 和时间复杂度与空间复杂度的关系问题对您有所帮助，还望关注下本站哦！
