大 O 时间表示法

1
2
3
4
5
6
7
8
int cal(int n){
int sum = 0;
int i = 1;

for (; i <= n ; ++i) {
sum += i;
}
}

这一段求和代码中,第 2、3 行分别要执行一个 unit_time 的时间。 第 5、6 行分别需要执行 n 个unit_time 的时间。

整段代码所需要执行的时间T(n) = 2*unit_time + 2n*unit_time = (2+2n)*unit_time

1
2
3
4
5
6
7
8
9
10
11
12
13
int cal2(int n) {

int i = 1;
int j = 1;
int sum = 0;

for (; i <= n ; ++i) {
j = 1;
for (; j <= n ; ++j) {
sum = sum + i*j;
}
}
}

这段代码中,第 3、4、5 分别要执行一个 unit_time 的时间。第 7、8 行分别要执行 n 个 unit_time 的时间。第 9、10 行分别要执行 n2 个unit_time 的时间。
所以这段代码所需要执行的时间为T(n) = (3+2n+2n^2)*unit_time

由此可见,代码执行时间与数据规模大小有关,从以下这两个公式中可以得出大 O 时间表示法

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

T(n) = O(ƒ(n)) : 大 O 时间表示法,表示数据规模增长的越高,执行时间越久。因为公式中的常量和系数并不会影响它们之间的关系,所以可以忽略,以上两个公式就可以简写为:

T(n) = O(n)
T(n) = O(n2)

时间复杂度分析

明白了「大 O 时间表示法」之后,来试着分析一下代码的时间复杂度,由于 T(n) = O(ƒ(n)) 中,对常量,系数可以忽略不计,那么在上面两段代码中,只需要去分析代码中循环次数最多的代码就可以了,比如在一段代码中,只需要分析:

1
2
3
for (; i <= n ; ++i) {
sum += i;
}

可以得出第一段代码中的时间复杂度为 O(n)。

在第二段代码中,只需要分析:

1
2
3
4
5
6
for (; i <= n ; ++i) {
j = 1;
for (; j <= n ; ++j) {
sum = sum + i*j;
}
}

可以得出第二段代码中的时间复杂度为 O(n2)

那么在一段代码中,有多段循环的代码,怎么分析呢?比如以下这样的代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
int cal3(int n) {
int sum_1 = 0;
int p = 1;
for (; p < 100; ++p) {
sum_1 += p;
}

int sum_2 = 0;
int q = 1;
for (; q < n; ++q) {
sum_1 += p;
}

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

return sum_1+sum_2+sum_3;
}

这段代码主要是得出sum_1+sum_2+sum_3。通过分析可以得到第一小段代码执行 100 次,是常量,所以时间复杂度是 O(n)。第二小段代码时间复杂度是 O(n)。第三小段代码的时间复杂度是 O(n2)。
那么这个时候就可以取复杂度最大的,也就是说这整段代码的时间复杂度为 O(n2)。

加法法则:当 T1(n) = O(f(n)),T2(n) = O(g(n)) , 则 T(n) = O(max(f(n),g(n)))

还有一种嵌套代码的情况,比如这样的:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
private static int cal4(int n) {
int sum = 0;
int i = 1;

for (; i < n; ++i) {
sum = sum + f(i);
}

return sum;
}

private static int f(int n) {

int sum = 0;
int i = 1;

for (; i < n; ++i) {
sum = sum + i;
}

return sum;
}

在第 6 行代码中,去调用了一个时间复杂度为 O(n) 的的函数,而第 5、6 行的时间复杂度本身就是 O(n),所以这整段代码的时间复杂度就是 T(n) = O(n) * O(n) = O(n2)。

所以,在嵌套代码中,时间复杂度就是嵌套代码内外复杂度的乘积。

常见的复杂度

复杂度由低到高如下:

  1. O(1)
  2. O(logn)
  3. O(n)
  4. O(nlogn)
  5. O(n2)

对于 O(logn) 复杂度:

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

在这里循环执行了 i=i*2,列出来就是:2x=n,也就是log2n=x;底数2可以忽略不计,所以复杂度为O(logn)