时间复杂度和空间复杂度计算方式

墨蓝 2024-03-27 18:22 90阅读 0赞

**-** **复杂度分析** **-**

数据结构与算法经常是放在一起讲，这两者是没办法独立的，因为算法是为了达到某种目的的一种实现方式，而数据结构是一种载体，也就是说算法必须依赖数据结构这种载体，否则就是空谈。换句话说：数据结构是为算法服务的，而算法又需要作用在特定的数据结构之上。

一个算法到底好不好，我们如何去评价？前面我们提到了，你的代码好不好，最直观的就是看响应速度，算法也一样，同样实现一个目的（比如说排序），谁的算法速度快，我们就可以认为谁的算法更优，如果说两种算法实现的速度差不多，那么我们还可以去评价算法所占用的空间，谁占用的空间少，那么就可以认为谁的算法更优，这就是算法的基础：时间复杂度和空间复杂度。

学习算法之前，我们必须要学会如何分析时间复杂度和空间复杂度（也就是“快”和“省”），否则自己写出来的算法自己都不知道算法的效率。

### 时间复杂度大 O表示法 ###

接触过算法的都知道，算法的时间复杂度是用大写的“O”来表示的，比如：`O(1)`，`O(n)`，`O(logn)`，`O(nlogn)`，`O(n²)` 等等。

时间复杂度的全称是渐进时间复杂度，表示算法的执行时间与数据规模之间的增长关系，上面的这种时间复杂度表示法并不能真正反应一个算法的执行时间，反应的只是一个趋势，所以我们在分析复杂度的时候要关注“变”，忽略“不变”。

变指的是变量，也就是一段代码的执行时间是随着变量的变化而变化的，而不变指的是常量，也就是不论我的变量如何改变，执行时间都不会改变。

接下来我们就实际的来分析下常用时间复杂度的例子来练习一下。

#### O(1) 常数阶 ####

0(1) 复杂度算法也称之为常数阶算法。这里的 `1` 是用来代指常量，也就是说这个算法的效率是固定的，无论你的数据量如何变化，效率都一样，这种复杂度也是最优的一种算法。

public static void print(int n){
        int a = 1;
        int b = 2;
        int c = 3;
        int sum = a + b + c;
        System.out.println(sum);
    }

上面的示例中不论有多少行代码，时间复杂度都是属于常数阶。换言之：只要代码不存在**循环**，**递归**等循环类调用，不论代码有多少行，其复杂度都是常数阶。

#### O(n) 线性阶 ####

`O(n)` 复杂度算法也称之为线性阶。比如下面这个示例我们应该怎么分析复杂度呢？

public static void print1(int n){
        int a = 0;
        for (int i=0;i<n;i++){
            System.out.println(i);
        }
    }

前面常量阶没分析是因为常量阶比较容易理解，接下来我们就以线性阶这个为例子来分析下具体是怎么得到的。

我们假设每一行代码的执行时间是 `T`，那么上面这段代码的执行复杂度是多少呢？

答案很明显，那就是 `T+n*T`，也就是 `(n+1)T`，而在算法中有一个原则，那就是常量可以被忽略，所以就得到了 `nT`，换成大 `O` 表示法就是 `O(n)`。

这只是一个简略的计算过程，大家也不用较真说每行代码执行时间可能不一样之类的，也不要较真说 `for` 循环占用了一行，下面的大括号也占用了一行，如果要较真这个，那我建议可以去想一下 `1=1` 为什么等于 `2`。

算法中的复杂度反应的只是一个趋势，这里 `O(n)` 反应的就是一个趋势，也就是随着 `n` 的变化，算法的执行时间是会降低的。

#### O(n²) 平方阶 ####

知道了上面的线性阶，那么平方阶就很好理解了，双层循环就是平方阶，同理，三次循环就是立方阶，`k` 次循环就是 `k` 次方阶。

#### O(logn) 对数阶 ####

`O(logn)` 也称之为对数阶，对数阶也很常见，像二分查找，二叉树之类的问题中会见到比较多的对数阶复杂度，但是对数阶也是比较难理解的一种算法复杂度。

下面我们还是来看一个例子：

public static void print2(int n){
        int i=1;
        while (i <= n) {
            i = i * 2;
        }
    }

这段代码又该如何分析复杂度呢？这段代码最关键就是要分析出 `while` 循环中到底循环了多少次，我们观察这个循环，发现 `i` 并不是逐一递增，而是不断的翻倍：`1->2->4->8->16->32->64` 一直到等于 `n` 为止才会结束，所以我们得到了这样的一个公式：`2^x=n`。

也就是我们只要计算出 `x` 的值，就得到了循环次数，而根据高中的数学知识我们可以得到 `x=log2n`（`2` 在下面，是底数，试了几种方法都打不出来，放弃了），所以根据上面线性阶的分析方法，我们省略常量，就得到了示例中的算法复杂度为 `O(log2n)`。

同样的分析方式，下面的例子，我们可以很快的分析出复杂度就为 `O(log3n)`：

