盐析白兔

这个屌丝很懒，什么也没留下！

热门标签

[数据结构基础]时间复杂度和空间复杂度详解_时间复杂度和空间复杂度的概念

作者：盐析白兔 | 2024-07-24 23:19:39

踩

时间复杂度和空间复杂度的概念

一. 预备知识

1.1 什么是数据结构

数据结构是指计算机中存储、组织数据的方式，指相互之间存在的一种或多种特定关系的数据元素的集合。

1.2 什么是算法

算法，就是定义良好的计算过程，它取一个或一组的值作为输入，并产生一个或一组的值作为输出。简单来说，算法就是一系列计算步骤，用于将数据转化为输出。

1.3 算法效率的衡量

可以从两个角度衡量一个算法的效率（时间复杂度和空间复杂度）：

时间复杂度：用于衡量一个算法运行的快慢
空间复杂度：用于衡量一个算法运行所需要的额外内存空间

由于现代计算机内存的不断扩大，人们对空间复杂度的关注越来越少。但是，对效率的极致追求一直是良好计算机程序的目标。因此，一般而言时间复杂度的重要性要高于空间复杂度。

二. 时间复杂度

2.1 时间复杂度概念

时间复杂度是一个函数，用于衡量算法的运行时间。注意：时间复杂度并不是执行这个算法所用的具体时间（秒、毫秒等为单位），而是算法中基本操作执行的次数。

下面来看一个案例：嵌套循环的时间复杂度分析

如图2.1所示的代码，选取count++为基本操作，代码中定义了一个嵌套for循环，执行基本操作 $n^{2}$ 次、一个单层for循环，执行基本操作次，一个while循环，执行基本操作 M=10 次。时间复杂度是算法执行基本操作的次数，因此，图2.1展示的代码的时间复杂度表达式可写为：

$F(N)=N^2+2 \times N+10$

2.2 大O渐进法

在实际计算时间复杂度时，我们并不一定要计算基本操作的精确执行次数，只要算出大概的执行次数即可，那么这是就需要使用大O渐进法。（只保留对结果影响最大的项）

大O渐进法推导原则：

用1来替代基本操作执行次数中所有加法项常数。
在修改后的基本操作执行次数表达式中，只保留阶数最高的项。
如果阶数最高的项的系数不为1，则去除这个系数用1来替代。

图2.1中展示的算法的精确时间复杂度表达式为： F(N)=N^2+N+10 ，最高项为 N^2 ，系数为1，因此用大O渐进法表示为： O(N^2)

2.3 典型算法的时间复杂度分析

2.3.1 字符查找函数strchr的时间复杂度分析

图2.2中展示了字符查找函数strchr的实现代码，可以从最乐观、平均、最差三个层面来分析strchr的时间复杂度。最乐观情况，即待查找字符串的首字符就是要被查找的字符，此时基本操作执行次数为1、最差的情况，即查找到字符串的最后一个字符才发现要被查找的字符或根本没找到这个字符，此时执行基本操作的次数为N、平均情况可认为是最坏和最乐观情况下基本操作执行次数的平均值，即(N+1)/2。

注意：一般而言，对于一个随着输入不同而时间复杂度不同的算法，时间复杂度做最悲观的预期，即看基本操作执行次数最多的情况。

2.3.2 二分查找函数b_search的时间复杂度分析

图2.3展示了对于升序整型数组的二分查找函数代码。每次查找将数据查找范围缩减一半，最坏的情况为最后一个查找的数组元素为目标查找数字或找不到。为了分析b_serach函数的时间复杂度，可以进行反推，假设第N次查找完成对所有数组元素的查找，那么第N-1次查找完成后剩1个数组元素，第N-2次查找完成后剩2个数组元素，第N-3次查找完成后剩4个数组元素，...，第1次查找完成后剩一半数组元素，具体可参考图2.4。取每次查找为一次基本操作，数组中含有num个元素，可列出等式等式： 2^N = num ，基本操作执行次数N为： $log_{2}(num)$ 。

用大O渐进法表示b_search的时间复杂度位： $O(log_{2}N)$

2.3.3 递归方法计算N的阶乘时间复杂度分析

图2.5为通过递归调用计算N的阶乘的函数，递归调用的时间复杂度 = 递归次数 × 每次递归函数被调用的次数。N的阶乘计算函数递归调用了N次，每次递归调用了一次函数，时间复杂度为 O(N)

2.3.5 递归方法计算斐波那契数列函数的时间复杂度

图2.6展示了斐波那契数列计算函数及时间复杂度分析图解，每次递归调用函数2次，每层递归从上往下依次调用函数 2^0 、 2^1 、 2^2 、...、 $2^{n-1}$ 次，由于N<2时函数返回0，因此右边的一些分支会提前结束。因此时间复杂度的精确表达式为： $F(N)=2^0+2^1+...+2^{N-1}-X$ ，即 F(N)=2^N-1-X ，用大O渐近法表示为： O(2^N) 。

综上可知：计算时间复杂度不能只看几层循环，要看程序的思想。

三. 空间复杂度

3.1 空间复杂度概念

空间复杂度与时间复杂度类似，也是一个数学函数表达式，是对一个算法在运行时临时占用的额外内存空间的度量。空间复杂度不是指程序占用多少byte的内存空间，而是临时创建的局部变量个数。

注意：如果一个算法中要调用其他函数，那么，调用函数创建的栈帧也要计入空间复杂度。

空间复杂度也遵循大O渐进法。

3.2 典型算法的空间复杂度分析

3.2.1 递归方法计算N的阶乘空间复杂度分析

函数递归N次，每次创建一个栈帧，函数不创建临时变量，空间复杂度 O(N)

3.2.1 递归方法计算斐波那契数列的空间复杂度分析

按照之前分析时间复杂度的方法，我们或许会认为这个算法的空间复杂度也是 O(2^N) ，但是，这个算法的实际空间复杂度为 O(N) ，因为这个算法在创建函数栈帧的过程中会重复利用内存空间。

在调用函数的过程中会从左向右依次计算每个分支，每个分支计算完成后，销毁为计算这个分支而创建的函数栈帧，并将这块空间重新用于存储下一条分支计算过程中创建的栈帧。计算最左侧分支： Fib(N) --> Fib(N-1) --> Fib(N-2) --> ... --> Fib(2) --> Fib(1) 时创建的栈帧最多，创建个函数栈帧。因此，该算法的空间复杂度为： O(N)

四. 常见的时间/空间复杂度效率对比

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/盐析白兔/article/detail/877140