从一些简单的例子看算法时间复杂度 原

从一些简单的例子看算法时间复杂度

    在编程中,一段代码的执行效率实际上很难估算和预测,其主要受到如下几个方面的影响:

1.算法依据的数学基础。

2.编译器产生的代码质量和语言的执行效率。

3.问题的输入规模。

4.硬件的执行速度。

通常情况下,问题的输入规模和算法的数学基础是编码人员需要考虑的条件。时间复杂度是一个用来描述算法执行效率的重要标准。  

    在理解时间复杂度之前,你应该先了解什么叫做算法的时间频度,所谓时间频度即是一个算法解决问题所消耗的时间。但是一般情况下,一个算法解决问题消耗的时间通常与输入值有关,例如我们输入一个整数,找到比它小的所有正偶数,代码如下:

let n = 10;

for (var i = 0; i < n; i++) {
	if (i%2==0) {
		console.log(i);
	}
}

上面代码,当输入n为10时,循环会执行10次,如果时间频度t,则当输入n为20时,时间频度为2t。时间复杂度是用来描述随着问题规模n的变化时间频度t的变化规律。下面是一段更加数学风格的描述:

 一般情况下,算法中基本操作重复执行的次数是问题规模n的某个函数,用T(n)表示,若有某个辅助函数f(n),使得当n趋近于无穷大时,T(n)/f(n)的极限值为不等于零的常数,则称f(n)是T(n)的同数量级函数。记作T(n)=O(f(n)),O(f(n)) 为算法的渐进时间复杂度,简称时间复杂度。

    计算一个算法的时间复杂度时,我们可以将算法分解为逐条语句,计算每条语句的时间复杂度后再进行累加,如下代码的作用是对输入进行求累加:

let n = 10;  
let res = 0; //1
for (var i = n; i > 0; i--) { //1+(n+1)+(n+1)
	res = i+res;  //n
}
console.log(res);//1  

当n输入为10时,时间频度为1+1+n+1+n+1+n+1 = 3n+5。设算法的时间复杂度函数为f(n),(3n+5)/f(n)当n趋于无穷大时,上式可以简化为3n/f(n),取f(n)=n,上次结果为非零常数,因此此算法的时间复杂度为f(n)=n,记做O(n)。

    当算法的执行时间频度和n无关时,算法的时间复杂度为O(1),这是时间复杂度最小的函数,但是需要注意,时间复杂度小并不能说明算法执行耗费的时间短,比如一万行代码每行只执行一次的算法时间复杂度也为O(1)。

     常见的算法时间复杂度由小到大以此为:

Ο(1)<Ο(log²n)<Ο(n)<Ο(nlog²n)<Ο(n2)<Ο(n3)<…<Ο(2n)<Ο(n!)

其中O(log² n)是除了O(1)外时间复杂度最小的函数,例如如下代码:

let n = 10;  
var i = 1;

while(i<n){//2^t<n t<log2(n)  t为时间频度
	i = i * 2;
	tip++;
}

上面的时间频度为 1+1+log2(n)+log2(n)+log2(n),去掉常数项后为3log2(n),时间复杂度为O(log2(n))。如果将上面的代码在加一层循环,则时间复杂度会变为O(nlog3(n)):

let n = 10;  


for (var i = 0; i < n; i++) {// 1+n+1+n+1
	var j = 1;   //n
	while(j<n){//[3^t<n t<log3(n)]n  t为时间频度
		j = j*3;
	}
}

    通过上面的示例,也很容易可以看出,循环层数的增多会剧烈的增加算法的时间复杂度,如果在递归函数中使用循环,则很容易产生时间复杂度为O(n!)的代码,从数学上看,这种代码随着输入复杂度的增加性能会急剧下降,在使用递归加循环时,还是要多多注意,示例代码如下:

function func(n) {  //n
	if (n<0) {
		return;
	}
	var i = 0;    //n
	for (; i < n; i++) { //n*(n-1)*(n-2)...*1
		console.log("tip");
	}
	func(--i);
}
func(10); 

上面示例的JavaScript代码当传入n为150时的耗时已经和正常循环10000次的相同。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏CDA数据分析师

用SPSS做数据分析?先弄懂SPSS的基础知识吧

1、SPSS数据分析的流程 ? 2、SPSS特性: ? 3、数据的编辑: 1 常量 数值型常量:除了普通写法外还可以用科学计数法,如:1.3E18; 字符型常量...

36010
来自专栏Python小屋

Python版组合数计算方法优化思路和源码

总体说明:本文的优化思路并不局限于Python,但C、C++、C#、Java等语言无法使用内置类型直接表示大整数,需要通过数组等特定形式并自己实现大整数乘除法才...

4265
来自专栏阿凯的Excel

巧妙解决二维表信息匹配问题

1452
来自专栏ml

错排公式

错排公式 百科名片 pala提出的问题: 十本不同的书放在书架上。现重新摆放,使每本书都不在原来放的位置。有几种摆法? 这个问题推广一下,就是错排问题: n个有...

4079
来自专栏自然语言处理

程序员眼中的统计学5

定义:若具有性质A的事件有m个,具有性质B的事件有n个,则具有性质A或性质B的事件有m+n个。

853
来自专栏机器之心

入门 | 一文介绍机器学习中基本的数学符号

选自Machine Learning Mastery 作者:Jason Brownlee 机器之心编译 参与:Edison Ke、黄小天 本文介绍了机器学习中的...

3599
来自专栏我是攻城师

理解算法的复杂度

在计算机科学中,算法的时间复杂度是一个函数,它定性描述该算法的运行时间,时间复杂度常用大O符号表示,不包括这个函数的低阶和首项系数,使用这种方式时,时间的复杂度...

1702
来自专栏机器人网

机器学习中基本的数学符号是什么?

本文介绍了机器学习中的基本数学符号。具体来说有算数符号,包括各种乘法、指数、平方根以及对数;数列和集合符号,包括索引、累加以及集合关系。此外,本文还给出了 5 ...

7576
来自专栏一个爱吃西瓜的程序员

每天学习一点儿算法--二分查找

算法是什么? 算法就是完成一组特定任务的方法。 比如将大象放进冰箱需要三步: 打开冰箱 将大象放进冰箱 关闭冰箱 这就是一种算法。 如果用计算机语言来叙述...

3336
来自专栏深度学习计算机视觉

算法基础+分治策略(算法复习第1弹)

马上就要算法考试了,好紧张,先复习第一波.... 参考文献(算法导论)+(张莉老师ppt) ---- 函数的增长,对算法效率的描述 渐进记号:Θ、Ω、O、o、...

3237

扫码关注云+社区

领取腾讯云代金券