时间复杂度_空间复杂度

朱雀 2023-06-29 15:59 118阅读 0赞

## 时间复杂度\_空间复杂度 ##

主要说明以下3点：  
1.算法效率  
2.时间复杂度  
3.空间复杂度

一、**算法效率**  
算法效率分析分为两种：第一种是时间效率，第二种是空间效率。时间效率被称为时间复杂度，而空间效率被 称作空间复杂度。 时间复杂度主要衡量的是一个算法的运行速度，而空间复杂度主要衡量一个算法所需要的额 外空间。  
二、**时间复杂度**  
算法中的基本操作的执行次数，为算法的时间复杂度。

// 请计算一下func1基本操作执行了多少次？
     void func1(int N){ 
     int count = 0; 
     for (int i = 0; i < N ; i++) {   
    for (int j = 0; j < N ; j++) {      
     count++;  
      }
       }
    for (int k = 0; k < 2 * N ; k++) {  
      count++; 
      }
    int M = 10;  
       while ((M--) > 0) { 
          count++;
           }
           System.out.println(count); 
           }

实际中我们计算时间复杂度时，我们其实并不一定要计算精确的执行次数，而只需要大概执行次数，那么这里 我们使用大O的渐进表示法。

最坏情况：任意输入规模的最大运行次数(上界)  
平均情况：任意输入规模的期望运行次数  
最好情况：任意输入规模的最小运行次数(下界) 例如：在一个长度为N数组中搜索一个数据x 最好情况：1次找到  
最坏情况：N次找到 平均情况：N/2次找到

**在实际中一般情况关注的是算法的最坏运行情况，所以数组中搜索数据时间复杂度为O(N) 。  
三、空间复杂度  
空间复杂度是对一个算法在运行过程中临时占用存储空间大小的量度 。空间复杂度不是程序占用了多少bytes 的空间，因为这个也没太大意义，所以空间复杂度算的是变量的个数。空间复杂度计算规则基本跟实践复杂度 类似，也使用大O渐进表示法**。  
1，使用了常数个额外空间，空间复杂度为 O(1) 。  
2，动态开辟了N个空间，空间复杂度为 O(N) 。  
3，递归调用了N次，开辟了N个栈帧，每个栈帧使用了常数个空间。空间复杂度为O(N