1.说说你不知道的时间复杂度

发布于 2022年 01月 29日 01:17

一、为什么要学习数据结构和算法

其实,以前我们都会说,学习数据结构有多么多么的重要,长篇大论。这次,我们java程序员来看看数据结构和算法重要性。

例题:判断一个数是否是2的n次方。比如:2,4,8,16是2的n次方;6,10不是。

拿到这道题,用java的思路分析

2:2

4:2*2

8:2 * 2 * 2

16:2 * 2 * 2 * 2

如果一个数除以2,最后余数是0,那么这个数就是2的n次方;如果余数是1,那么就不是。代码实现如下:

public static void main(String[] args) {
				// 随意给一个数,判断这个数是不是2的n次方
        int n = 16;
  
        int yuShu = n%2;
        int chuShu = n/2;
        while (chuShu > 1) {
            yuShu = chuShu % 2;
            chuShu = chuShu / 2;
        }

        System.out.println( n + " 这个数" + (yuShu == 0?"是":"不是")+"2的n次方");

    }

但是,如果使用数据结构呢?下面来分析一下:将所有的十进制数字都转成2进制

2:10

4:100

8:1000

16:10000

他们的特点是什么呢?第一个数字是1,其余的都是0

而这几个数字之前的一个数字是什么呢?

1:01

3:011

7:0111

15:01111

他们的特点是什么呢?第一个是0,其余的都是1.

利用这两组数字,我们找规律,如果i和i-1按位&与的结果是0,就说明这个i是2的n次方;否则就不是

2 & 1 = 0

4 & 3 = 0

8 & 7 = 0

16 & 15 = 0

但是15 & 14呢,14的二进制数是01110,01111 & 01110 = 00001

所以,通过对数据的分析,我们可以用一句代码判断

if(n & (n=1) == 0) {
  // 这个数就是2的n次方
} else {
  // 否则不是
}

二、数据结构概述

数据结构包括:线性结构和非线性结构

1、线性结构

1)线性结构是最常用的数据结构,其特点是数据元素之间存在一对一的线性关系。

2)线性结构有两种不同的存储结构,即顺序存储结构和链式存储结构。顺序存储的线性表成为顺序表,顺序表中的存储元素是连续的

3)链式存储的线性表成为链表,链表中的存储元素不一定是连续的,元素节点中存放数据元素以及相邻元素的地址信息。

4)线性结构常见的有:数组、队列、链表和栈,后面我们会详细讲解

2、非线性结构

非线性结构包括:二维数组、多维数组、广义表、树结构、图结构

三、算法

算法有五个特征:有穷性,确定性,可行性,有输入,有输出

正确性,可读性,健壮性,bug(写出的代码bug少,而且系统稳定)

高效率与低存储:内存+CPU 堆栈内存 OOM

内存占用最小,CPU占用最小,运算速度最快。

评价算法的两个重要指标:时间复杂度 和 空间复杂度

时间复杂度:运行一个程序所花费的时间。

空间复杂度:运行程序所需要的内存。

1、 时间复杂度

1) 计算时间复杂度的意义:分析接口的性能

2) 时间复杂度表示方法:大写的O(n)表示,全称是O(nlogn)

3)常见的时间复杂度

计算时间复杂度,通常是计算比较大的,而且是不确定的的数。如果是已经确定的,那么就不用计算了,常量就是我们说的不用计算的一种。

> 常数:O(1) 1表示的是常数。不是循环的次数

比如下面的这个循环,时间复杂度是O(1)

public class BigO {

    public static void main(String[] args) {
        int n = 0; // 这句话的时间复杂度是O(1)
        
        for (int i = 0; i < 3; i++) {  // 这句话会执行4次, 它的时间复杂度也是O(1)
            n = n + 1;  // 这句话会执行3次, 他的时间复杂度也是O(1)
        }
    }
}

> 对数:O(logn) 或 O(nlogn)

那么什么情况下会使用时间复杂度是对数的这种情况呢?来看一下下面的代码:

public static void time_log() {
        int a = Integer.MAX_VALUE;
        int i = 1;
        while (i <= a) {
            i = i * 2;  // 这个循环一共要循环多少次呢?
            // 我们来看看i的值2,4,8,16,32,64,128    2^0,2^1,2^2,2^3,2^4,2^5 ====> 2(n) = a ===> n = log2a
        }
    }

这里i = i * 2 这句话需要循环多少次呢?其实我们要求的就是:循环多少次,i<= a 呢?2^n = a ; 求n=log2a, log以2为底a的对数。

以上是O(logn)的情况,那么什么情况下使用O(nlogn)呢?看下面的代码:

public static void time_nlogn() {
        int a = Integer.MAX_VALUE;
        int i = 1;
        for (int j = 0; j < 10; j++) {
            while (i <= a) {
                i = i * 2;  // 这个循环一共要循环多少次呢?
                // 我们来看看i的值2,4,8,16,32,64,128    2(1),2(2),2(3),2(4),2(5)  2(n) = a ===> n = log2a
                // 外面还有个j,所以就是(j * log2a)次
            }
        }  
    }

只有while循环的时候,需要执行log2a次。那么外面多了一层for循环,这次要循环多少次呢?(j * log2a)次

> 线性:O(n)

线性指的就是O(n),也就是运行n次。