int i=1;
    while (i <= n) {
        i = i * 3;
    }

上面得到的 `log3n` 我们可以再做进一步的转换：`log3n=log32 * log2n`，而 `log32`（注意这几个地方的 `3` 是底数，在下面） 是一个常量，常量可以省略，所以也就得到了：`O(log3n)=O(log2n)`。同样的道理，不论底数是多少，其实最终都可以转化成和 `O(log2n)` 相等，正因为如此，为了方便，我们算法中通常就会省略底数，直接写作 `O(logn)`。

上面的数学公式大家如果忘了或者看不懂也没关系，只要记住不论对数的底数是多少，我们都算作 `O(logn)`，而对于一个算法的复杂度是否是对数阶，还有一个简易的判断方法：**当循环中下标以指定倍数形式衰减，那么这就是一个对数阶**。

#### O(nlogn) 线性对数阶 ####

如果理解了上面的对数阶，那么这种线性对数阶就非常好理解了，只需要在对数阶的算法中再嵌一层循环就是线性对数阶：

int i=1;
    for (int j=1;j<=n;j++){
        while (i <= n) {
            i = i * 2;
        }
    }

分析了前面这些最常用的时间复杂度，其实我们可以得到以下规律：

*  只要是常量级别，不论多大，效率都是一样的（如：常量阶复杂度例子）。
 *  分析一段代码的时间复杂度，只需要分析执行次数最多的一段代码（如：所以例子中我们只分析了循环体中代码执行次数）。
 *  嵌套代码的复杂度等于嵌套内外代码复杂度的乘积（如：分析线性对数阶复杂度例子）。

#### 其他复杂度 ####

除了上面常用的复杂度之外，另外还有指数阶，阶层阶，根号阶等，这些接触的相对会较少，我们就不特意做分析了，如果大家感兴趣的话，可以自己去了解下。

#### 组合式复杂度分析 ####

前面我们分析的都是只有一段代码比较复杂的情况下得到的复杂度结果，那么假如我一个算法中，有多段代码都比较复杂呢？这时候复杂度该如何分析？

##### 取最大复杂度作为整个算法复杂度 #####

我们先看下面这个例子：

public static void print1(int n){
        for (int i=0;i<1000;i++){
            System.out.println(i);
        }
        for (int j=0;j<n;j++){
            System.out.println(j);
        }
    
        for (int p=0;p<n;p++){
            for (int q=0;q<n;q++){
                System.out.println(p+q);
            }
        }
    }

这个例子中有三个循环，首先第一个，是一个常量，那么根据前面的结论，不论这个常量是多大，都属于常量级，所以第一个循环中的复杂度为 `O(1)`，第二个和第三个循环我们前面也分析过，复杂度分别为 `O(n)` 和 `O(n²)`。

也就是这一段代码中有三段代码产生了三种不同复杂度，而且这三个复杂度可以很明显得到的大小关系为：`O(1)<O(n)<O(n²)`，像这种在同一个算法中有明确大小关系的，我们就可以直接取最大值作为这个算法的复杂度，所以这个例子中算法的复杂度就是 `O(n²)`。

##### 取多个复杂度之和作为整个算法复杂度 #####

接下来我们再来看一个例子：

public static void print2(int m,int n){
        for (int i=0;i<1000;i++){
            System.out.println(i);
        }
        for (int j=0;j<m;j++){
            System.out.println(j);
        }
        for (int k=0;k<n;k++){
            System.out.println(k);
        }
    }

这个例子我们同样对三段循环分别分析可以分别得到如下复杂度：`O(1)`，`O(m)`，`O(n)`。这时候我们只能知道 `O(1)` 最小可以忽略，但是后面两个无法却无法确定大小，所以这时候我们需要取两段循环复杂度之和来作为算法的复杂度，所以可以得到这个例子的算法复杂度为：`O(m+n)`。

### 时间复杂度类型 ###

上面分析的时间复杂度都是比较简单的，实际算法中可能会比示例中复杂的多，而且我们示例中只要是循环都是无脑循环，也就是一定从头循环到尾，然而实际中我们有时候并不需要从头循环到尾，可能中途就会结束循环，所以我们根据实际情况，又可以将时间复杂度从以下四个方面来进一步分析：

*  最好时间复杂度
 *  最坏时间复杂度
 *  平均时间复杂度
 *  均摊时间复杂度

这四种类型的时间复杂度在这里只会介绍前面三种，因为第四种比较复杂，而且使用场景也非常有限，而且对于这四种复杂度的分析，大家也作为了解就可以，不敢兴趣的朋友们可以跳过这一小部分，因为在绝大部分情况我们只需要分析最坏复杂度就行，也就是假设循环全部执行完毕场景下的时间复杂度。

#### 最好时间复杂度 ####

我们通过一个例子来理解下最好时间复杂度：

public static int findEle(int[] arr,int val){
            if (null == arr || arr.length == 0){
                return -1;
            }
           for (int i=0;i<arr.length;i++){
               if (arr[i] == val){
                   return i;
               }
           }
           return -1;
        }

