算法的空间复杂度与时间复杂度介绍

发表于 阅读次数： 评论数： 本文字数： 916 阅读时长 ≈ 1 分钟

如何评价一个算法的好坏

一个算法的好坏是通过时间复杂度和空间复杂度来衡量的。

  • 时间复杂度：就行执行算法的时间成本。
  • 空间复杂度：就行执行算法的内存空间成本。

大 O 表示法的介绍

对数的概述

大 O 表示法的概述

算法的时间复杂度与空间复杂度都是用大 O 来表示的（即大欧表示法），写作 O(*)。由于目前的内存成本比较便宜，因此我们一般谈论算法的复杂度都是指时间复杂度。

大 O 表示法：算法的时间复杂度通常用大 O 符号表示，其定义为 T[n] = O(f(n))。称函数 T(n) 以 f(n) 为界，或者称 T(n) 受限于 f(n)。如果一个问题的规模是 n，那么解决这一问题的某一算法所需要的时间为 T(n)。T(n) 称为这一算法的 “时间复杂度”。当输入量 n 逐渐加大时，时间复杂度的极限情形称为算法的 “渐近时间复杂度”。常见时间复杂度的大 O 表示法有以下几种：

大 O 表示法的读音

  • O(1) 读作 "欧 1"
  • O(n) 读作 "欧 n"
  • O(n²) 读作 "欧 n 的平方"
  • O(log n) 读作 "欧 log n"

常用算法的时间复杂度举例

常数阶 O (1)

  • 数据库表按照主键查询记录
  • Java 中 HashMap 的 get 操作

线性阶 O (n)

  • 一段代码循环执行 n 次，那么此时代码的时间复杂度就是 O (n)
1
2
3
4
5
6
7
8
9
public class Test {

    public void circle(int n) {
        for (int i = 0; i < n; i++) {   // 执行 n 次
            System.out.println(i);  // 执行 n 次
        }
    }

}

对数阶 O (log n)

  • 二分查找算法
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
public class Test {

    public static int binarySearch(int[] arraySorted, int target) {
        int left = 0;
        int right = arraySorted.length - 1;

        while (left <= right) {
            int middle = left + (right - left) / 2;
            if (arraySorted[middle] == target) {
                return middle;
            } else if (arraySorted[middle] ### target) {
                right = middle - 1;
            } else {
                left = middle + 1;
            }
        }
        return -1;
    }

    public static void main(String[] args) {
        int[] arrays = new int[] {1, 11, 22, 33, 77, 99, 103};
        int target = 77;
        System.out.println(binarySearch(arrays, target));
    }

}

线性对数阶 O (n log n)

  • 将一段时间复杂度为对数阶 O (log n) 的代码重复执行 n 次，那么此时代码的时间复杂度就是线性对数阶 O (n log n)
1
2
3
4
5
6
7
8
9
10
11
12
public class Test {

    public void logarithm(int n) {
        int count = 1;
        for (int i = 0; i < n; i++) {   // 执行 n 次
            while (count <= n) {    // 执行 log n 次
                count = count * 2;  // 执行 n log n 次
            }
        }
    }

}

平方阶 O (n²)

  • 一段代码拥有两层循环，那么此时代码的时间复杂度就是平方阶 O (n²)
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
public class Test {

    /**
     * 当内层循环和外层循环的次数一致时，时间复杂度为平方阶 O(n²)
     */
    public void square(int n) {
        for (int i = 0; i < n; i++) {   // 执行 n 次
            for (int j = 0; j < n; j++) {   // 执行 n 次
                System.out.println(i + j);  // 执行 n 平方次
            }
        }
    }

    /**
     * 当内层循环和外层循环的次数不一致时，时间复杂度如下：
     * 内层循环执行 m 次，其时间复杂度为线性阶 O(m)，
     * 外层循环执行次数为 n 次，其时间复杂度为线性阶 O(n)，
     * 整段代码的时间复杂度就是 O(m*n)，即循环的时间复杂度等于循环体的时间复杂度乘以该循环运行次数。
     */
    public void square(int n, int m) {
        for (int i = 0; i < n; i++) {   // 执行 n 次
            for (int j = 0; j < m; j++) {   // 执行 m 次
                System.out.println(i + j);  // 执行 m*n 次
            }
        }
    }

}

立方阶 O (n³)

  • 一段代码拥有三层循环，那么此时代码的时间复杂度就是立方阶 O (n³)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public class Test {

    void run(int n) {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                for (int k = 0; k < n; k++) {
                    System.out.print("Hello, World");
                }
                System.out.print("------");
            }
            System.out.print("******");
        }
    }

}

指数阶 O (2ⁿ)

  • Java 中 HashMap 的扩容操作，扩容后的大小是原始大小的一倍

阶乘 O (n!)

  • 实现时间复杂度为阶乘 O (n!) 的代码并不常见，因为这种复杂度通常意味着算法需要非常多的计算步骤，这里不再累述。

时间复杂度的排序

  • 一个算法在 n 规模下，其时间复杂度的排序，从小到大依次排列如下：
  • O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(n³) < O(2ⁿ) < O(n!)