时间复杂度分析

此文是学习《数据结构与算法之美》时的笔记。

为什么要分析复杂度

事后统计法

将代码跑一遍,通过统计、监控得到执行时间和占用空间,这种方法有很大的局限性。

1.1 测试结果非常依赖测试环境
最近有很多同学问我怎么选一款电脑,我首先会问什么需求(电脑用来干什么?是编程开发、还是后期制作、还是游戏或者是追剧?)。对于后期制作方面,选i7当然比i5好,i7的渲染能力是实测强于i5的。对于游戏,i7和i5性能发挥差不多,所以买i5处理器划算。当然还需要考虑散热以及预算等问题。。等等。对于编程测试环境的硬件不同会对测试结果有很大影响。

1.2 测试结果受数据规模的影响很大
对于同一种排序算法,待排序数据的有序度不一样,排序的执行时间就会有很大的差别。如果测试数据很小,测试结果可能无法真实的反应算法的性能。

大O复杂度表示法

1
2
3
4
5
6
7
8
9
10
11
/*求1,2,3,……,n的累加和*/
int add(int n)
{
int sum = 0;
int i = 1;
for(; i<=n; i++)
{
sum = sum + i;
}
return sum;
}

假设每行代码执行时间一样为unit_time,T(n)为这段代码的执行时间。

T(n) = (2n+2)*unit_time

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

上面这段代码的执行时间为:T(n) = (2n^2 + 2n +3)*unit_time

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

所有就有:T(n) = O(f(n))

大O时间复杂度实际上并不表示具体代码真正的执行时间,而是表示代码执行时间随数据规模增长的变化趋势,也称为渐进时间复杂度。当n很大时,公式中的低阶、常量、系数并不左右增长趋势,所以可以忽略。

故,以上两个例子的时间复杂度记为:T(n)=O(n) T(n) = O(n^2)

时间复杂度分析原则

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

大O只表示一种变化趋势,所以在分析一个算法、一段代码的时候,只关注循环执行次数最多的那一段就可以了。

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

fun1的总时间复杂度为O(n)

加法原则

总复杂度等于量级最大的那段代码的时间复杂度。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
int fun2(int n)
{
int sum1 = 0;
int p = 1;
for( ; p<100; p++)
{
sum1 = sum1 + p;
}

int sum2 = 0;
int q = 1;
for( ; q<n; q++)
{
sum2 = sum2 + q;
}

int sum3 = 0;
int i = 1;
int j = 1;
for( ; i<=n; i++)
{
j = 1;
for( ; j<=n; j++)
{
sum3 = sum3 + i*j;
}
}

return sum1+sum2+sum3;
}

第一段执行了100次,和n的规模无关。

第二段代码时间复杂度为O(n)。

第三段代码时间复杂度为O(n^2)。

综合这三段代码的时间复杂度,取最大量级,所以这段代码的时间复杂度为O(n^2)。

乘法原则

嵌套代码的复杂度等于嵌套内外代码复杂度的乘积。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
int fun1(int n)
{
int ret = 0;
int i = 1;
for( ; i<n; i++)
{
ret = ret + fun2(i);
}
return ret;
}

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

这段代码的时间复杂度为:O(n^2)

常见的几种时间复杂度

指数阶:O(2^n) 和 阶乘阶:O(n!)成为非多项式量级。

通常把时间复杂度为非多项式量级的算法问题成为NP问题(Non-Deterministic Polynomial,非确定多项式)。当数据规模n越来越大时,NP问题算法的执行时间会几句增加,非常低效。

O(1)

1
2
3
int i = 1;
int j = 2;
int sum = i + j;

O(logn)、O(nlogn)

1
2
3
4
5
6
/* 1 */
int i = 1;
while( i<=n )
{
i = i*2;
}
1
2
3
4
5
6
/* 2 */
int i = 1;
while( i<=n )
{
i = i*3;
}

1 代码的复杂度为log2(n)

2 代码的复杂度为log3(n)

对数是可以相互转换的:log3(n) = log3(2) * log2(n)所以:O(log3(n)) = O(C * log2(n)),其中C是一个常量,我们忽略系数C。

故将对数阶时间复杂度均表示为:log(n)

如果一段代码的时间复杂度为log(n),执行了n遍,时间复杂度就为nlogn(n)

O(m+n)、O(m*n)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
int fun1(int m, int n)
{
int sum1 = 0;
int i = 1;
for( ; i<m; i++)
{
sum1 = sum1 + i;
}

int sum2 = 0;
int j = 1;
for( ; j<n; j++)
{
sum2 = sum2 + j
}

return sum1+sum2;
}

这段代码的时间复杂度为:O(m+n)

针对这种情况,时间复杂度和m、n均有关,加法原则就不正确了,乘法原则依然正确。


参考文章:《数据结构与算法之美》

文章作者: ahoj
文章链接: https://ahoj.cc/2019/01/Algorithm-复杂度分析/
版权声明: 本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 ahoj 的小本本