public static void time_on() {
        int n = Integer.MAX_VALUE;
        int a = 0;
        for (int i = 0; i < n; i++) {
            a = a + 1; // 这句话的时间复杂度是什么? O(n) n是几就运行几次. n是未知的,不确定的.如果n是确定的,就是常量了. 时间复杂度就是O(1)
        }
    }

这里面a = a + 1;这句话会运行多少次呢?他和n有关系,如果n是10就运行10次,n是100就运行100次。有n决定,所以时间复杂度是O(n);

注意:这里的n是不确定的。如果n是确定的,那么时间复杂度就是O(1)le

> 线性对数:O(nlogn)

这个在上面已经说过了

> 平方:O(n ^ 2)

/**
     * 时间复杂度O(n^2)
     */
    public static void time_Onn() {
        int n = Integer.MAX_VALUE;
        int a = 0;
        for(int i = 0; i < n; i++) {
            for (int j = 0; j< n; j++) {
                a = a + 1; // 这句话执行多少次呢?也就是说它的时间复杂度是多少呢? 外层循环执行n次,内层循环也是n次,所以最终执行n*n次,所以时间复杂度是O(n^2)
            }
        }
    }

这里有两层循环,外层循环执行n次,内存循环也是n次,所以代码a = a + 1;执行O(n*n)次。

常见的O(n^2)还有冒泡排序

public static void time_Onn2() {
        int[] num = {3,6,1,0,8,5};
        int n = num.length;

        int a = 0;
        for(int i = 0; i < n; i++) {
            for (int j = i; j < n; j++) {
                a = a + 1; // 这句话执行多少次呢?也就是说它的时间复杂度是多少呢? 来找找它的规律
                /*
                 * 外层循环i=n, 内层代码执行1次
                 * 外层循环i=n-1,内层代码执行2次
                 * 外层循环i=n-2,内层代码执行3次
                 * 外层循环i=n-3,内层代码执行4次
                 * 外层循环i=1,内层代码执行n次
                 * 
                 * 一共执行多少次呢? 0+1+2+3+......+n = n * (n+1)/2次
                 * 也就是冒泡算法的时间复杂度是O(n*(n+1)/2)次
                 */
            }
        }
    }

冒泡排序的时间复杂度是多少呢?我们来分析一下:

外层循环i=n, 内层代码执行1次
外层循环i=n-1,内层代码执行2次
外层循环i=n-2,内层代码执行3次
外层循环i=n-3,内层代码执行4次
外层循环i=1,内层代码执行n次

一共执行多少次呢? 0+1+2+3+......+n = n * (n+1)/2次
也就是冒泡算法的时间复杂度是O(n*(n+1)/2)次。

在计算时间复杂度的时候去掉常数,所以就是O(n^2)

> N次方:

如果是三层循环,四层循环呢?那就是 n * n * n * n=n^4

上面的冒泡算法会执行n*(n+1)/2 = (n^2 + n)/2 ===>当有加减法的时候,这个时间复杂度怎么计算呢?

取最大的就可以,这个最大是:首先去掉常数后,n2比n的阶层高,所以最后是O(n2)

4) 怎么计算时间复杂度?

第一步:找有循环的地方

第二步:找有网络请求的地方,包括RPC协议请求,数据库请求

​ 网络请求可以通过打印日志来计算时间。

5) 常见时间复杂度的运行效率

O(1) > O(logn) > O(n) > O(nlogn) > O(n^2) > O(n^x)

O(1)的运行效率是最高的。

所以,我们在优化的时候,目标是将所有的时间复杂度往O(1)进行优化。

实际上,O(1) > O(logn) > O(n) > O(nlogn) 效果都是很好的,几乎优化的空间不是很大。我们的最终目标就是将O(n^2) 和 O(n^x)往前优化。

  • 案例1:

再来看看最开始的这个案例:判断一个数是否是2的n次方。比如:2,4,8,16是2的n次方;6,10不是。

如果一个数除以2,最后余数是0,那么这个数就是2的n次方;如果余数是1,那么就不是。代码实现如下:

public static void main(String[] args) {
				// 随意给一个数,判断这个数是不是2的n次方
        int n = 16;
  
        int yuShu = n%2;
        int chuShu = n/2;
        while (chuShu > 1) {
            yuShu = chuShu % 2;
            chuShu = chuShu / 2;
        }

        System.out.println( n + " 这个数" + (yuShu == 0?"是":"不是")+"2的n次方");

    }

那么这段代码的时间复杂度是多少呢?log2n:log以2位底n的对数。O(logn)

后来通过二进制代码进行优化,优化后的结果是

if(n & (n=1) == 0) {
  // 这个数就是2的n次方
} else {
  // 否则不是
}

这段代码的时间复杂度是O(1)。

我们优化以后,将O(logn)优化为O(1)了,效率大大提高了

  • 案例2

比如,我们在看一段代码的时候,发现有性能瓶颈,然后这段代码使用的排序方式是冒泡排序,如何对这个排序进行优化呢?

找更优秀的替代排序方法,快速排序,归并排序,堆排序等。

2、空间复杂度

1)空间复杂度分析的意义

找出哪些地方花费内存多,哪些数据占用的内存开销大

2)如何找出程序的空间复杂度?

开空间的地方,比如:数组,链表,缓存Map,Set,队列Queue,递归等

数据结构和算法书籍推荐

推荐文章