时间复杂度与空间复杂度

在涉及到数据结构和算法的时候,无论怎么都绕不开两个知识点:时间复杂度和空间复杂度。之前一直没有仔细学习,在涉及到常见的排序算法的时候,都是直接死记的。最近重新在学习常见的一些数据结构,所以在深入学习之前,先看了下时间复杂度和空间复杂度,意外的发现挺简单的。

大O复杂度表示法

先来看一段代码:

public int cal(int n){
    int sum = 0;
    for (int i=0;i<n;i++){
        sum+=i;
    }
    return sum;
}

从CPU的角度来看,这段代码的每一行都执行着类似的操作:读数据-运算-写数据。尽管每行代码对应的CPU执行的个数、执行的时间都不一样,但是,我们这里只是粗略估计,所以可以假设每行代码执行的时间都一样,为unit_time。

约定好了之后,可以看下上面这段代码的执行总时间。第二行代码,只执行了一次,所以需要1个unit_time。第三、第四行,都执行了n次,所以一共需要2*n*unit_time的执行时间。所以,这段代码总的执行时间为:(2n+2)*unit_time。不难看出,代码的执行时间T(n)与每行代码的执行次数成正比。

再来看一段代码:

public int cal(int n){
	int sum = 0;
	for (int i=0;i<n;i++){
		for (int j=0;j<n;j++){
			sum+=i*j;
		}
	}
	return sum;
}

再来分析一下:第二行代码执行一次,需要1个unit_time,第三行代码执行n次,需要n*unit_time,第四、第五行代码,执行n*n次,故需要n*n*unit_time的执行时间。共需要:(n²+n+1)*unit_time的执行时间。

尽管不知道unit_time的具体值,但是,通过上面两个推导的过程,可以知道,所有代码的执行时间T(n)与每行代码的执行次数n成正比。

我们可以总结成一个公式:

T(n)表示代码的执行时间,n表示数据规模的大小,f(n)表示每行代码执行的次数总和。其中,O就表示T(n)与f(n)成正比。

所以,第一个例子T(n)=O(2n+2),第二个例子T(n)=O(n²+n+1),这就是大O时间复杂度表示法。大O时间复杂度实际上并不具体表示代码真正的执行
时间,而是表示代码执行时间随数据规模增长的变化趋势,所以,也叫作渐进时间复杂度,简称时间复杂度。

当n很大时,你可以把它想象成10000、100000。而公式中的低阶、常量、系数三部分并不左右增长趋势,所以都可以忽略。我们只需要记录一个最大量级就可以了,如果用大O表示法表示刚讲的那两段代码的时间复杂度,就可以记为:T(n) = O(n); T(n) = O(n²)。

时间复杂度分析

好了,花了不少篇幅,引出大O复杂度表示法。下面,结合几种具体的代码,讲解时间复杂度怎么分析。

1、只关注循环执行次数最多的一段代码

前面有讲到,大O表示法,只是表示一种变化的趋势,通常会忽略掉公式中的常量、低阶、系数,只需要记录一个最大阶的量级就可以了。所以,我们在分析一个算法、一段代码的时间复杂度的时候,也只关注循环执行次数最多的那一段代码就可以了。这段核心代码执行次数的n的量级,就是整段要分析代码的时间复杂度。

还是这段代码:

public int cal(int n){
	int sum = 0;
	for (int i=0;i<n;i++){
		sum+=i;
	}
	return sum;
}

第一行是常量级的执行时间,与n的大小无关,循环次数最多的是第三、第四行代码,前面分析过,这两行代码分别被执行了n次,所以时间复杂度就是O(n)。

2、加法法则:总复杂度等于量级最大的那段代码的复杂度

看下面这么一段代码:

public void cal(int n){
	int sum1 = 0;
	for (int i=0;i<100;i++){
		sum1+=i;
	}
	int sum2=0;
	for (int j=0;j<n;j++){
		sum2+=j;
	}
	int sum3=0;
	for (int k=0;k<n;k++){
		for (int l=0;l<n;l++){
			sum3+=k*l;
		}
	}
}

如果单独分析每个for循环的时间复杂度,应该很容易得出。第一段的为O(1),因为执行了100次,是个常量,哪怕执行了100000次,也是个常量。第二段的为O(n),第三段为O(n²)。根据加法法则,这整段代码的时间复杂度就为O(n²)。

隐藏内容,您需要满足以下条件方可查看
End

人已赞赏
Java基础编程语言

HashMap源码解析与面试问题汇总

2020-5-28 17:37:29

Java基础编程语言

【JVM系列】JVM内存模型详解

2020-6-7 15:10:11

0 条回复 A文章作者 M管理员
    暂无讨论,说说你的看法吧
个人中心
今日签到
有新私信 私信列表
搜索