文档章节

数据结构与算法-如何计算时间复杂度

raylee2015
 raylee2015
发布于 2015/08/24 14:39
字数 963
阅读 9
收藏 1

今天我们来谈一下如何计算时间复杂度。

时间复杂度概念:(百度版)

同一问题可用不同算法解决,而一个算法的质量优劣将影响到算法乃至程序的效率。算法分析的目的在于选择合适算法和改进算法。

计算机科学中,算法的时间复杂度是一个函数,它定量描述了该算法的运行时间。这是一个关于代表算法输入值的字符串的长度的函数。时间复杂度常用大O符号表述,不包括这个函数的低阶项和首项系数。使用这种方式时,时间复杂度可被称为是渐近的,它考察当输入值大小趋近无穷时的情况。

注意:本文承接上一篇《数据结构与算法-函数的渐近增长》,想详细了解渐近增长,请点击:数据结构与算法-函数的渐近增长


现在先上代码,请大家详细阅读注释,因为整个计算过程都已经在注释里面体现。


/**
 * 计算时间复杂度
 * 
 * @author ray
 * 
 */
public class Test {

	private void test1(int n) {
		System.out.println(n);// 操作=1
	}

	private void test2(int n) {
		int a = 0;
		for (int i = 0; i < n; i++) {// 操作=n
			a++;// 操作=1
		}
		// 总操作=n*1=n
		// 时间复杂度=O(1)
	}

	private void test3(int n) {
		int a = 0;
		for (int i = 0; i < n; i++) {// 操作=n
			for (int j = 0; j < n; j++) {// 操作=n
				a++;// 操作=1
			}
		}
		// 总操作=n*n*1=n^2
		// 时间复杂度=O(n^2)
	}

	private void test4(int n) {
		int a = 0;
		for (int i = 0; i < n; i++) {
			for (int j = i; j < n; j++) {// 操作=n,n-1,n-2,n-3......1=(n+1)n/2
				a++;// 操作=1
			}
		}
		// 总操作=(n+1)n/2=n^2/2+n/2
		// 由于时间复杂度是一个抽象的概念,当n的规模达到一定程度的时候,时间复杂度只取最高次幂,而且忽略其他次要项和系数
		// 时间复杂度=O(n^2)
	}

	private void test5(int n) {
		int a = 0;
		for (int i = 0; i < n; i++) {
			for (int j = i; j < n; j++) {// 操作=n,n-1,n-2,n-3......1=(n+1)n/2
				a++;// 操作=1
				System.out.println(a);// 操作=1
				// for循环内总操作=2
			}
		}
		// 总操作=(n+1)n/2*2=n^2+n
		// 由于时间复杂度是一个抽象的概念,当n的规模达到一定程度的时候,时间复杂度只取最高次幂,而且忽略其他次要项和系数
		// 时间复杂度=O(n^2)
	}

	private void test6(int n) {
		int a = 0;
		for (int i = 0; i < n; i++) {
			for (int j = i; j < n; j++) {// 操作=n,n-1,n-2,n-3......1=(n+1)n/2
				a++;// 操作=1
				System.out.println(a);// 操作=1
				System.out.println(i);// 操作=1
				// for循环内总操作=3
			}
		}
		// 总操作=(n+1)n/2*3=n^2*3/2+n*3/2
		// 由于时间复杂度是一个抽象的概念,当n的规模达到一定程度的时候,时间复杂度只取最高次幂,而且忽略其他次要项和系数
		// 时间复杂度=O(n^2)
	}

	private void test7(int n) {
		int a = 0;
		int b = 0;
		for (int i = 0; i < n; i++) {// 操作=n
			for (int j = 0; j < n; j++) {// 操作=n
				a++;// 操作=1
				System.out.println(a);// 操作=1
				// for循环内总操作=2
				for (int k = 0; k < n; k++) {// 操作=n
					b++;// 操作=1
					// for循环内总操作=1
				}
			}
		}
		// 总操作==n^3+2n^2
		// 由于时间复杂度是一个抽象的概念,当n的规模达到一定程度的时候,时间复杂度只取最高次幂,而且忽略其他次要项和系数
		// 时间复杂度=O(n^3)
	}

