算法基础——时间复杂度和空间复杂度

时间复杂度和空间复杂度是什么？

时间复杂度是一个算法运行所需要的时间。

空间复杂度是一个算法运行所需要的储存空间

时间复杂度

同样的算法，在不同环境下（如i7和i5的cpu）所运行的时间可能不相等，故需要一种对算法所需时间的通用表示方法——大O表示法

大O表示法

每个算法都是对数据的操作（交换、遍历等），当操作完成算法便结束，故数据的规模（以下统称为n）是对算法起决定性作用的

• 与n无关的操作，其时间复杂度为O(1)
• 对n的非循环操作，其时间复杂度为O(1)
• 对n的循环操作，其时间复杂度取决于循环层次（与循环次数无关）
• 将以上复杂度加起来得到最终的复杂度

下面进行举例

O(1)

与n无关的操作或对n的非循环操作

void time(int n) {
    int a = 1;
    int b = 2;
    int c = a + b;
}
1
2
3
4
5

void time(int n) {
    int a = n + 1;
}
1
2
3

O(n)

对n的循环操作

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

其时间复杂度与循环次数无关，如下也是O(n)

void time(int n) {
    int sum = 0;
    for (int i = 0; i < 2 * n; i++) {
        sum += n;
    }
}
1
2
3
4
5
6

O(n*n)

如下是对n的多层循环操作，

void time(int n) {
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            System.out.println(n[i][j]);
        }
    }
}
1
2
3
4
5
6
7

Ο(1)＜Ο(log2n)＜Ο(n)＜Ο(nlog2n)＜Ο(n2)＜Ο(n3)＜…＜Ο(2n)＜Ο(n!)