1 时间复杂度

分析程序时间复杂度的时候只需要关注循环中的代码即可

1.1 常见的时间复杂度

时间复杂度分类

常见的时间复杂度有 O(1), O(n), O(logn), O(nlogn), O(\(n^2\)).. O(\(n^k\)), O(\(2^n\)), O(n!)

其中 O(\(2^n\)) 和 O(n!) 在数据规模增大时呈现指数级增长,属于很糟糕的表现

时间复杂度坐标图

1.2 O(1)

1
2
3
4
    public static void main(String[] args) {
        int i = 1;
        System.out.println(i + 1);
    }

时间复杂度: O(1)

1.3 O(n)

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

时间复杂度:O(n)

1.4 O(logn)

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

时间复杂度:O(logn)

如果把运行时 i 的值一个一个的列出来,如下图所示

i 的数值

x 便是最终代码运行次数,由 \(2^x = n\) 可得 \(x = log_2 n\) 所以时间复杂度即为 O(logn)

这里如果将代码改成下述的样子

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

时间复杂度是否变成了 O(\(log_3n\)) 呢?其实并没有还是 O(logn),这是由于 O(\(log_3n\)) = O(\(log_32 * log_2n\)),由于 \(log_32\) 是一个常数,故而可以忽略,O(\(log_3n\)) = O(\(log_2n\)) 故而我们在对数阶的时间复杂度里面忽略底,统一写成 O(logn)。

1.5 O(nlogn)

知道 O(n) 和 O(logn),那么这一种就好理解了,直接看代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
    public int sum(int n) {
        int i = 1;
        while (i <= n) {
            i = i * 3;
        }
    }

     public void n(int n) {
        for (int i = 1; i < n; i++) {
            sum(n);
        }
    }

时间复杂度:O(nlogn)

1.6 O(m + n)

这种时间复杂度取决于两个数据规模,因为无法知道这两个数据规模谁大谁小

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
    int cal(int m, int n) { 
        int sum_1 = 0; 
        for (int i = 1; i < m; ++i) { 
            sum_1 = sum_1 + i; 
        }
        int sum_2 = 0;  
        for (int j = 1; j < n; ++j) { 
            sum_2 = sum_2 + j; 
        }
        return sum_1 + sum_2;
    }

时间复杂度:O(m + n)

2 空间复杂度

1
2
3
4
5
6
    void print (int n) {
        int[] a = new int[n];
        for(int i = 0; i < n; i++) {
            a[i] = i * i;
        }
    }

空间复杂度:O(n)

上述代码只有 int[] a = new int[n] 申请了一个大小为 n 的 int 类型数组,剩下的没有占用更多的空间,所以整段代码的空间复杂度就是 O(n)。