int sum = 0; // 运行1次
int total = 0; // 运行1次
for (int i = 1; i <= n; i++) { // 运行n+1次
sum += i; // 运行n次
for (int j = 1; j <= n; j++) { // 运行n*(n+1)次
total += i*j; // 运行n*n次
}
}
把所有语句的运行次数加起来:
1
+
1
+
n
+
1
+
n
+
n
∗
(
n
+
1
)
+
n
∗
n
1+1+n+1+n+n*(n+1)+n*n
1+1+n+1+n+n∗(n+1)+n∗n,可以用一个函数T(n)表达:
T
(
n
)
=
2
n
2
+
3
n
+
3
T(n)=2n^2+3n+3
T(n)=2n2+3n+3
当 n 足够大时,例如
n
=
1
0
5
n=10^5
n=105 时,
T
(
n
)
=
2
×
1
0
10
+
3
×
1
0
5
+
3
T(n)=2\times10^{10}+3\times10^5+3
T(n)=2×1010+3×105+3,我们可以看到算法运行时间主要取决于第一项,后面的甚至可以忽略不计。
我们称这样的函数为爆炸增量函数,想一想,如果算法时间复杂度是
O
(
2
n
)
O(2^n)
O(2n)会怎样?随着 n 的增长,这个算法会不会“爆掉”?
常见的算法时间复杂度分类:
常数阶:运行的次数是一个常数,如 5、20、100。常数阶算法时间复杂度通常用
O
(
1
)
O(1)
O(1)表示。
多项式阶:很多算法时间复杂度是多项式,通常用
O
(
n
)
、
O
(
n
2
)
、
O
(
n
3
)
O(n)、O(n^2)、O(n^3)
O(n)、O(n2)、O(n3)等表示。
指数阶:指数阶时间复杂度运行效率极差,程序员往往像躲“恶魔”一样避开它。常见的有
O
(
2
n
)
、
O
(
n
!
)
、
O
(
n
n
)
O(2^n)、O(n!)、O(n^n)
O(2n)、O(n!)、O(nn)等。使用这样的算法要慎重,例如上面的趣味故事。
对数阶:时间复杂度运行效率较高,常见的有
O
(
log
n
)
、
O
(
n
log
n
)
O({\log}n)、O(n{\log}n)
O(logn)、O(nlogn)等。
常见时间复杂度函数曲线如图:
从图中可以看出,指数阶增量随着x的增加而急剧增加,而对数阶增加缓慢。它们之间的关系为:
O
(
1
)
<
O
(
log
n
)
<
O
(
n
)
<
O
(
n
log
n
)
<
O
(
n
2
)
<
O
(
n
3
)
<
O
(
2
n
)
<
O
(
n
!
)
<
O
(
n
n
)
O(1)<O(\log{n})<O(n)<O(n\log{n})<O(n^2)<O(n^3)<O(2^n)<O(n!)<O(n^n)
O(1)<O(logn)<O(n)<O(nlogn)<O(n2)<O(n3)<O(2n)<O(n!)<O(nn)
我们在设计算法时要注意算法复杂度增量的问题,尽量避免爆炸级增量。
趣味故事:兔子序列(斐波那契数列)
f
(
n
)
{
1
,
n
=
1
1
,
n
=
2
f
(
n
−
2
)
+
f
(
n
−
1
)
,
n
>
2
f(n) \begin{cases} 1, &n=1 \\ 1, &n=2 \\ f(n-2)+f(n-1), &n>2 \end{cases}
f(n)⎩⎨⎧1,1,f(n−2)+f(n−1),n=1n=2n>2
递归实现:
#include <QCoreApplication>
#include <QTime>
#include <iostream>
using namespace std;
long double fib(int n) {
long double temp;
if (n < 1) {
return -1;
} else if (n == 1 || n == 2) {
return 1;
} else {
return fib(n - 1) + fib(n - 2);
}
}
int main(int argc, char *argv[])
{
QCoreApplication a(argc, argv);
int n = 0;
cout << "Please input n:" << endl;
cin >> n;
QTime timer;
timer.start();
int fibn = fib(n);
cout << "fibn:" << fibn << endl;
cout << "total time:" << timer.elapsed() << endl;
return a.exec();
}
但实际你自己输入试试后就会发现,效率十分低,因为它会重复计算很多,看一下 n=50 时候的时间。
看到这个时间,应该吓一跳吧。如果 n 再大一点的话更吓人!那我们就不使用递归了,换一种算法吧。
循环实现
long double fib(int n) {
if (n < 1) {
return -1;
} else if (n == 1 || n == 2) {
return 1;
}
int s1 = 1;
int s2 = 1;
for (int i = 3; i <= n; i++) {
s2 = s1 + s2; // 辗转相加法
s1 = s2 - s1; // 记录前一项
}
return s2;
}
我们使用了若干个辅助变量,迭代辗转相加,每次记录前一项,时间复杂度为
O
(
n
)
O(n)
O(n),空间复杂度为
O
(
1
)
O(1)
O(1),是不是比递归好太多了。是不是还有更好的算法呢?那肯定是有的,大家可以自行去研究一下。