算法分析（一）

一、算法的时间复杂度分析

1.1、大O表示法

1）、在进行算法分析时，语句总的执行次数 T(n) 是关于问题规模 n 的函数，进而分析 T(n) 随着 n 的变化情况并确定 T(n)的量级

2）、算法的时间复杂度，我们记作：T(n) = O(f(n)) ，它表示随着问题规模 n 的增大，算法执行时间的增长率和 f(n) 的增长率相同，其中 f(n) 是问题规模 n 的某个函数，在这里，我们需要明确一个事情：执行次数 = 执行时间

3）、用大写 O()来体现算法时间复杂度的记法，我们称之为大O表示法。一般情况下，随着输入规模 n 的增大，T(n) 增长最慢的算法为最优算法。

算法一：

public class Client {
    public static void main(String[] args) {
        int sum = 0;//执行一次
        int n = 100;//执行一次
        sum = (n + 1) * n / 2;//执行一次
        System.out.println(sum);
    }
}

算法二：

public class Client {
    public static void main(String[] args) {
        int sum = 0;//执行1次
        int n = 100;//执行1次
        for (int i = 1; i <= n; i++) {
            sum += i;//执行n次
        }
        System.out.println(sum);
    }
}

算法三：

public class Client {
    public static void main(String[] args) {
        int sum = 0;//执行1次
        int n = 100;//执行1次
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                sum += i;//执行n^2次
            }
        }
        System.out.println(sum);
    }
}

如果忽略判断条件的执行次数和输出语句的执行次数，那么当输入规模为 n 时，以上算法执行的次数分别为：

1、算法一：3 次

2、算法二：n + 2 次

3、算法三：n^2 + 2 次

1.1.1、大O表示法规则

大O表示法有以下几个规则可以使用：

1、用常数 1 取代运行时间中的所有加法常数

2、在修改后的运行次数中，只保留高阶项

3、如果最高阶项存在，且常数因子不为 1，则去除与这个项相乘的常数

根据规则，我们可以推算上述三个算法的时间复杂度：

1、算法一：O(1)

2、算法二：O(n)

3、算法三：O(n^2)

1.2、常见的大O阶

1.2.1、线性阶

一般含有非嵌套循环涉及线性阶，线性阶就是随着输入规模的扩大，对应计算次数呈直线增长，例如：

public class Client {
    public static void main(String[] args) {
        int sum = 0;
        int n = 100;
        for (int i = 1; i <= n; i++) {
            sum += i;
        }
        System.out.println(sum);
    }
}

上面这段代码，他循环的时间复杂度为 O(n)，因为循环体中的代码需要执行 n 次

1.2.2、平方阶

一般嵌套循环属于这种时间复杂度，例如：

public class Client {
    public static void main(String[] args) {
        int sum = 0;
        int n = 100;
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                sum += i;
            }
        }
        System.out.println(sum);
    }
}

上面这段代码，n = 100，也就是说，外层循环每执行一次，内层循环执行 100 次，那总共程序想要从两个循环中出来，就需要执行 100*100 次，也就是 n 的平方次，所以这段代码的时间复杂度是 O(n^2)

1.2.3、立方阶

一般三层嵌套循环属于这种时间复杂度

public class Client {
    public static void main(String[] args) {
        int sum = 0;
        int n = 100;
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                for(int k = 1; k <= n; k++){
                    sum += i;
                }
            }
        }
        System.out.println(sum);
    }
}

上面这段代码，n = 100，也就是说，外层循环每执行一次，中间循环就执行 100 次，中间循环每执行一次，内层循环就需要执行 100 次，那总共程序想要从三个循环中出来，就需要执行100*100*100次，也就是 n 的立方次，所以这段代码的时间复杂度是 O(n^3)

1.2.4、对数阶

对数，属于高中数学的内容，我们以分析程序为主，数学为辅：

public class Client {
    public static void main(String[] args) {
        int i = 1;
        int n = 100;
        while(i < n){
            i = i * 2;
        }
    }
}

由于每次 i * 2 之后，就距离 n 更近一步，假设有 x 个 2 相乘后大于 n，则会推出循环，由于是 2^x=n，得到 x = log(2)n，所以这个循环的时间复杂度为O(logn)

