搞懂时间复杂度、时间复杂度

末蓝、 2023-10-08 12:48 12阅读 0赞

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

*  写在前面
 *   *  1、数学中的log什么意思？
     *  2、时间复杂度
     *   *  2.1、用T(n)表示程序执行次数
         *  2.2、用O(n)表示时间复杂度
         *  2.3、时间复杂度大小比较
     *  3、用O(n)表示空间复杂度

## 写在前面 ##

时间复杂度是用来干什么的？  
时间复杂度可以用来衡量算法的执行效率。

> 注意并不是衡量具体执行时间，而是用来表示执行时间的量级、消耗时间的趋势

空间复杂度是用来干什么的？  
空间复杂度可以用来衡量占用存储的趋势。

> 一般考虑空间复杂度仅考虑的是”算法“上，不考虑”代码“本身的长短。

### 1、数学中的log什么意思？ ###

预备知识：数学中的log什么意思？

log表示对数。如果a的b次方等于n，那么  
![在这里插入图片描述][20210422104213714.png]  
在上面的式子中，我们可以看出log最后等于的是b，b表示a的多少次方，b是一个量级、a是一个系数，而时间复杂度中只考虑量级，所以我们写的时候常常忽略a，直接写 log n。

### 2、时间复杂度 ###

#### 2.1、用T(n)表示程序执行次数 ####

1、如下程序执行了两次，T(n) = 2

void a(){
        
       System.out.println("1");
       System.out.println("2");
    }

2、如下程序执行了3n次，T(n) = 3n

void a(int n){
        
        for(int i=0; i<n; i++){
        ;
            System.out.println("1");
            System.out.println("2");
            System.out.println("3");
        }
    }

3、如下程序执行了 5倍log(2)n 次，T(n) = 5logn， (底数2被忽略了)

void a(int n){
        
       for(int i=1; i<n; i*=2){
        
           System.out.println("1");
           System.out.println("2");
           System.out.println("3");
           System.out.println("4");
           System.out.println("5");
       }
    }

#### 2.2、用O(n)表示时间复杂度 ####

比如算法A的相对时间是T（n）= 100n，算法B的相对时间是T（n）= 5n^2，这两个到底谁的运行时间更长一些？这就要看n的取值了。

> 所以，这时候有了渐进时间复杂度的概念，官方的定义如下：  
> 若存在函数 f（n），使得当n趋近于无穷大时，T（n）/ f（n）的极限值为不等于零的常数，则称 f（n）是T（n）的同数量级函数。记作 T（n）= O（f（n）），称O（f（n）） 为算法的渐进时间复杂度，简称时间复杂度。  
> 渐进时间复杂度用大写O来表示，所以也被称为大O表示法。

> 简单的说 O（n）就是T（n）省去系数、仅留下最高项，也就是时间复杂度只关注程序执行的“量级”。

例如：  
T（n） = 3n ，省去系数3，仅保留量级n，转化的时间复杂度为：  
T（n） = O（n）

T（n） = 5log(2)n ，省去系数5、底数2，转化的时间复杂度为：  
T（n） = O（logn）

T（n） = 2 只有常数量级，转化的时间复杂度为：  
T（n） = O（1）

T（n） = 0.5n^2 + 0.5n  
最高阶项为0.5n^2，省去系数0.5，转化的时间复杂度为：  
T（n） = O（n^2）

#### 2.3、时间复杂度大小比较 ####

这四种时间复杂度究竟谁用时更长，谁节省时间呢？稍微思考一下就可以得出结论：

O（1）< O（logn）< O（n）< O（n^2）

在编程的世界中有着各种各样的算法，除了上述的四个场景，还有许多不同形式的时间复杂度，比如：

O（nlogn）, O（n^3）, O（m\*n），O（2^n），O（n！）

举例：  
算法A的相对时间规模是T（n）= 100n，时间复杂度是O(n)  
算法B的相对时间规模是T（n）= 5n2，时间复杂度是O(n2)  
算法A运行在小灰家里的老旧电脑上，算法B运行在某台超级计算机上，运行速度是老旧电脑的100倍。  
那么，随着输入规模 n 的增长，两种算法谁运行更快呢？  
![在这里插入图片描述][20210422110951851.png]  
从表格中可以看出，当n的值很小的时候，算法A的运行用时要远大于算法B；当n的值达到1000左右，算法A和算法B的运行时间已经接近；当n的值越来越大，达到十万、百万时，算法A的优势开始显现，算法B则越来越慢，差距越来越明显。

### 3、用O(n)表示空间复杂度 ###

通常来说，只要算法不涉及到动态分配的空间以及递归、栈所需的空间，空间复杂度通常为O(1)。

O(1)  
![在这里插入图片描述][20210422140109646.png]  
O(n)：数组  
![在这里插入图片描述][2021042214015553.png]  
O(n^2)：二维数组  
![在这里插入图片描述][20210422140223944.png]

[20210422104213714.png]: https://img-blog.csdnimg.cn/20210422104213714.png
[20210422110951851.png]: https://img-blog.csdnimg.cn/20210422110951851.png
[20210422140109646.png]: https://img-blog.csdnimg.cn/20210422140109646.png
[2021042214015553.png]: https://img-blog.csdnimg.cn/2021042214015553.png
[20210422140223944.png]: https://img-blog.csdnimg.cn/20210422140223944.png