赞
踩
目录
众所周知,设计算法需要提高效率。那么,如何度量一个算法的执行时间呢?
我们的计算机前辈们,为了对算法的评判更加科学,研究出了一种叫做事前分析估算的方法。实际上,就是通过在程序运行前通过对代码语句执行的次数进行求和,以此来评判一个算法的效率。
所谓的时间复杂度,也就跟这个代码语句的执行次数密切相关。
提示:以下是本篇文章正
在进行算法分析时,语句总的执行次数T(n)时关于问题规模n 的函数,进而分析T(n)随n的变化情况并确定T(n)的数量级。算法的时间复杂度,也就是算法的时间度量,记作T(n)=O(f(n))。它表示随问题规模n 的增大,算法执行时间的增长率和f(n)的增长率相同,称作算法的渐近时间复杂度,简称为时间复杂度。其中f(n)是问题规模n 的某个函数。
注:这样用大写O()来体现算法时间复杂度的记法,我们称之为大O记法。一般情况下,随着n的增大,T(n)的增长最慢的算法为最优算法。
1.用常数1取代运行时间中的所有加法常数。
2.在修改后的运行次数函数中,只保留最高阶项。
3.如果最高阶项存在且其系数不是1,则去除与这个项相乘的系数。
通过以上步骤,最后得出的结果就是大O阶
下面,我们就来介绍四种典型的时间复杂度:O(1)、O(n)、O(logn)、O(n^2).
代码如下(示例):
int Sum = 0,n = 100; /* 执行一次 */
Sum = (1 + n) * n / 2; /* 执行一次 */
printf("%d", Sum); /* 执行一次 */
这段代码的运行次数为3,通过我们的推导方法,第一步就是讲3改为1,然后保留最高阶项仍为1,所以最后的时间复杂度就为O(1)。
假如说,Sum这个求和的代码运行了13次,即:
int sum = 0, n = 100; /* 执行1次 */
sum = (1+n)*n/2; /* 执行第1次 */
sum = (1+n)*n/2; /* 执行第2次 */
sum = (1+n)*n/2; /* 执行第3次 */
sum = (1+n)*n/2; /* 执行第4次 */
sum = (1+n)*n/2; /* 执行第5次 */
sum = (1+n)*n/2; /* 执行第6次 */
sum = (1+n)*n/2; /* 执行第7次 */
sum = (1+n)*n/2; /* 执行第8次 */
sum = (1+n)*n/2; /* 执行第9次 */
sum = (1+n)*n/2; /* 执行第10次 */sum = (1+n)*n/2; /* 执行第11次 */
sum = (1+n)*n/2; /* 执行第12次 */
sum = (1+n)*n/2; /* 执行第13次 */
printf("%d",sum); /* 执行1次 */
有很多初学者会误认为时间复杂度是O(15),实际上,对于分支结构而言,无论是真还是假,执行的次数都是固定的一次,不会随着问题规模n的变大而变大或变小。所以,不包含循环结构的分支结构,其时间复杂度也是O(1)。
代码如下(示例):
int a;
for(a = 0; a< n; a++)
{
/* 时间复杂度为O(1)的程序步骤,在循环体中需要执行n次*/
}
由于在循环体中,需要执行n次,所以其时间复杂度为O(n)。
int i= 1;
while (i < n)
{
i= i * 2;
/* 时间复杂度为O(1)的程序步骤 */
}
如果要理解对数阶,咱们还是需要用一点点数学知识。在循环体中,每次都将 i 扩大两倍,使之离 n 更加接近,用公式来表示就是2^x=n,结果就是 x=log2n。所以,这个循环的时间复杂度就是O(logn)。
上面分析过,一个循环体中有一个时间复杂度为O(1)的时间复杂度的程序步骤,那么这个循环的时间复杂度就为O(n)。以此类推,将两个时间复杂度为O(n)的循环进行嵌套操作,就能得到一个时间复杂度为O(n^2)的算法程序。
int i,j;
for(i = 0; i < n; i++)
{
for(j = 0; j < n; j++)
{
/* 时间复杂度为O(1)的程序步骤*/
}
}
这里提醒一下,如果外循环或者内循环的循环次数改为了m,时间复杂度就变为O(m×n)。
int i,j;
for(i = 0; i < m; i++)
{
for(j = 0; j < n; j++)
{
/* 时间复杂度为O(1)的程序步骤 */
}
}
这里我给出一段代码,请判断它的时间复杂度是多少?
int i,j;
for(i = 0; i < n; i++)
{
for(j = i; j < n; j++) /* 注意j = i而不是0 */
{
/* 时间复杂度为O(1)的程序步骤 */
}
}
通过计算我们可以发现,当i=1时,j 执行了n次,i=2时,j 执行了n-1次……所以最后的总次数为n^2/2+n/2。
运用我们的推导方法,不难得出时间复杂度就是O(n^2)。
执行次数函数 | 阶 | 非正式术语 |
---|---|---|
15 | O(1) | 常数阶 |
5n+6 | O(n) | 线性阶 |
6n^2+6n+9 | O(n^2) | 平方阶 |
4log2n+3 | O(logn) | 对数阶 |
6n+7nlog2n+3 | O(nlogn) | nlogn阶 |
6n^3+6 | O(n^3) | 立方阶 |
3^n | O(3^n) | 指数阶 |
常见的时间复杂度耗费时间从小到大依次是:
O(1)<O(logn)<O(n)<O(nlogn)<O(n^2)<O(n^3)<O(2^n)<O(n!)<O(n^n)
总结
从上面的例子我们不难看出,理解大O推导并不算难,难的是对数列的一些相关运算,这更多的是考察你的数学能力。
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。