这个方法就是在一个指定数组中找到指定元素的下标，找不到就返回 `-1`，这个方法比较简单，应该比较好理解。

注意这个方法中的循环体，如果找到元素，那么就直接返回，这就会有一个现象，那就是我这个循环体到底会循环多少次是不确定的，可能是 `1` 次，也可能是 `n`（假设数组的长度） 次，所以假如我们要找的元素就在数组中的第一个位置，那么我循环一次就找到了，这个算法的复杂度就是 `O(1)`，这就是最好情况时间复杂度。

#### 最坏时间复杂度 ####

理解了最好时间复杂度，那么最坏时间复杂度也很好理解了，那就是数组中不存在我要找到元素，或者说最后一个值才是我要找的元素，那么这样我就必须循环完整个数组，那么时间复杂度就是 `O(n)`，这也就是最坏时间复杂度。

#### 平均时间复杂度 ####

最好时间复杂度和最坏时间复杂度毕竟只有特殊情况才会发生，概率还是相对较小，所以我们很容易就想到我们也需要有一个平均时间复杂度。

我们简单的来分析一下，为了便于分析，我们假设一个元素在数组和不在数组中的概率都为 `1/2`，然后假如在数组在，那么又假设元素出现在每个位置的概率也是一样的，也就是每个位置出现元素的概率为： `1/n`。

所以最终得到的平均时间复杂度应该等于元素在数组中和元素不在数组中两种情况相加。

*  元素在数组中的复杂度

因为元素在数组中的概率为 `1/2`，然后在每个位置出现的概率也为 `1/n`。假如元素出现在第一个位置，复杂度为 `1*(1/2n)`；假如元素出现在第二个位置，复杂度为 `2 * (1/2n)`，最终得到当前场景下时间复杂度为：`1*(1/2n) + 2 * (1/2n) + ... + n*(1/2n)`=(n+1)/4。

*  元素不在数组中的复杂度

前面已经假定了元素不在数组中的概率为 `1/2`，所以当前场景下的时间复杂度为：`n * (1/2)`，因为元素不在数组中，那么这个算法必然会将整个循环执行完毕，也就循环是 `n` 次。

最后我们把两种情况的复杂度之和相加就得到了平均时间复杂度：`(n+1)/4 + n/2 = (3n+1)/4`，最终我们将常数类的系数忽略掉，就得到了平均时间复杂度为 `O(n)`。

#### 均摊时间复杂度 ####

均摊时间复杂度的算法需要使用摊还分析法，计算方式相对有点复杂，而且使用场景很有限，本文就不做过多介绍了。

### 空间复杂度 ###

空间复杂度全称就是渐进空间复杂度，用来表示算法的存储空间与数据规模之间的增长关系。和时间复杂度一样，空间复杂度也是用大 `O` 进行表示。

其实学会了分析时间复杂度，那么空间复杂度的分析就简单了，主要就看我们在一个算法当中到底有没有使用到了额外的空间来进行存储数据，然后判断这个额外空间的大小会不会随着 `n` 的变化而变化，从而得到空间复杂度。

我们来看一个给数组赋值例子，假设这就是一个算法，我们可以来分析下这个算法的空间复杂度：

public static void init(int n){
        int a = 0;
        int arr[] = new int[n];
        for (int i=0;i<n;i++){
            arr[i]=n;
        }
    }

一开始定义了一个变量，这里需要空间，但是这是一个常量级的（不随 `n` 的变化而变化），然后再定义了一个数组，数组的长度为 `n`，这里数组也需要占用空间，而且数组的空间是随着 `n` 的变化而变化的，其余代码没有占用额外空间，所以我们就可以认为上面示例中的空间复杂度为 `O(n)`。

对于算法的空间复杂度也可以简单的进行总结一下：

*  如果申请的是有限个数（常量）的变量，空间复杂度为 `O(1)`。
 *  如果申请的是一维数组，队列或者链表等，那么空间复杂度为 `O(n)`。
 *  如果申请的是二维数组，那么空间复杂度为 `O(n²)`。
 *  如果是在循环体中申请的数组等，可能就需要取嵌套的乘积来作为空间复杂度，这种就需要具体的进一步分析。

##  ##

![图片][de183b2a5e42c6eb35160dbc5c322b5f.png]

**-** **总结** **-**

本文主要讲述了为什么要学习算法，也简单减少了数据结构与算法之间的关系，随后主要介绍了算法中的入门知识：时间复杂度和空间复杂度。想要学好算法，必须要掌握如何分析一个算法的时间复杂度和空间复杂度，只有自己会分析这两个个衡量算法主要性能的标准，才能更好的写出性能优秀的算法，同时我们也讲到了最好时间复杂度，最坏时间复杂度，平均时间复杂度和均摊时间复杂度，不过这四种复杂度的计算方式大家作为了解即可，等实际确实需要使用到再来回顾也不迟。

[de183b2a5e42c6eb35160dbc5c322b5f.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/11/28c97375dc1b4fb780bc489ee542e103.png