算法的时间复杂度定义
一个算法花费的时间与算法中语句的执行次数成正比例,时间复杂度一般用O(f(x))表示.
f(x)在简单程序中就是看有几个for循环,然后看看再它的判断语句,就是看看它执行了几次,f(x)=“执行的次数”。
像题中的(1)有一个for循环执行次数为n次,所以f(x)=n,时间复杂度就为O(n)
(2)有两个for循环执行次数为n*n,即n的平方,所以f(x)=n的平方,时间复杂度就是O(n的平方)。
(3)是递归,它也执行了n次所以它的时间复杂度就是O(n).
不过要注意时间复杂度的f(x)在有限次时就用具体数值表示,无限次时就用n,n的平方,log以2为底n的对数,其实很简单就是看n的最高次方,看n的最高次方等于几,f(x)就等于几。
在进行算法分析时,语句总的执行次数T(n)是关于问题规模n的函数,进而分析T(n)随n的变化情况并确定T(n)的数量级。算法的时间复杂度,也就是算法的时间量度。记作:T(n)=O(f(n))。它表示随问题n的增大,算法执行时间的增长率和f(n)的增长率相同,称作算法的渐进时间复杂度,简称为时间复杂度。其中,f(n)是问题规模n的某个函数。
这样用大写O()来体现算法时间复杂度的记法,我们称之为大0记法。
一、概念
时间复杂度是总运算次数表达式中受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)依此类推
eg:
(1) for(i=1;i<=n;i++) //循环了n*n次,当然是O(n^2)
for(j=1;j<=n;j++)
s++;
(2) for(i=1;i<=n;i++)//循环了(n+n-1+n-2+...+1)≈(n^2)/2,因为时间复杂度是不考虑系数的,所以也是O(n^2)
for(j=i;j<=n;j++)
s++;
(3) for(i=1;i<=n;i++)//循环了(1+2+3+...+n)≈(n^2)/2,当然也是O(n^2)
for(j=1;j<=i;j++)
s++;
(4) i=1;k=0;
while(i<=n-1){
k+=10*i; i++; }//循环了n-1≈n次,所以是O(n)(5) for(i=1;i<=n;i++)
for(j=1;j<=i;j++)
for(k=1;k<=j;k++)
x=x+1;
//循环了(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.一个算法执行所耗费的时间,从理论上是不能算出来的,必须上机运行测试才能知道。但我们不可能也没有必要对每个算法都上机测试,只需知道哪个算法花费的时间多,哪个算法花费的时间少就可以了。并且一个算法花费的时间与算法中语句的执行次数成正比例,哪个算法中语句执行次数多,它花费时间就多。
一个算法中的语句执行次数称为语句频度或时间频度。记为T(n)。
2.一般情况下,算法的基本操作重复执行的次数是模块n的某一个函数f(n),因此,算法的时间复杂度记做:T(n)=O(f(n))。随着模块n的增大,算法执行的时间的增长率和f(n)的增长率成正比,所以f(n)越小,算法的时间复杂度越低,算法的效率越高。
在计算时间复杂度的时候,先找出算法的基本操作,然后根据相应的各语句确定它的执行次数,再找出T(n)的同数量级(它的同数量级有以下:1,Log2n ,n ,nLog2n ,n的平方,n的三次方,2的n次方,n!),找出后,f(n)=该数量级,若T(n)/f(n)求极限可得到一常数c,则时间复杂度T(n)=O(f(n))。
3.常见的时间复杂度
按数量级递增排列,常见的时间复杂度有:
常数阶O(1), 对数阶O(log2n), 线性阶O(n), 线性对数阶O(nlog2n), 平方阶O(n^2), 立方阶O(n^3),..., k次方阶O(n^k), 指数阶O(2^n) 。
其中,1.O(n),O(n^2), 立方阶O(n^3),..., k次方阶O(n^k) 为多项式阶时间复杂度,分别称为一阶时间复杂度,二阶时间复杂度。。。。2.O(2^n),指数阶时间复杂度,该种不实用3.对数阶O(log2n), 线性对数阶O(nlog2n),除了常数阶以外,该种效率最高
例:算法:
for(i=1;i<=n;++i)
{
for(j=1;j<=n;++j)
{
c[ i ][ j ]=0; //该步骤属于基本操作 执行次数:n^2
for(k=1;k<=n;++k)
c[ i ][ j ]+=a[ i ][ k ]*b[ k ][ j ]; //该步骤属于基本操作 执行次数:n^3
}
}
则有 T(n)= n^2+n^3,根据上面括号里的同数量级,我们可以确定 n^3为T(n)的同数量级
则有f(n)= n^3,然后根据T(n)/f(n)求极限可得到常数c
则该算法的 时间复杂度:T(n)=O(n^3)
四、
定义:如果一个问题的规模是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的值非常小,因为,在 这个问题中增加一个元素就导致运行时间加倍。不幸的是,确实有许多问题 (如著名的“巡回售货员问题” ),到目前为止找到的算法都是指数的。如果我们真的遇到这种情况,通常应该用寻找近似最佳结果的算法替代之。
在进行算法分析时,语句总的执行次数T(n)是关于问题规模n的函数,进而分析T(n)随n的变化情况并确定T(n)的数量级。算法的时间复杂度,也就是算法的时间量度。记作:T(n)=O(f(n))。它表示随问题n的增大,算法执行时间的增长率和f(n)的增长率相同,称作算法的渐进时间复杂度,简称为时间复杂度。其中,f(n)是问题规模n的某个函数。
这样用大写O()来体现算法时间复杂度的记法,我们称之为大0记法。
时间复杂度怎么算
时间复杂度是算法方法是:T(n)=O(f(n))。算法的时间复杂度,用来度量算法的运行时间,记作:T(n)=O(f(n))。它表示随着输入大小n的增大,算法执行需要的时间的增长速度可以用f(n)来描述。因为f(n)的增长速度是大于或者等于T(n)的,即T(n)=O(f(n))。所以我们可以用f...
算法的时间复杂度与什么有关
4、5、为了计算时间复杂度,通常会估计算法的操作单元数量,每个单元运行的时间都是相同的。因此,总运行时间和算法的操作单元数量最多相差一个常量系数。相同大小的不同输入值仍可能造成算法的运行时间不同,因此我们通常使用算法的最坏情况复杂度,记为T(n),定义为任何大小的输入n所需的最大运行时间...
时间复杂度o(1)是什么意思
时间复杂度o(1)意思是常数阶时间复杂度。一般情况下,算法的基本操作重复执行的次数是模块n的某一个函数f(n),因此,算法的时间复杂度记做:T(n)=O(f(n))按数量级递增排列。常见的时间复杂度有:常数阶O(1),对数阶O(log2n),线性阶O(n),线性对数阶O(nlog2n),平方阶O(n^2),立方阶O...
计算机算法的时间复杂度的表示方法有哪些?
O(n)不是算法,它是一个函数,是一个表征算法时间复杂度的一个函数。计算机科学中,算法的时间复杂度是一个函数,它定性描述了该算法的运行时间。这是一个关于代表算法输入值的字符串的长度的函数。时间复杂度常用大O符号表述,不包括这个函数的低阶项和首项系数。使用这种方式时,时间复杂度可被称为...
算法时间复杂度的度量方法是
但有时我们想知道它变化时呈现什么规律,为此我们引入时间复杂度的概念。算法的时间复杂度也就是算法的时间度量,记作:T(n) = O(f(n))。它表示随问题规模n的增大,算法执行时间的增长率和f(n)的增长率相同,称作算法的渐进时间复杂度,简称「时间复杂度」。这种表示方法我们称为「 大O符号表示法...
时间复杂度和空间复杂度是什么情况
时间复杂度与空间复杂度没有必然联系。但是也有以空间换时间或时间换空间的,此时,它们就会有影响。像散列法,用更多的空间,但时间会小于O(n)。时间复杂度和空间复杂度,其实就是所耗时间与空间关于输入数据规模的函数,一般输入数据规模越大,所耗时间和空间就越多,如果所耗时间与数据规模成正比。
算法的时间复杂度取决于
算法的时间复杂度取决于如下:算法的时间复杂度取决于问题的规模,待处理数据的初态。算法(Algorithm)是指解题方案的准确而完整的描述,是一系列解决问题的清晰指令,算法代表着用系统的方法描述解决问题的策略机制。也就是说,能够对一定规范的输入,在有限时间内获得所要求的输出。如果一个算法有缺陷,...
算法的空间复杂度和时间复杂度的关系
算法时间复杂度分析是一个很重要的问题,任何一个程序员都应该熟练掌握其概念和基本方法,而且要善于从数学层面上探寻其本质,才能准确理解其内涵。2、算法的空间复杂度 类似于时间复杂度的讨论,一个算法的空间复杂度(Space Complexity)S(n)定义为该算法所耗费的存储空间,它也是问题规模n的函数。渐近空间复杂度也常常...
算法时间复杂度的分析通常有两种方法,即___和___,通常我们对算法求时...
时间复杂度通常是衡量算法的优劣的,衡量算法的时间严格来讲是很难衡量的,由于不同的机器性能不用环境都会造成不同的执行时间空间复杂度是对一个算法在运行过程中临时占用存储空间大小的度量,也是使用大O表示法。算法分析解释 是对一个算法需要多少计算时间和存储空间作定量的分析算法是解题的步骤,可以...
时间复杂性的时间复杂度
则时间复杂度为O(1),另外,在时间频度不相同时,时间复杂度有可能相同,如T(n)=n2+3n+4与T(n)=4n2+2n+1它们的频度不同,但时间复杂度相同,都为O(n2)。 1.一般情况下,算法的基本操作重复执行的次数是模块n的某一个函数f(n),因此,算法的时间复杂度记做:...
势贸吴天: 指算法执行过程中所需要的基本运算次数.
青冈县17368542702: 什么是算法复杂度 - ?
势贸吴天: 算法复杂度,即算法在编写成可执行程序后,运行时所需要的资源,资源包括时间资源和内存资源. 同一问题可用不同算法解决,而一个算法的质量优劣将影响到算法乃至程序的效率.算法分析的目的在于选择合适算法和改进算法.一个算法的...
青冈县17368542702: 什么是算法的时间复杂度? - ?
势贸吴天: 时间复杂度表面的意思就是代码花费的时间,但是一般使用这个概念的时候,更注重的是随着数据量增长,代码执行时间的增长情况.一般认为一个基本的运算为一次运行算,例如加减乘除判断等等 例1和例2时间复杂度都可以简单认为是o(N),...
青冈县17368542702: 算法的时间复杂度指的是 - ?
势贸吴天: 同一问题可用不同算法解决,而一个算法的质量优劣将影响到算法乃至程序的效率.算法分析的目的在于选择合适算法和改进算法.一个算法的评价主要从时间复杂度和空间复杂度来考虑.
青冈县17368542702: 数据结构中算法的时间复杂度是什么? - ?
势贸吴天: 程序所用时间关于数据规模的函数 比如: 给n个数排序需要n^2的时间 时间复杂度就是O(n^2) 通常有 O(2) 常数 与输入数据规模无关 O(n) 成正比 O(log2n) 平方与数据规模成正比 O(n^2) 与数据规模的平方成正比 O(n^3) ……三次方…… O(n!) 阶乘
青冈县17368542702: 算法复杂度的时间复杂度 - ?
势贸吴天: (1)时间频度 一个算法执行所耗费的时间,从理论上是不能算出来的,必须上机运行测试才能知道.但我们不可能也没有必要对每个算法都上机测试,只需知道哪个算法花费的时间多,哪个算法花费的时间少就可以了.并且一个算法花费的时间...
青冈县17368542702: 算法的时间复杂度是指?
势贸吴天: 时间复杂度 算法的时间复杂度是指算法需要消耗的时间资源.一般来说,计算机算法是问题规模n 的函数f(n),算法的时间复杂度也因此记做 T(n)=Ο(f(n)) 因此,问题的规模n 越大,算法执行的时间的增长率与f(n) 的增长率正相关,称作渐进时间复杂度(Asymptotic Time Complexity).算法的
青冈县17368542702: JAVA中算法的时间复杂程度是什么 - ?
势贸吴天: JAVA中算法的时间复杂程度 简而言之就是运算时候的执行次数的统计 1.时间频度 一个算法执行所耗费的时间,从理论上是不能算出来的,必须上机运行测试才能知道.但我们不可能也没有必要对每个算法都上机测试,只需知道哪个算法花费...
青冈县17368542702: 有关算法的时间复杂度 - ?
势贸吴天: N的3次方是指这里举的例子:“两个n阶矩阵相乘”而言. 它说,这个问题的“规模”等于矩阵的阶数 n . 两个n阶矩阵相乘的基本运算(两个实数的乘法)次数正好是阶数的三次方. f (n) = n ^ 3 .矩阵乘法程序见: http://zhidao.baidu.com/question/9394030.html别的算法的时间复杂度=算法的工作量=f (n) f (n) 是什么,要看算什么,怎么算,才知道.未必是N的3次方.