导航:首页 > 计算方法 > 常见时间复杂度的计算方法

常见时间复杂度的计算方法

发布时间:2022-12-21 06:15:59

‘壹’ 如何计算一个算法的时间复杂度

我们可以通过这样的方法来求解算法的时间复杂度:
⑴ 找出算法中的基本语句。
⑵ 计算基本语句的执行次数的数量级。
⑶ 用大Ο记号表示算法的时间性能。
具体步骤是:
第一、找出算法中的基本语句;
算法中执行次数最多的那条语句就是基本语句,通常是最内层循环的循环体。
第二、计算基本语句的执行次数的数量级;
只需计算基本语句执行次数的数量级,这就意味着只要保证基本语句执行次数的函数中的最高次幂正确即可,可以忽略所有低次幂和最高次幂的系数。这样能够简化算法分析,并且使注意力集中在最重要的一点上:增长率。
第三、用大Ο记号表示算法的时间性能。
将基本语句执行次数的数量级放入大Ο记号中。
如果算法中包含嵌套的循环,则基本语句通常是最内层的循环体,如果算法中包含并列的循环,则将并列循环的时间复杂度相加。例如:
for (i=1; i<=n; i++)
x++;
for (i=1; i<=n; i++)
for (j=1; j<=n; j++)
x++;
第一个for循环的时间复杂度为Ο(n),第二个for循环的时间复杂度为Ο(n2),则整个算法的时间复杂度为Ο(n+n2)=Ο(n2)。
常见的算法时间复杂度由小到大依次为:
Ο(1)<Ο(log2n)<Ο(n)<Ο(nlog2n)<Ο(n2)<Ο(n3)<…<Ο(2n)<Ο(n!)
Ο(1)表示基本语句的执行次数是一个常数,一般来说,只要算法中不存在循环语句,其时间复杂度就是Ο(1)。Ο(log2n)、Ο(n)、Ο(nlog2n)、Ο(n2)和Ο(n3)称为多项式时间,而Ο(2n)和Ο(n!)称为指数时间。计算机科学家普遍认为前者是有效算法,把这类问题称为P类问题,而把后者称为NP问题。
这只能基本的计算时间复杂度,具体的运行还会与硬件有关。

‘贰’ 如何计算一个算法的时间复杂度

你这个问题是自己想出来的吧?
第一,你指的时间复杂度是大o表示法的复杂度,也就是一个上界,但不是上确界,所以就算你以一种方式中断排序过程,时间复杂度还是o(n*logn),假设排序过程还能执行的话。
第二,达到o(n*logn)的排序算法,以快速排序为例,快速排序不知道你看过没有,它不像选择排序或者冒泡排序那样,每一趟可以确定一直最大或者最小值,对于快速排序,每一趟排序后如果你删掉最后一个元素将导致整个算法失效。如果你要用这种删除元素方法的话,只能采用冒泡排序或者选择排序,时间复杂度是o(n^2)
所以,我猜想你是不是想做类似于在n个元素中寻找前k个最大者之类的事情(k=n-l)
如果是这样的话,有复杂度是o(n*logk)的算法,利用快速排序中的partition操作
经过partition后,pivot左边的序列sa都大于pivot右边的序列sb;
如果|sa|==k或者|sa|==k-1,则数组的前k个元素就是最大的前k个元素,算法终止;
如果|sa|
k,则从sa中寻找前k大的元素。
一次partition(arr,begin,end)操作的复杂度为end-begin,也就是o(n),最坏情况下一次partition操作只找到第1大的那个元素,则需要进行k次partition操作,总的复杂度为o(n*k)。平均情况下每次partition都把序列均分两半,需要logk次partition操作,总的复杂度为o(n*logk)。
由于k的上界是n,所以以n表示的总复杂度还是o(n*logn)

‘叁’ 时间复杂度计算公式

时间复杂度计算公式如下