1.2.5、常数阶

一般不涉及循环的操作都是常数阶，他不会随着 n 的增长而增加操作次数，例如：

public class Client {
    public static void main(String[] args) {
        int n = 100;
        int i = n + 2;
        System.out.println(i);
    }
}

上述代码，不管输入规模 n 是多少，都只执行 2 次，根据大O表示法规则，时间复杂度为 O(1)

1.3、函数调用的时间复杂度分析

之前，我们分析的都是单个函数内，算法代码的时间复杂度，接下来我们分析函数调用过程中的时间复杂度

案例一：

public class Client {
    public static void main(String[] args) {
        int n = 100;
        for (int i = 0; i < n; i++) {
            show(i);
        }
    }
    
    private static void show(int i){
        System.out.println(i);
    }
}

在 main 方法中，有一个 for 循环，循环体调用了 show 方法，由于 show 方法内部只执行了一行代码，所以 show 方法的时间复杂度为 O(1) ，那 main 方法的时间复杂度就是 O(n)

案例二：

public class Client {
    public static void main(String[] args) {
        int n = 100;
        for (int i = 0; i < n; i++) {
            show(i);
        }
    }

    private static void show(int i){
        for (int j = 0; j < i; j++) {
            System.out.println(i);
        }
    }
}

在 main 方法中，有一个 for 循环，循环体调用了 show 方法，由于 show 方法内部也有一个 for 循环，所以 show 方法的时间复杂度为 O(n) ，那 main 方法的时间复杂度就为 O(n^2)

二、算法的空间复杂度分析

2.1、Java 中常见内存占用

1、基本数据类型内存占用情况：

数据类型	内存占用字节数
byte	1
short	2
int	4
long	8
float	4
double	8
char	2
boolean	1

2、一个字节占 8 位（bit）

3、一个引用需要 8 个字节表示，例如：

//date 这个变量需要占用 8 个字节来表示
Date date = new Date();

4、创建一个对象，例如：new Date() ，除了 Date 对象内部存储的数据（年月日）占用的内存，该对象本身也有内存开销，每个对象本身开销是 16 个字节，用来保存对象的头信息

5、一般内存的使用，如果不够 8 个字节，都会被自动填充位 8 字节，如下例子：

public class A{
  public int a = 1;
}

//通过 new A() 创建一个对象的内存：
//1、整型成员变量 a 占用 4 个字节
//2、对象本身占用 16 个字节
//那么创建该对象总共需要 20 个字节，但由于不是 8 的倍数，会自动填充变为 24 个字节
new A();

6、Java 中数组被限定位对象，他们一般都会因为记录长度而需要额外的内存，一个原始数据类型的数组一般需要 24 字节的头信息（16 个自己的对象开销，4 字节用于保存长度以及4个填充字节），在加上保存值所需的内存。

2.2、算法的空间复杂度

了解了 Java 内存最基本的机制，就能够有效帮助我们估计最大量程序的内存使用情况。

算法的空间复杂度公式记为：S(n)=O(f(n)) ，其中 n 为输入规模，f(n) 为语句关于 n 所占存储空间的函数

案例：对指定数组元素进行反转，被返回反转的内容

public class Client {
    public static int[] reverse(int[] arr){
        int n = arr.length;//申请 4 个字节
        int temp;////申请 4 个字节
        for(int start = 0,end = n - 1; start <= end; start++,end--){
            temp = arr[start];
            arr[start] = arr[end];
            arr[end] = temp;
        }
        return arr;
    }
}

忽略判断条件占用内存，我们得出的内存占用情况如下：

不管传入的数组大小为多少，始终额外申请 4 + 4 = 8 个字节；

根据大O表示法，该算法的空间复杂度为 O(1)

三、总结

本篇文章我们介绍了：

1、时间复杂度和空间复杂度计算，采用大 O 表示法

2、大 O 表示法使用规则介绍

3、常见的大 O 阶

4、Java 内存最基本的机制

5、编写了一些实际的例子并计算时间复杂度和空间复杂度

好了，本篇文章到这里就结束了，感谢你的阅读🤝