大 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(&fnof;(n)) : 大 O 时间表示法，表示数据规模增长的越高，执行时间越久。因为公式中的常量和系数并不会影响它们之间的关系，所以可以忽略，以上两个公式就可以简写为：

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

时间复杂度分析

明白了「大 O 时间表示法」之后，来试着分析一下代码的时间复杂度，由于 T(n) = O(&fnof;(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)