method1(){
System.out.println("祝你看了这篇文章"); //执行1次 System.out.println("诸事顺利"); //执行1次 System.out.println("万事如意"); //执行1次}// 1+1+1 = 3
method2()

for(int i=0;i<5;i++){ //i=0 执行1次;i<5 判断5+1次,等于5时判断后退出;i++ 执行5次 System.out.println("点赞发财!"); //执行5次 }} //1+(5+1)+5+5 = 17
method3(int n)

for(int i=0;i<n;i++){ //i=0 执行1次;i<n 执行n+1次;i++ 执行n次 System.out.println("点赞好运!"); //执行n次,你会有n次好运哦 }} //1+(n+1)+n+n = 3n+2

大O表示法

上面的时间复杂度的表示还是较复杂,我们一般都使用大O表示法来简化表示时间复杂度。

1、复杂度为常数,如23,9999,等等 都表示为O(1)

2、复杂度包含n时,省略系数与常数项,只取n的最高阶项

如:2n+45 为 O(n) ; 4n^3+6n^2+n 为O(n^3)

3、复杂度为对数时:如log5(n)、log2(n) 等等 都表示为 O(logn)

4、省略低阶,只取高阶 (即取最大的)

如:logn+nlogn 表示为O(nlogn)

‘肆’ 时间复杂度及其计算

算法是指解题方案的准确而完整的描述,是一系列解决问题的清晰指令,算法代表着 用系统的方法描述解决问题的策略机制 。对于同一个问题的解决,可能会存在着不同的算法,为了衡量一个算法的优劣,提出了<u>空间复杂度与时间复杂度</u>这两个概念。

一个算法是由 控制结构(顺序、分支和循环3种) 原操作(指固有数据类型的操作) 构成的,则算法时间取决于<u>两者的综合效果</u>。为了便于比较同一个问题的不同算法,通常的做法是:
<p>从算法中选取一种对于所研究的问题(或算法类型)来说是基本操作的原操作,以该基本操作的重复执行的次数作为算法的时间量度。</p>

参考文章: 算法的时间复杂度和空间复杂度-总结
时间复杂度,又称时间频度,即 一个算法执行所耗费的时间

<u>一个算法花费的时间与算法中语句的执行次数成正比例,哪个算法中语句执行次数多,它花费时间就多。</u>一个算法中的语句执行次数称为语句频度或时间频度。记为T(n)

n称为 问题的规模 ,当n不断变化时,时间频度T(n)也会不断变化。一般情况下,算法中基本操作重复执行的次数是问题规模n的某个函数,用T(n)表示,<i> 若有某个辅助函数f(n),使得当n趋近于无穷大时,*T(n)/f(n)的极限值为不等于零的常数,则称f(n)是T(n)的同数量级函数。记作T(n)=O(f(n)),称O(f(n)) 为算法的渐进时间复杂度,简称时间复杂度。简单来说,就是T(n)在n趋于正无穷时最大也就跟f(n)差不多大。</i>

算法中语句执行次数为一个常数,则时间复杂度为O(1)。常见的时间复杂度有:<p><b>常数阶O(1),对数阶O(log2n),线性阶O(n), 线性对数阶O(n log2n),平方阶O(n2),立方阶O(n3),...。</b></p>
<i><b>Log</b><u>2</u><b>8</b>:2为底N的对数,即2的几次方等于8,值为3</i>


常见的算法时间复杂度由小到大依次为:Ο(1)<Ο(log2n)<Ο(n)<Ο(n log2n)<Ο(n2)<Ο(n3)<…<Ο(2n)<Ο(n!)
即:常数阶 < 对数阶 < 线性阶 < 线性对数阶 < 平方阶 < 立方阶 < … < 指数阶 < 阶乘

如:

第一个for循环的时间复杂度为Ο(n),第二个for循环的时间复杂度为Ο(n2),则整个算法的时间复杂度为Ο(n1+n2+n3)=Ο(n3)。

Ο(1)表示基本语句的执行次数是一个常数,一般来说,只要算法中不存在循环语句,其时间复杂度就是Ο(1)。其中Ο(log2n)、Ο(n)、 Ο(nlog2n)、Ο(n2)和Ο(n3)称为多项式时间,而Ο(2n)和Ο(n!)称为指数时间。计算机科学家普遍认为前者(即多项式时间复杂度的算法)是有效算法。

<i>指数函数:y=ax,对数函数:y=logax,幂函数:y=xa
x为变量,a为常量</i>

‘伍’ 如何计算时间复杂度

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(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.时间频度
一个算法执行所耗费的时间,从理论上是不能算出来的,必须上机运行测试才能知道。但我们不可能也没有必要对每个算法都上机测试,只需知道哪个算法花费的时间多,哪个算法花费的时间少就可以了。并且一个算法花费的时间与算法中语句的执行次数成正比例,哪个算法中语句执行次数多,它花费时间就多。一个算法中的语句执行次数称为语句频度或时间频度。记为T(n)。
2.计算方法
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.分类
按数量级递增排列,常见的时间复杂度有: 常数阶O(1),对数阶O(log2n),线性阶O(n), 线性对数阶O(nlog2n),平方阶O(n2),立方阶O(n3),..., k次方阶O(nk), 指数阶O(2n) 。随着问题规模n的不断增大,上述时间复杂度不断增大,算法的执行效率越低。

‘柒’ 递归算法时间复杂度怎么分析

1、递归
是指对一个问题的求解,可以通过同一问题的更简单的形式的求解来表示. 并通过问题的简单形式的解求出复杂形式的解. 递归是解决一类问题的重要方法. 递归程序设计是程序设计中常用的一种方法,它可以解决所有有递归属性的问题,并且是行之有效的. 但对于递归程序运行的效率比较低,无论是时间还是空间都比非递归程序更费,若在程序中消除递归调用,则其运行时间可大为节省. 以下讨论递归的时间效率分析方法,以及与非递归设计的时间效率的比较.
2 时间复杂度的概念及其计算方法
算法是对特定问题求解步骤的一种描述. 对于算法的优劣有其评价准则,主要在于评价算法的时间效率,算法的时间通过该算法编写的程序在计算机中运行的时间来衡量,所花费的时间与算法的规模n有必然的联系,当问题的规模越来越大时,算法所需时间量的上升趋势就是要考虑的时间度量.
算法的时间度量是依据算法中最大语句频度(指算法中某条语句重复执行的次数)来估算的,它是问题规模n的某一个函数f(n). 算法时间度量记作:T(n)=O(f(n))
它表示随问题规模n的增大,算法执行时间的增长率和f(n)的增长率相同,称作算法的时间复杂度,简称时间复杂度[2].
例如下列程序段:
(1)x=x+1;(2)for(i=1;i<=n;i++) x=x+1;(3)for(j=1;j<=n;j++) for(k=1;k<=n;k++) x=x+1. 以上三个程序段中,语句x=x+1的频度分别为1,n,n2,则这三段程序的时间复杂度分别为O(1),O(n),O(n2).
求解过程为:先给出问题规模n的函数的表达式,然后给出其时间复杂度T(n).
但是在现实程序设计过程中,往往遇到的问题都是比较复杂的算法,就不能很容易地写出规模n的表达式,也比较难总结其时间复杂度. 递归函数就是属于这种情况. 下面举例说明递归函数的时间复杂度的分析方法.

‘捌’ 如何计算时间复杂度

如何计算时间复杂度

定义:如果一个问题的规模是n,解这一问题的某一算法所需要的时间为T(n),它是n的某一函数 T(n)称为这一算法的“时间复杂性”。

当输入量n逐渐加大时,时间复杂性的极限情形称为算法的“渐近时间复杂性”。

我们常用大O表示法表示时间复杂性,注意它是某一个算法的时间复杂性。大O表示只是说有上界,由定义如果f(n)=O(n),那显然成立f(n)=O(n^2),它给你一个上界,但并不是上确界,但人们在表示的时候一般都习惯表示前者。

此外,一个问题本身也有它的复杂性,如果某个算法的复杂性到达了这个问题复杂性的下界,那就称这样的算法是最佳算法。

“大 O记法”:在这种描述中使用的基本参数是 n,即问题实例的规模,把复杂性或运行时间表达为n的函数。这里的“O”表示量级 (order),比如说“二分检索是 O(logn)的”,也就是说它需要“通过logn量级的步骤去检索一个规模为n的数组”记法 O ( f(n) )表示当 n增大时,运行时间至多将以正比于 f(n)的速度增长。

这种渐进估计对算法的理论分析和大致比较是非常有价值的,但在实践中细节也可能造成差异。例如,一个低附加代价的O(n2)算法在n较小的情况下可能比一个高附加代价的 O(nlogn)算法运行得更快。当然,随着n足够大以后,具有较慢上升函数的算法必然工作得更快。

O(1)

Temp=i;i=j;j=temp;

以 上三条单个语句的频度均为1,该程序段的执行时间是一个与问题规模n无关的常数。算法的时间复杂度为常数阶,记作T(n)=O(1)。如果算法的执行时 间不随着问题规模n的增加而增长,即使算法中有上千条语句,其执行时间也不过是一个较大的常数。此类算法的时间复杂度是O(1)。

O(n^2)

2.1. 交换i和j的内容
sum=0; (一次)
for(i=1;i<=n;i++) (n次 )
for(j=1;j<=n;j++) (n^2次 )
sum++; (n^2次 )
解:T(n)=2n^2+n+1 =O(n^2)

2.2.
for (i=1;i<n;i++)
{
y=y+1; ①
for (j=0;j<=(2*n);j++)
x++; ②
}
解: 语句1的频度是n-1
语句2的频度是(n-1)*(2n+1)=2n^2-n-1
f(n)=2n^2-n-1+(n-1)=2n^2-2
该程序的时间复杂度T(n)=O(n^2).

O(n)

2.3.
a=0;
b=1; ①
for (i=1;i<=n;i++) ②
{
s=a+b;③
b=a;④
a=s;⑤
}
解: 语句1的频度:2,
语句2的频度: n,
语句3的频度: n-1,
语句4的频度:n-1,
语句5的频度:n-1,
T(n)=2+n+3(n-1)=4n-1=O(n).

O(log2n )

2.4.
i=1; ①
while (i<=n)
i=i*2; ②
解: 语句1的频度是1,
设语句2的频度是f(n), 则:2^f(n)<=n;f(n)<=log2n
取最大值f(n)= log2n,
T(n)=O(log2n )

O(n^3)

2.5.
for(i=0;i<n;i++)
{
for(j=0;j<i;j++)
{
for(k=0;k<j;k++)
x=x+2;
}
}
解: 当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(n^3).

我 们还应该区分算法的最坏情况的行为和期望行为。如快速排序的最 坏情况运行时间是 O(n^2),但期望时间是 O(nlogn)。通过每次都仔细 地选择基准值,我们有可能把平方情况 (即O(n^2)情况)的概率减小到几乎等于 0。在实际中,精心实现的快速排序一般都能以 (O(nlogn)时间运行。
下面是一些常用的记法:

访问数组中的元素是常数时间操作,或说O(1)操作。一个算法 如 果能在每个步骤去掉一半数据元素,如二分检索,通常它就取 O(logn)时间。用strcmp比较两个具有n个字符的串需要O(n)时间 。常规的矩阵乘算法是O(n^3),因为算出每个元素都需要将n对 元素相乘并加到一起,所有元素的个数是n^2。
指数时间算法通常来源于需要 求出所有可能结果。例如,n个元 素的集合共有2n个子集,所以要求出所有子集的算法将是O(2n)的 。指数算法一般说来是太复杂了,除非n的值非常小,因为,在 这个问题中增加一个元素就导致运行时间加倍。不幸的是,确实有许多问题 (如着名 的“巡回售货员问题” ),到目前为止找到的算法都是指数的。如果我们真的遇到这种情况, 通常应该用寻找近似最佳结果的算法替代之。

阅读全文

与常见时间复杂度的计算方法相关的资料

热点内容
窗帘幔子怎么安装方法 浏览:847
简述利润表阅读与分析的方法 浏览:979
猪群最佳引种方法 浏览:57
电脑组装方法步骤图片 浏览:471
花生多效唑的使用方法及注意事项 浏览:444
如何学会吹笛子的方法 浏览:561
环己酮的检测方法 浏览:478
四米八锻炼身体的方法 浏览:784
第八代五粮液酒鉴别真伪的方法2021年 浏览:545
玉石的鉴别方法用手电照 浏览:618
常见的案例研究方法有哪些 浏览:452
100个计算方法视频 浏览:341
膨胀挂钩安装方法 浏览:684
老式全站仪坐标计算方法 浏览:605
支原体的治疗方法 浏览:436
标枪训练方法的应用 浏览:287
快速消耗儿童体力的方法 浏览:667
纸质退单正确书写方法 浏览:94
马云手机创业方法 浏览:567
仔猪的脚疼怎么治疗方法 浏览:974