Posted on 

从一道简单编程题了解时间复杂度

这是一道来自PTA的编程题:

最大子列和问题( 点击可显示题目 )

暴力枚举

使用暴力枚举,这道题显然很“简单”:(尽管代码繁琐到让人难以直视)

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
#include <stdio.h>
using namespace std;

int main()
{
int K;
scanf("%d", &K);
int series[K];
int result = 0;
int temp = 0;
for(int i=0; i<K; ++i)
{
scanf("%d", &series[i]);
}
for (int i=0; i<K; ++i)
{
for(int j=i+1; j<K; ++j)
{
for(int k=i; k<=j; ++k)
{
temp += series[k];
}
if (temp > result) result = temp;
temp = 0;
}
temp = 0;
}
printf("%d", result);
return 0;
}

对于少量的数据,这个算法自然可以接受。但是当输入数据量级逐渐上升,这个算法就力不从心了:


那这个算法到底有多“笨”呢? 这个问题就需要“时间复杂度”来解答。

常见时间复杂度

时间复杂度,可以衡量一个算法所消耗的时间。一个通用的分析方法称为“大O表示法”,即表示为:T(n) = O(f(n))

常数阶 O(1)

顾名思义,这个算法的复杂度就像一个“常数”,无论代码有多长,里面没有循环等复杂的结构,其复杂度就是简单的O(1)

示例:

1
2
3
int a = 1;
int b = 5;
int c = a * b;

线性阶O(n)

当代码中包含单层循环结构,那么循环体中的代码会重复执行n遍,其复杂度与n有关,复杂度为O(n)

示例:

1
2
3
4
for (int i=0; i<10; ++i)
{
printf("%d", i);
}

对数阶O(logN)

像上面示例中,代码重复执行的次数是显而易见的,也就是10次,复杂度就是O(n).那么如果换成下面的代码:

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

循环的次数就需要一定的计算了:在每次循环中,i都被乘以2,因此log2n次后循环结束,即复杂度为O(logn)

线性对数阶O(nlogn)

对数阶被一个复杂度为O(n)的循环结构包裹,其复杂度即为两个复杂度之积 O(nlogn)

平方阶O(n2)

从上一个可以看到,嵌套结构的复杂度就是两个复杂度“乘起来”,那么O(n2)自然就是两个复杂度为O(n)的结构嵌套:

1
2
3
4
5
6
7
for (int i=0; i<m; ++i)
{
for (int j=0; j<n; ++j)
{
printf("%d %d", i,j);
}
}

类似的,还有O(n3) O(n4) O(nk)…..

小窍门

再补充几个计算的窍门:

  1. 两段算法复杂度相加(并列),结果是其中复杂度更大的那个。
  2. 两段算法复杂度相乘(嵌套),结果是两个复杂度“相乘”。T1(n) * T2(n) = O( f1(n) * f2(n) )

分析算法

回到这个不知道有多“笨”的算法,它到底有多复杂?

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
//...
int main()
{
// ...
for(int i=0; i<K; ++i)
{
//此处复杂度为 O(n)
}
for (int i=0; i<K; ++i)
{
for(int j=i+1; j<K; ++j)
{
for(int k=i; k<=j; ++k)
{
// 三层嵌套 复杂度是O(n的三次方)
}
// ...
}
// ...
}
// ...
}

因此,这段算法的复杂度是 O(n3)。 当输入数据达到了10000个整数时,这个算法要进行计算的次数是很可怕的,自然也就超时了。

修改算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include<stdio.h>
int main()
{
int i,k;
int getNum,max=0;
int sum=0;
scanf("%d",&k);
for(i=0;i<k;i++)
{
scanf("%d",&getNum);
sum+=getNum;
if (sum<0)
sum=0;
if (sum>max)
max=sum;
}

printf("%d",max);
}

具体过程就不赘述了,这个简洁不少的算法的复杂度怎么样呢?

很显然,一层for循环,复杂度就是O(n)


不仅可以在规定时间内跑完,而且只要短短9ms就能计算十万个输入数据。可见,O(n) 与 O(nk) 的差距是数量级的,非常可怕。


这张图包含了一些常用的时间复杂度的增长趋势,可以看出,O(logn) 是“最好”的复杂度,增长很缓慢,O(n2)几乎成了一条纵向的直线,还有就是“老大哥” O(n!) 。 如果实现了一个复杂度是 O(n!)的算法,那可真是一场灾难了。

开往-友链接力
A member of 开往-友链接力

This site was deployed by @OasisLee using Stellar.

本站由Vercel提供托管与Serverless支持 | PlanetScale提供数据库支持