空间复杂度和时间复杂度

朴灿烈づ我的快乐病毒、 2024-04-23 15:58 99阅读 0赞

>  *  ?**作** **者**：[是江迪呀][Link 1]
>  *  ✒️**本文关键词**：`时间复杂度`、`空间复杂度`、`算法`
>  *  ☀️**每日 一言**：`车到山前必有路，船到码头自然直！`

#### 文章目录 ####

*  一、前言
 *  二、时间杂度
 *   *  2.1.时间复杂度
     *   *  （1）时间频度
         *  （2）时间复杂度
         *  （3） 求解算法的时间复杂度的具体步骤是：
         *  （4）在计算算法时间复杂度时有几个简单的程序分析法则：
         *  （5）测试
 *  三 、空间复杂度
 *   *  3.1 算法的输入输出数据所占用的存储空间：
     *  3.2 存储算法本身所占用的存储空间：
     *  3.3 算法在运行过程中临时占用的存储空间：

![在这里插入图片描述][78c1c0b7757d4da48388aafa7cc7851d.png_pic_center]

## 一、前言 ##

时间复杂度和空间复杂度是算法和数据结构领域中两个重要的概念，它们评估了一个算法在时间和内存资源上的消耗。这两个概念是分析和设计算法时必不可少的工具，对于解决计算问题的效率至关重要。

## 二、时间杂度 ##

在给定一个算法，首先要分析两项：  
**（1）第一项：** 数学上证明算法的正确性。  
**（2）第二项：** 在算法正确的基础之上，分析算法的时间复杂度，算法时间复杂度反应了程序执行时间随输入规模增长增长的量级。时间复杂度，很大程度上反应了算法的优劣。

### 2.1.时间复杂度 ###

一个算法的是由控制结构（顺序、分支和循环三种）和原操作（指固有数据类型的操作）构成的。则算法时间取决于两者的综合效果。为了方便比较同一个问题的不同算法，通用的做法是，从算法选取一种对于所研究的问题（或算法类型）来说是基本操作的原操作，以该基本操作的重复执行次数作为算法的**时间量度**。

#### （1）时间频度 ####

要想算出一个算法执行的时间，必须要上机测试，但是没有这个必要。因为一个算法花费的时间与算法中语句的执行次数成正比的关系，所**以哪个算法中语句执行的次数多，它花费的时间就越多**。这个算法中语句执行的次数被称为语句频度或者时间频度，记作`T(n)`。

#### （2）时间复杂度 ####

在上述的时间频度中，`n`称为**问题的规模**，当`n`发生变化时，时间频度也会发生变化。为了表示`T(n)`随`n`变化而变化的规律，因此引入时间复杂度概念。**总结：时间复杂度是用来表示 时间频度`T(n)`随问题规模`n`变化而变化的规律。**

一般情况下，算法中基本操作重复执行的次数是问题规模`n`的某个函数，用`T(n)`表示，若有某个辅助函数`f(n)`，使得当`n`趋近于无穷大的时候，`T(n)/f(n)`的极限值为不等于零的常数，则称`f(n)`是`T(n)`的**同量级函数**。记作`T(n) = O(f(n))`（注：Landau符号的作用是用简单的函数描述复杂的函数行为，给出一个上或下（确）界）。称O(f(n))为算法的渐进时间复杂度，简称时间复杂度。

`T (n) = Ο(f (n))`表示存在一个常数`C`，使得在当`n`趋于正无穷时总有 `T (n) ≤ C * f(n)`。简单来说，就是`T(n)`在`n`趋于正无穷时最大也就跟`f(n)`差不多大。也就是说当`n`趋于正无穷时`T (n)`的上界是`C * f(n)`。其虽然对`f(n)`没有规定，但是一般都是取尽可能简单的函数。例如，`O(2n2+n +1) = O (3n2+n+3) = O (7n2 + n) = O ( n2 )`，一般都只用`O(n2)`表示就可以了。注意到大`O`符号里隐藏着一个常数`C`，所以`f(n)`里一般不加系数。如果把T(n)当做一棵树，那么O(f(n))所表达的就是树干，只关心其中的主干，其他的细枝末节全都抛弃不管。

在各种不同的算法中，若 算法中语句执行的次数为一个常数，则时间复杂度为O(1)。另外，在时间频度不同的情况下，时间复杂度有可能相同，比如`T(n)=n2+3n+4与T(n)=4n2+2n+1`它们的频度不同，但时间复杂度相同，都为`O(n2)`。常见的时间复杂度有：常数阶`O(1)`，对数阶`O(log2n)`，线性阶`O(n)`， 线性对数阶`O(nlog2n)`，平方阶`O(n2)`，立方阶`O(n3)……`， `k`次方阶`O(nk)`，指数阶`O(2n)`。随着问题规模`n`的不断增大，上述时间复杂度不断增大，算法的执行效率越低。  
![在这里插入图片描述][51f00c37f00745f9a044367d14fb0609.png]

