(Java数据结构)时间复杂度空间复杂度

曾经终败给现在 2024-04-07 14:00 100阅读 0赞

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

*  算法效率
 *  时间复杂度
 *   *  概念
     *  大O的渐进表示法
     *  常见时间复杂度计算举例
 *  空间复杂度

## 算法效率 ##

> 算法效率分析分为两种：第一种是时间效率，第二种是空间效率。时间效率被称为时间复杂度，而空间效率被称作  
> 空间复杂度。 时间复杂度主要衡量的是一个算法的运行速度，而空间复杂度主要衡量一个算法所需要的额外空间。

## 时间复杂度 ##

### 概念 ###

> 算法的时间复杂度是一个数学函数,算法中的基本操作的执行次数，为算法的时间复杂度。

### 大O的渐进表示法 ###

> 1、用常数1取代运行时间中的所有加法常数。  
> 2、在修改后的运行次数函数中，只保留最高阶项。  
> 3、如果最高阶项存在且不是1，则去除与这个项目相乘的常数。得到的结果就是大O阶。

> 有些算法的时间复杂度存在最好、平均和最坏情况：  
> 最坏情况：任意输入规模的最大运行次数(上界)  
> 平均情况：任意输入规模的期望运行次数  
> 最好情况：任意输入规模的最小运行次数(下界)

> 一般情况关注的是算法的最坏运行情况。

### 常见时间复杂度计算举例 ###

// 计算bubbleSort的时间复杂度
    void bubbleSort(int[] array) {
        
    for (int end = array.length; end > 0; end--) {
        
        boolean sorted = true;
        for (int i = 1; i < end; i++){
        
          if (array[i - 1] > array[i]){
        
             Swap(array, i - 1, i);
             sorted = false;
          }
        }
        if(sorted == true) {
        
           break;
        }
      }
    }

> 最坏情况：数组是降序，假设数组有n个元素，执行次数：n-1+n-2+n-3+…+1=n(n-1)/2.  
> 最坏情况的时间复杂度是O(n^2)。

> 最好情况：数组就是升序，第一趟走完不需要交换，执行次数是n-1。  
> 最好情况的时间复杂度是O(n)。

> 递归的时间复杂度=递归的次数\*每次递归之后的执行次数

// 计算斐波那契递归fibonacci的时间复杂度？
    int fibonacci(int N) {
        
    return N < 2 ? N : fibonacci(N-1)+fibonacci(N-2);
    }

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

## 空间复杂度 ##

> 空间复杂度是对一个算法在运行过程中临时占用存储空间大小的量度。  
> 可以理解为额外占用的存储空间。

/
    / 计算斐波那契递归fibonacci的空间复杂度？
    int fibonacci(int N) {
        
    return N < 2 ? N : fibonacci(N-1)+fibonacci(N-2);
    }

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

> 空间复杂度是O(n)。

[2c45ea9e9920449898e370b58b76aaa1.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/07/fc9b942ba0cb48d9a15a4891e6f566c9.png
[99aaf4825dfa4e0a9be501fb6cf3d519.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/07/aa33d95d798949b6ad82213619a92513.png