时间复杂度和空间复杂度

时间复杂度和空间复杂度

算法的时间复杂度和空间复杂度是用来描述算法优劣的两个指标

时间复杂度

算法的时间复杂度反应了算法执行时间随输入规模增长而增长的量级,通常的时间复杂度指的是最坏时间复杂度

时间复杂度预估步骤

1. 找出基准语句,即算法中执行次数最多的那条语句
2. 计算基本语句的执行次数的数量级
3. 用O()表示算法的时间性能,括号内为基准语句执行次数的数量级

预估时间复杂度的具体实例

注: 只计算时间复杂度

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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
// 时间复杂度 O(1)
if (n > 10) {
    System.out.println("n > 10");
} else if (n > 5) { // 2
    System.out.println("n > 5");
} else {
    System.out.println("n <= 5"); 
}

// 时间复杂度 O(n)
for (int i = 0; i < n; i++) {
    // 循环内语句最大执行次数: n
    System.out.println("test");
}

// 时间复杂度 O(n)
for (int i = 0; i < n; i++) {
    for (int j = 0; j < 15; j++) {
        // 内层循环内语句最大执行次数: 15*n
        System.out.println("test");
    }
}

// 时间复杂度 O(n^2)
for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
        // 内层循环内语句最大执行次数: n^2
        System.out.println("test");
    }
}

// 时间复杂度 O(logn)
// java中整形数值相除当x<y时x/y=0
while ((n = n / 2) > 0) {
    // 循环内语句最大执行次数: n除几次2=1  ->  log2(n)
    System.out.println("test");
}

// 时间复杂度 O(logn)
while ((n = n / 5) > 0) {
    // 循环内语句最大执行次数: n除几次5=1  ->  log5(n)
    System.out.println("test");
}

// 时间复杂度 O(nlogn)
for (int i = 1; i < n; i = i * 2) {
    // 外层循环执行次数: log2(n)
    for (int j = 0; j < n; j++) {
        // 单独内层循环语句执行次数为: n
        // 基准语句最大执行次数为: n*log2(n)
        System.out.println("test");
    }
}

空间复杂度

算法的空间复杂度是算法在运行时间内临时占用的内存空间的大小,但一般的程序只要满足占用空间小于可用空间即可. 所以尝尝牺牲空间复杂度来满足时间复杂度