数据结构与算法(1)_复杂度分析

发表于 | 分类于

前言

今天在极客时间上开始了数据结构与算法的学习.这一块应该是我最大的薄弱点,希望能借此次学习与笔记,能把这一块短板补上.在此先立一个flag:每周至少一次发表一篇博客笔记.学好数据结构与算法,找到一份满意的工作.

复杂度分析的重要性

复杂度分析是整个算法学习的精髓,只要掌握了它,数据结构和算法的内容基本上就掌握了一半.

为什么这么说?

  • 衡量编写的算法的执行效率,即时间、空间复杂度分析

  • 基于不同设备的性能测试,无法统一执行效率的标准

  • 数据量不够大,无法真实反映算法性能

所以,我们需要不用具体的测试数据来测试，就可以粗略地估计算法的执行效率的方法.

大O复杂度方法

1
2
3
4
5
6
7
8
int cal(int n){
	int sum = 0;
	int i =1;
	for(i;i<=n;i++){
		sum = sum+i;
	}
	return sum;
}

在以上代码中,假设每行代码的执行时间是一样的,即unitTime.第2,3行代码都是一个unitTime.第4,5行都是n个unitTime.执行时间即为(2n+2)*unitTime.即

所有代码执行时间T(n)与每行代码的执行时间成正比

再看

1
2
3
4
5
6
7
8
9
10
11
int cal(int n){
	int sum = 0;
	int i = 1;	
	int j = 1;
	for(i;i<n;i++){
		j=1;
		for(j;j<n;j++){
			sum = sum+i*j;
		}
	}
}

每行代码的执行时间还是unit_time,第2,3,4行分别是一个unitTime.第5,6行分别是n个unitTime.第7,8行分别是$$ n^2 $$个unitTime.所以执行时间
(2$$ n^2 $$+2n+3)*unitTime

总结公式:T(n) = Of(n);

T(n)代表执行时间,n代表数据规模,f(n)代表表示每行代码执行的次数综合,因为这是一个公式,所以用f(n)表示.O表示代码的执行时间T(n)与f(n)表达式成正比.

渐进时间复杂度

根据上边公式,第一个例子T(n)=O(2n+n),第二个例子T(n)=O(2$$ n^2 $$ + 2n+3);这就是大O时间复杂度表示法.大O时间复杂度实际上并不代表代码的具体执行时间,而是表示代码执行时间随数据规模增长的变化趋势,所以也叫渐进时间复杂度,简称时间复杂度.

时间复杂度分析

如何分析一段代码的时间复杂度?

只关注循环次数最多的一段代码

大O这种复杂度表示方法表示的是一种变化趋势.通常忽略掉公式中的常量,低阶,系数,只需记住最大阶的量级就可以了.所以,我们在分析算法和代码的时间复杂度时,只关注循环次数最多的一段代码就可以了.这段核心代码执行次数n的量级,就是整段代码的时间复杂度.

上面的第一个例子

1
2
3
4
5
6
7
8
int cal(int n){
	int sum = 0;
	int i =1;
	for(i;i<=n;i++){
		sum = sum+i;
	}
	return sum;
}

其中第2,3行都是常量级,与n无关,所以对复杂度没有影响.第4,5行是重点,这两段代码执行了n次,所以总时间复杂度就是O(n);

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

一段代码的各个部分时间复杂度可能不同,此时我们取最大的时间复杂度作为本段代码的时间复杂度.

如果一段代码的某个部分,是常量的执行时间,不管是执行1万次,还是10万次,都是一个已知的数跟n无关,就可以忽略.因为时间复杂度表示的是一种变化趋势,虽然对代码执行时间有很大影响,但是对于变化趋势无关,所以我们就可以忽略.

乘法法则: 嵌套代码的复杂程度等于嵌套内外代码复杂度的乘积

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int cal(int n){
	int sum = 0;
	int i =1;
	for(i;i<=n;i++){
		sum = sum+f(i);
	}
	return sum;
}

int f(int n){
	int sum = 0;
	int i =1;
	for(i;i<=n;i++){
		sum = sum+i;
	}
	return sum;
}

单独看cal函数,假设f(i)只是一个普通操作,其复杂程度为T1(n)= O(n);
但,f(n)函数不是简单操作,其复杂程度为T2(n) = O(n);所以整个复杂程度就是T(n) = T1(n)T2(n)=O(n n)=O($$ n^2 $$)

几种常见的复杂度实例分析

常见复杂度量级

  • O(1) 常量阶
  • O(logn) 对数阶
  • O(n) 线性阶
  • O(nlogn) 线性对数阶
  • O($$ n^2 $$) 平方阶,O($$ n^3 $$) 立方阶,O($$ n^k $$) k次方阶
  • O($$ 2^n $$) 指数阶
  • O(n!) 阶乘阶

与数据变化的趋势大概如下:

以上常见复杂度量级可以分为多项式量阶和非多项式量阶,其中只有O($$ 2^n $$)和 O(n!)是非多项量阶.非多项式量阶在n越来越大时,其执行时间会急剧增加,是非常低效的算法

O(1)

只要代码执行时间不随n的增大而增长,都是O(1).

O(logn)、O(nlogn) 最常见也最难分析

1
2
3
4
i = 1;
while(i<=n){
	i = i * 2;
}

当i从1开始取值,每循环一次就乘以2,当大于n时,循环结束.即:

