时间复杂度和空间复杂度

浅浅的花香味﹌ 2022-11-12 14:59 274阅读 0赞

#### 一、时间复杂度 ####

##### 1、定义 #####

若存在函数 ，使得当 趋向无穷大时， 的极限值为不等于 0 的常数，则称 是 的同数量级函数，记作 ，称为算法的渐进时间复杂度，简称时间复杂度，用大 O 来表示，称为大 O 表示法；

##### 2、原则 #####

*  若运行时间是常数量级，则用常数 1 表示；
 *  只保留时间函数中最高阶项
 *  若最高阶项存在，则省去最高阶项前的系数；

##### 3、时间复杂度曲线 #####

常见时间复杂度有:常数阶、线性阶、平方阶、立方阶、对数阶、nlog2n阶、指数阶  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTA1MjAxNDY_size_16_color_FFFFFF_t_70]  
效率：

O(1) > O(log2n)> o(n)> o(nlog2n) > o(n^2) > o(n^3) > o(2^n) > o(n!) > o(n^n)

##### 4、示例 #####

（1） 常数阶 O(1)

public void test(n){ 
    	System.out.println(“1”);
    	System.out.println(“2”);
    }
    不管n是多少，只打印2次，那么时间复杂度就是O(2),取为O(1)

（2）线性阶 O(n)

计算1+2+3+....+n的和
    
    int sum=0
    for(i=0;i<n;i++){ 
       sum+=i
    }
    该计算中循环了n次，所以时间复杂度就是O(n), 时间复杂度就是程序计算次数

（3）平(立)方阶

int sum=0;
    for(int i=0;i<n;i++){ 
        for(int j=0;j<n;j++){ 
          sum+=j
        }
    }
    两次循环，里面循环执行了n次，外层循环也执行了n次，所以时间复杂度为O(n^2),立方阶同理

（4）特殊平方阶

例如：O(n^2/2+n/2)->O(n^2)
    
    for(){ 
        for(){ 
        .....            ----------->n^2
        }
    }
                                      +
    for(){ 
       .....             ------------> n
    }
    System.out.println(“1”);
    
    所以整体上计算次数为n^2+n+1,则时间复杂度为O(n^2)

（5）对数阶

例如：O(log2n)
    
    while(n>=1){ 
        n=n/2;
    }
    
    n    执行次数
    1      1
    2      2
    3      2
    
    规律：
    
    第一次     第二次       第三次      第四次      第五次
    n          n/2        n/2/2      n/2/2/2    n/2/2/...
    20--------->10---------->5-------->2.5------->1
    可以得出规律:
    n*（1/(2^m)）=1;
    即 n=2^m
    得出m=log2n,所以时间复杂度为O(logn)或者O(log2n)

对数函数的基本算法

1、a^(log(a)(b))=b   =>log(a)(1)=0,log(a)(a)=1
    2、log(a)(MN)=log(a)(M)+log(a)(N); 
    3、log(a)(M÷N)=log(a)(M)-log(a)(N); 
    4、log(a)(M^n)=nlog(a)(M) 
    5、log(a^n)M=1/nlog(a)(M)

##### 5、常见排序算法的时间复杂度情况 #####

![在这里插入图片描述][2021032416292358.png]

#### 二、空间复杂度 ####

##### 1、定义 #####

空间复杂度是对一个算法在运行过程中临时占用存储空间大小的一个量度（即除开原始序列大小的内存，在算法过程中用到的额外的存储空间），反映的对内存占用的趋势，而不是具体内存

##### 2、定义 #####

空间复杂度的算法与时间复杂度类似

*  如果程序所占用的存储空间和输入值无关，则该程序的空间复杂度就为 O(1)；反之，如果有关，则需要进一步判断它们之间的-关系：
 *  如果随着输入值 n 的增大，程序申请的临时空间成线性增长，则程序的空间复杂度用 O(n) 表示;
 *  如果随着输入值 n 的增大，程序申请的临时空间成 n2 关系增长，则程序的空间复杂度用 O(n2) 表示；
 *  如果随着输入值 n 的增大，程序申请的临时空间成 n3 关系增长，则程序的空间复杂度用 O(n3) 表示；  
    …

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTA1MjAxNDY_size_16_color_FFFFFF_t_70]: /images/20221022/3b3d0c7445ee4584967e98149dc6ee81.png
[2021032416292358.png]: /images/20221022/95abd092e4fe422c9739d511dd5aa0a6.png