常见的算法时间复杂度由小到大依次为：`Ο(1)＜Ο(log2n)＜Ο(n)＜Ο(nlog2n)＜Ο(n2)＜Ο(n3)＜…＜Ο(2n)＜Ο(n!)`

#### （3） 求解算法的时间复杂度的具体步骤是： ####

*  找出算法中的基本语句。算法中执行次数最多的那个就是基本语句，通常是最内层循环的循环体。
 *  计算基本语法的执行次数的数量级。只需计算基本语句执行次数的数量级，这就意味着只要保证基本语句执行次数的函数中的最高次幂正确即可，可以忽略所有低次幂和最高次幂的系数。这样能够简化算法分析，并且使注意力集中在最重要的一点上：**增长率**。
 *  用大`O`记号表示算法的时间性能。将基本语句执行次数的数量级放入大`Ο`记号中。如果算法中包含嵌套的循环，则基本语句通常是最内层的循环体，如果算法中包含并列的循环，则将并列循环的时间复杂度相加。例如：

for (i=1; i<=n; i++)
         x++;
    for (i=1; i<=n; i++)
      　for (j=1; j<=n; j++)
            x++;

**解释：** 第一个for循环的时间复杂度为`Ο(n)`，第二个`for`循环的时间复杂度为1Ο(n2)1，则整个算法的时间复杂度为`Ο(n+n2)=Ο(n2)`。`Ο(1)`表示基本语句的执行次数是一个常数，一般来说，只要算法中不存在循环语句，其时间复杂度就是Ο(1)。其中`Ο(log2n)`、`Ο(n)`、 `Ο(nlog2n)`、`Ο(n2)`和`Ο(n3)`称为**多项式时间**，而`Ο(2n)`和`Ο(n!)`称为**指数时间**。

计算机科学家普遍认为前者（即多项式时间复杂度的算法）是有效算法，把这类问题称为`P`（**Polynomial，多项式**）类问题，而把后者（即指数时间复杂度的算法）称为 **NP（Non-Deterministic Polynomial ，非确定多项式）** 问题。

**疑问点：**

一般来说多项式级的复杂度是可以接受的，很多问题都有多项式级的解——也就是说，这样的问题，对于一个规模是n的输入，在`n^k`的时间内得到结果，称为P问题。有些问题要复杂些，没有多项式时间的解，但是可以在多项式时间里验证某个猜测是不是正确。比如问4294967297是不是质数？如果要直接入手的话，那么要把小于4294967297的平方根的所有素数都拿出来，看看能不能整除。还好欧拉告诉我们，这个数等于641和6700417的乘积，不是素数，很好验证的，顺便麻烦转告费马他的猜想不成立。大数分解、Hamilton回路之类的问题，都是可以多项式时间内验证一个**解**是否正确，这类问题叫做`NP`问题。

#### （4）在计算算法时间复杂度时有几个简单的程序分析法则： ####

*  对于一些简单的输入输出语句或赋值语句，近似认为需要O(1)时间。
 *  对于顺序结构，需要依次执行一系列语句所用的时间可采用大O下"求和法则"  
    求和法则:是指若算法的2个部分时间复杂度分别为`T1(n)=O(f(n))和 T2(n)=O(g(n))`，则 `T1(n)+T2(n)=O(max(f(n)， g(n)))`  
    特别地，若`T1(m)=O(f(m))`，`T2(n)=O(g(n))`则`T1(m)+T2(n)=O(f(m) + g(n))`
 *  对于选择结构，如if语句，它的主要时间耗费是在执行`then`字句或`else字`句所用的时间，需注意的是检验条件也需要`O(1)`时间
 *  对于循环结构，循环语句的运行时间主要体现在多次迭代中执行循环体以及检验循环条件的时间耗费，一般可用大O下"乘法法则"  
    乘法法则: 是指若算法的2个部分时间复杂度分别为 `T1(n)=O(f(n))和 T2(n)=O(g(n))`，则 `T1*T2=O(f(n)*g(n))`
 *  对于复杂的算法，可以将它分成几个容易估算的部分，然后利用求和法则和乘法法则技术整个算法的时间复杂度另外还有以下2个运算法则:  
    若`g(n)=O(f(n))，则O(f(n))+ O(g(n))= O(f(n))`；`O(Cf(n)) = O(f(n))`，其中C是一个正常数

#### （5）测试 ####

*  `O(1)`

Temp=i; 
    i=j; 
    j=temp;

以上三条单个语句的**频度均为1**，该程序段的执行时间是一个与问题规模`n`无关的常数。算法的时间复杂度为常数阶，记作`T(n)=O(1)`。  
**注意：如果算法的执行时间不随着问题规模`n`的增加而增长，即使算法中有上千条语句，其执行时间也不过是一个较大的常数。此类算法的时间复杂度是O(1)。**