	public static void main(String[] args) {
		int n = 10;
		Test t = new Test();
		t.test1(n);
		t.test2(n);
		t.test3(n);
		t.test4(n);
		t.test5(n);
		t.test6(n);
		t.test7(n);
	}
}



版权声明:本文为博主原创文章,未经博主允许不得转载。

© 著作权归作者所有

raylee2015
粉丝 6
博文 265
码字总数 44224
作品 0
江门
私信 提问
1.数据结构&算法的引言+时间复杂度

print(sumOfN(10)) print(foo(10)) start_time = time.time()for a in range(0,1001): end_time = time.time()print(endtime-starttime) 执行结果为: 0 500 500200 375 425375 200 425500 0......

杨洪涛
06/01
0
0
数据结构与算法——学习整理记录

===注:此文由本人结合网上资源整理总结而来,仅代表个人的学习与理解,如有错漏,欢迎指正!=== # 1. 数据结构 ## 1.1 数据结构是什么? 数据结构,直白地理解,就是研究数据的逻辑关系与存...

elinuxboy
2018/11/28
0
0
一致性Hash算法实现

一致性Hash算法 关于一致性Hash算法,在我之前的博文中已经有多次提到了,MemCache超详细解读一文中"一致性Hash算法"部分,对于为什么要使用一致性Hash算法、一致性Hash算法的算法原理做了详...

此鱼不得水
2016/03/17
56
0
《数据结构》学习笔记二:算法(一)

本节虽然名为“算法”,其实讲的只是算法的一些概念以及评估方式,并没有涉及很复杂的算法。 解决问题: 什么是算法 算法的特性 算法设计的要求 如何评估一个算法的优劣 通过本节的学习,我们...

小曼Study
2018/10/11
0
0
算法的时间复杂度计算

计算算法的时间复杂度,通常说的是算法的渐进增长时间复杂度,也就是随着数据的变大,该算法所需要的时间是如何增长的。 推导时间复杂度的原则 用常数1取代运行事件中的所有加法常数。 在修改...

光哥很霸气
2017/01/09
0
0

没有更多内容

加载失败,请刷新页面

加载更多

java快递电子面单打印接口对接demo

之前的后天管理系统的电子面单打印使用的是灵通打单。 使用相对比较麻烦,需要到处Excel之后再导入,麻烦。 快递鸟有电子面单api,后台系统直接对接很是方便,不过也遇到了好些问题。 不难是...

程序的小猿
27分钟前
3
0
fasjtjson文档

https://github.com/alibaba/fastjson/wiki/JSONField

jirak
27分钟前
3
0
Mybatis中插入多条记录

Oracle数据库 实现方法 <insert id="saveWithdrawLog"> INSERT ALL INTO OSM_TRADE_DETAIL(SID,MBR_ID,USR_ID,TRADE_MONEY,TRADE_TYPE,TRADE_TIME,TRADE_WAY,PAY_ID) VALUES(#{si......

豫华商
28分钟前
3
0
Flink on YARN(下):常见问题与排查思路

作者:杨弢(搏远) Flink 支持 Standalone 独立部署和 YARN、Kubernetes、Mesos 等集群部署模式,其中 YARN 集群部署模式在国内的应用越来越广泛。Flink 社区将推出 Flink on YARN 应用解读...

开源中国小二
30分钟前
3
0
技术沙龙|京东云端到端多媒体关键技术揭秘

编者按:从带来更高编码效率、更好的用户体验的京享高清,到直播架构与网络演进优化,从而为用户带来更流畅的观看体验,以及运维系统的异常自动修复和高弹性的多媒体存储架构,一层一层展示出...

京东云技术新知
30分钟前
3
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部