$$ 2^0 $$,$$ 2^1 $$,$$ 2^2 $$,$$ 2^3 $$,…$$ 2^x $$ = n;

所以x即为代码的执行次数,x = $$ log_2n$$.所以时间复杂度为O($$ log_2n$$).在采用大O标记复杂度的时候可以忽略系数,因此不同对数,我们可以忽略对数的”底”,统一表示为O(logn)

那O(nlogn)就是一段代码时间复杂度为O(logn)的函数执行了n遍.例如归并排序,快速排序

O(m+n),O(m * n)

在以下情况下

1
2
3
4
5
6
7
8
9
10
11
12
13
int cal(int m,int n){
	int sum1 = 0;
	int i = 1;
	for(i;i<m;i++){
		sum1 = sum1+i;
	}
	int sum2 =0;
	int j = 1;
	for(j;j<n;j++){
		sum2 = sum2+j;
	}
	return sum1+sum2;
}

此时,我们不知道m,n两个的数据规模,所以加法法则此时失效了.所以复杂度就是O(m+n);但是乘法法则继续有效O(m * n)

最好,最坏情况时间复杂度

1
2
3
4
5
6
7
8
9
10
//n代表数组arr的长度
int find(int[] arr,int n,int x){
	int i = 0;
	int pos = -1;
	for(i;i<n;i++){
		if(arr[i] == x) pos = i;
		break;
	}
	return pos;
}

在无序数组arr中查找变量x.x可能出现在数组的任意位置.

最好情况时间复杂度,就是在最理想情况下,执行这段时间的代码复杂度.在上面例子中即:O(1).

最坏情况时间复杂度,就是在最糟糕的情况下,执行这段时间的代码复杂度.在上面例子中即:O(n)

平均情况时间复杂度

还是上边例子中,要查找x,要么在数组中,要么不在.我们假设在数组中与不在数组中的概率都为1/2.要查找的数据出现在0~n-1这n个位置的概率为1/n.所以,根据概率乘法法则,出现在0~n-1中任意位置的概率就是1/(2n).

因此将所有概率情况考虑进去,那平均时间复杂度:

1 1/(2n) + 2 1/(2n) + 3 1/(2n) + … + n 1/(2n) + n * 1/(2) = (3n+1)/4

用大O表示法表示,去掉系数和常量,这段代码的加权平均时间复杂度还是O(n).

这就是概率论中的加权平均值,也叫做期望值,所以平均时间复杂度的全称应该叫加权平均时间复杂度或者期望时间复杂度.

均摊时间复杂度

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
//arr表示一个长度为n的数组,arr.length就等于n
int[] arr = new int[n];
int count = 0;
void insert(int v){
	if(count == arr.length){
		int sum = 0;
		for(int i=0;i<arr.length;i++){
			sum = sum + arr[i];
		}
		arr[0] = sum;
		count = 1;
	}
	arr[count] = v;
	i++;
}

上面这个例子的最好情况时间复杂度是O(1),最坏情况时间复杂度是O(n);

平均时间复杂度是O(1).

假设数组长度为n,根据数组插入的位置不同,我们可以分为n中情况,每种情况的时间复杂度是O(1).在数组没有空闲时插入一个数据,此时的时间复杂度是O(n).而且简单认为,这n+1中情况发生的概率是一样的都是1/(n+1),所以此时的加权平均时间复杂度:

1 1/(n+1) + 1 1/(n+1) + …. + 1 1/(n+1) + n 1/(n+1) = O(1);

但是这个例子中的平均时间复杂度分析并不需要这么复杂.相对于find函数有两个不同.

首先,find函数在极端情况下复杂度才为O(1),但insert函数大部分情况下的复杂度都是O(1).

其次,insert函数O(1)时间复杂度的插入和O(n)时间复杂度的函数插入,出现的频率是有规律的,一般都是O(n)插入之后,紧跟着n-1个O(1)插入.循环往复

针对这种特殊情况,我们使用摊还分析法,通过摊还分析法得到的时间复杂度即为均摊时间复杂度.

均摊时间复杂度计算:

在这个例子中,每一次O(n)插入后,都会有n-1个O(1)插入.我们把耗时多的那次操作均摊下来到接下来的n-1次耗时少的操作上,其均摊时间复杂度就是O(1).

均摊时间复杂度应用场景:

对一个数据结构进行一组连续操作中,大部分时间复杂程度都很低,只有个别情况下复杂程度会很高.而这些操作之间存在这前后连贯的时序关系,这时候看是否能将较高的时间复杂度操作,均摊上时间复杂度较低的操作上.而且一般能够应用均摊时间复杂度的场景,一般均摊时间复杂度就等于最好情况时间复杂度

空间复杂度分析

也叫渐进空间复杂度,表示算法的存储空间与数据规模的增长关系

1
2
3
4
5
6
7
8
9
10
11
void print(int n){
	int i=0;
	int[] a = new int[n];
	for(i;i<n; ++i){
		a[i] = i * i;
	}
	
	for (i = n-1; i >= 0; --i) {
		System.out.println(a[i]);
	}
}

第2行代码中,我们申请了一个空间存储常量i,它是常量阶跟数据n没有关系,可忽略.第3行申请了一个大小为n的int数组,除此之外并没有其他代码都没有占用太多空间,所以其空间复杂度为O(n);