*  `O(n2)`

sum=0；                 （一次）
      for(i=1;i<=n;i++)     （n+1次）
         for(j=1;j<=n;j++) （n2次）
          sum++；            （n2次）

**解：因为`Θ(2n2+n+1)=n2`（`Θ`即：去低阶项，去掉常数项，去掉高阶项的常参得到），所以`T(n)= =O(n2)`；**

for (i=1;i<n;i++)
        {
         
            y=y+1;         ①   
            for (j=0;j<=(2*n);j++)    
               x++;         ②      
        }

**解： 语句1的频度是`n-1`，语句2的频度是`(n-1)*(2n+1)=2n2-n-1`，`f(n)=2n2-n-1+(n-1)=2n2-2`；又`Θ(2n2-2)=n2`，该程序的时间复杂度`T(n)=O(n2)`。**

**注意：一般情况下，对不进循环语句只需考虑循环体中语句的执行次数，忽略该语句中步长加1、终值判别、控制转移等成分，当有若干个循环语句时，算法的时间复杂度是由嵌套层数最多的循环语句中最内层语句的频度`f(n)`决定的。**

*  `O(n)`

a=0;
        b=1;                      ①
        for (i=1;i<=n;i++) ②
        {
          
           s=a+b;　　　　③
           b=a;　　　　　④  
           a=s;　　　　　⑤
        }

**解： 语句1的频度：2，语句2的频度： `n`，语句3的频度：`n-1`，语句4的频度：`n-1`，语句5的频度：`n-1`， `T(n)=2+n+3(n-1)=4n-1=O(n)`**

*  `O(log2n)`

i=1;     ①
        while (i<=n)
           i=i*2; ②

**解： 语句1的频度是1设语句2的频度是`f(n)`， 则：`2^f(n)<=n;f(n)<=log2n`取最大值`f(n)=log2n`，`T(n)=O(log2n )`**

*  `O(n3)`

for(i=0;i<n;i++)
        {
          
           for(j=0;j<i;j++)  
           {
        
              for(k=0;k<j;k++)
                 x=x+2;  
           }
        }

**解：当i=m，j=k的时候，内层循环的次数为k当i=m时，j 可以取 `0、1……m-1`，所以这里最内循环共进行了`0+1+...+m-1=(m-1)m/2`次所以，`i`从`0`取到`n，` 则循环共进行了: `0+(1-1)*1/2+...+(n-1)n/2=n(n+1)(n-1)/6`所以时间复杂度为`O(n3)`。**

## 三 、空间复杂度 ##

类似于时间复杂度的讨论，一个算法的**空间复杂度**(Space Complexity)`S(n)`定义为该算法所耗费的存储空间，它也是问题规模`n`的函数。渐近空间复杂度也常常简称为空间复杂度。  
空间复杂度(Space Complexity)是对一个算法在运行过程中临时占用存储空间大小的量度。一个算法在计算机存储器上所占用的存储空间，包括存储算法本身所占用的存储空间，算法的输入输出数据所占用的存储空间和算法在运行过程中临时占用的存储空间这三个方面。

### 3.1 算法的输入输出数据所占用的存储空间： ###

它是由要解决的问题决定的，是通过参数表由调用函数传递而来的，它不随本算法的不同而改变。

### 3.2 存储算法本身所占用的存储空间： ###

它与算法书写的长短成正比，要压缩这方面的存储空间，就必须编写出较短的算法。

### 3.3 算法在运行过程中临时占用的存储空间： ###

它随算法的不同而异，有的算法只需要占用少量的临时工作单元，而且不随问题规模的大小而改变，我们称这种算法是**就地**进行的，是节省存储的算法，如这一节介绍过的几个算法都是如此；有的算法需要占用的临时工作单元数与解决问题的规模n有关，它随着n的增大而增大，当n较大时，将占用较多的存储单元，例如快速排序和归并排序算法就属于这种情况。  
如当一个算法的空间复杂度为一个常量，即不随被处理数据量n的大小而改变时，可表示为`O(1)`；当一个算法的空间复杂度与以2为底的`n`的对数成正比时，可表示为`0(10g2n)`；当一个算法的空I司复杂度与n成线性比例关系时，可表示为`0(n)`.若形参为数组，则只需要为它分配一个存储由实参传送来的一个地址指针的空间，即一个机器字长空间；若形参为引用方式，则也只需要为其分配存储一个地址的空间，用它来存储对应实参变量的地址，以便由系统自动引用实参变量。

[Link 1]: https://blog.csdn.net/qq_42785250?spm=1011.2124.3001.5343
[78c1c0b7757d4da48388aafa7cc7851d.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/23/00184032de814c77a5191121d43d2505.png
[51f00c37f00745f9a044367d14fb0609.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/23/05b2197e8ac44829a777a329bcd4d383.png