时间和空间复杂度分析

首先要知道为什么要有时间和空间复杂度的概念,要想知道一个程序的执行效率理论上来说就应该直接上机测试，但是由于硬件的差异，我们很难做到统一，所以就产生了时间和空间复杂度，用来估计算法的效率。

时间复杂度

时间复杂度主要衡量的是一个算法的运行速度

时间复杂度的概念

时间复杂度的定义：一个算法所花费的时间与其中语句的执行次数成正比例，算法中的基本操作的执行次数，为算法的时间复杂度

时间复杂度有最好情况下，平均情况下和最坏情况下

一般指的时间复杂度是最坏情况下

大O渐进表示法

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-jtdnih8D-1662871856965)(C:/Users/chuanfei/AppData/Roaming/Typora/typora-user-images/image-20220721210811759.png)]

我们只需要将知道一个大概的执行次数就可以了，所以采用大O渐进表示法

// 请计算一下func1基本操作执行了多少次？
void func1(int N){
int count = 0;
for (int i = 0; i < 2N ; i++) {
	for (int j = 0; j < N^2 ; j++) {
	count++;
	}
}
for (int k = 0; k < 2 * N ; k++) {
	count++;
}
int M = 10;
while ((M--) > 0) {
	count++;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

精确计算就是2* N^3+2N+10，但是经过大O渐进表示法，就是时间复杂度就是O(N ^3)

几个例子

void func2(int N) {
int count = 0;
for (int k = 0; k < 2 * N ; k++) {
count++;
}
int M = 10;
while ((M--) > 0) {
count++;
}
System.out.println(count);
}
1
2
3
4
5
6
7
8
9
10
11

2* N+10，去掉后面的数字，去掉系数，所以时间复杂度就是O（N）

// 计算func3的时间复杂度？
void func3(int N, int M) {
int count = 0;
for (int k = 0; k < M; k++) {
	count++;
}
for (int k = 0; k < N ; k++) {
	count++;
}
System.out.println(count);
}
1
2
3
4
5
6
7
8
9
10
11

由于M和N未知，所以就是O（M+N）

void func4(int N) {
int count = 0;
for (int k = 0; k < 100; k++) {
	count++;
}
System.out.println(count);
}	
1
2
3
4
5
6
7

循环了100次，是一个确定的常数，所以就是O（1）

最坏情况下就是不优化，N*(N-1)=N^2-N,所以时间复杂度(最坏情况)就是O（N ^2 ）

最好的情况就是数组就是升序的，只走了一遍全部数字，第二个循环就直接跳出去了，没有发生交换，所以此时 最好的情况就是O（N）

冒泡排序完整版（升序）

import java.util.Arrays;

 class BubbleSort {
  public  static void  bubblesort(int[] arr) {  	//记得加上static，确保main里面可以带调用
        for (int end =arr.length;end>0;end--) {
            boolean flag=true;
            for (int i = 1; i <end ; i++) {
                if (arr[i - 1] > arr[i]) {
                    int tmp = arr[i - 1];
                    arr[i - 1] = arr[i];
                    arr[i] = tmp;
                }
                flag = false;
            }
            if (flag==true) {
                break;
            }
        }
    }
    public static void main(String[] args) {
        int[] arr = {1, 3, 2, 4, 23, 6};
        //BubbleSort bubbleSort = new BubbleSort();
        //要是上面的方法没有加上static也可以定义一个对象，new一下直接补全
        //但还是在方法前面加上static最省心
        bubblesort(arr);
        System.out.println(Arrays.toString(arr));

    }
}

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

冒泡排序+二分查找

import java.util.Arrays;
import java.util.Scanner;

//冒泡排序
public class BubbleSort {
    static void  bubblesort(int[] arr) {
        for (int end =arr.length;end>0;end--) {
            boolean flag=false;
            for (int i = 1; i <end ; i++) {
                if (arr[i - 1] > arr[i]) {
                    int tmp = arr[i - 1];
                    arr[i - 1] = arr[i];
                    arr[i] = tmp;
                }
                flag = true;
            }
            if (!flag) {
                break;
            }
        }
    }
//二分查找
    static int  Binarysort(int[] arr, int value) {
        int l=0;
        int r=arr.length-1;
        while (l <= r) {
            int mid = l + (r - l) / 2;
            if (arr[mid] < value) {
                l = mid + 1;
            } else if (arr[mid] > value) {
                r = mid - 1;
            }else{
                return mid;
            }
        }
        return -1;
    }
    
    public static void main(String[] args) {
        int[] arr = {1, 3, 2, 4, 23, 6};
        bubblesort(arr);//二分查找的前提是有序数组
        Scanner scanner = new Scanner(System.in);//创建一个scanner的对象
        while (scanner.hasNext()) {
            int value = scanner.nextInt();
            if (Binarysort(arr, value) == -1) {
                System.out.println("找不到这个数字");
            }else{
                System.out.println("找到了，下标为"+Binarysort(arr, value));
            }
        }
    }
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

二分查找的时间复杂度

最坏的情况就是要找的数字在最右边，此时要查找的次数最多

所以二分查找的时间复杂度是O(log₂n)

递归的时间复杂度

递归的时间复杂度=递归的次数*每次递归执行的次数

计算阶乘递归的时间复杂度

public static int factorial(int n) {
    return n > 2 ? n : factorial(n - 1) * n;
}
1
2
3

一共要递归n-1次，每次递归执行一次三目运算符，所以这个阶乘的时间复杂度是O(n)

计算斐波那契数的时间复杂度

public static int feb(int n) {
        return n < 2 ? n : feb(n - 1) + feb(n - 2);
    }
1
2
3

假设n=3，要是在最坏情况下，那就是2^ 0+2^ 1+2^ 2

类比开来，就是2⁰⁺² 0+2^ 1+2^ 2 +……+2^(n-1) ,也就是一个等比数列求和问题

所以结果为2^n+1,所以时间复杂度为O(2 ^n) —指数级别增长

空间复杂度

==空间复杂度算的是额外的变量的个数。==空间复杂度也使用大O渐进表示法。

计算冒泡排序的空间复杂度

public class BubbleSort {
    static void  bubblesort(int[] arr) {
        for (int end =arr.length;end>0;end--) {
            boolean flag=false;
            for (int i = 1; i <end ; i++) {
                if (arr[i - 1] > arr[i]) {
                    int tmp = arr[i - 1];
                    arr[i - 1] = arr[i];
                    arr[i] = tmp;
                }
                flag = true;
            }
            if (!flag) {
                break;
            }
        }
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

在代码运行的时候，有end、flg、i 、tmp 4个额外的变量，所以空间复杂度是O(1)

计算斐波那契数的空间复杂度

int[] fibonacci(int n) {
long[] fibArray = new long[n + 1];
fibArray[0] = 0;
fibArray[1] = 1;
for (int i = 2; i <= n ; i++) {
fibArray[i] = fibArray[i - 1] + fibArray [i - 2];
}
return fibArray;
}
1
2
3
4
5
6
7
8
9
10

会根据数组的大小，开辟不同的变量大小,是n+1,s所以时间复杂度是O（N)

递归的空间复杂度

long factorial(int N) {
	return N < 2 ? N : factorial(N-1)*N;
}
1
2
3

每递归进去一次，就要开辟一次内存，所以这个阶乘的空间复杂度是O（N）

常见的时间复杂度：O（1）、O(log₂n)、O（N）、O(N*log₂n>)、O(N^2)、O（2 ^n）

以上的时间复杂度的效率是越来越慢的

总结来说，要想知道时间复杂度不能只看代码，还要关注代码的实现思想。