Java算法——大O记法

叁歲伎倆 2023-10-04 14:29 38阅读 0赞

算法时间复杂度分析；算法空间复杂度分析；大O记法

--------------------

#### 目录 ####

*  1.时间复杂度分析
 *   *  1.1.事后分析估算方法
     *  1.2.时候分析估算方法
 *  2.空间复杂度分析
 *   *  2.1.基本数据类型内存占用
     *  2.2.实例化对象的内存占用
 *  3.函数的渐进增长
 *  4.大O记法
 *   *  4.1.推导大O阶的标识法的规则：
     *  4.2.常见的大O阶
     *  4.3.最坏情况分析

## 1.时间复杂度分析 ##

用来计算算法时间损耗情况

### 1.1.事后分析估算方法 ###

将算法执行若干次，并计量执行算法所需要的时间

> 1.设置循环（如for循环），执行若干次算法  
> 2.利用`long start/end = System.currentTimeMills()` `timeA = end - start`计算耗费时间  
>   
> 显然，此方法只适用于小型算法

### 1.2.时候分析估算方法 ###

在计算机编写程序前，通过统计方法对算法耗时进行估算

> 一门**高级语言**编写的程序在计算机上运行所损耗的时间取决于：
> 
> --------------------
> 
>     1.算法采用的策略与方案     2.编译产生的代码质量     3.问题的输入规模     4.机器执行指令的速度

## 2.空间复杂度分析 ##

用来计算算法内存占用情况

### 2.1.基本数据类型内存占用 ###

单位：字节（Byte）= 8比特（bit）

<table> 
 <thead> 
  <tr> 
   <th>类型</th> 
   <th>内存</th> 
   <th>类型</th> 
   <th>内存</th> 
   <th>类型</th> 
   <th>内存</th> 
   <th>类型</th> 
   <th>内存</th> 
   <th>类型</th> 
   <th>内存</th> 
   <th>类型</th> 
   <th>内存</th> 
   <th>类型</th> 
   <th>内存</th> 
   <th>类型</th> 
   <th>内存</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>byte</td> 
   <td>1</td> 
   <td>short</td> 
   <td>2</td> 
   <td>int</td> 
   <td>4</td> 
   <td>long</td> 
   <td>8</td> 
   <td>float</td> 
   <td>4</td> 
   <td>double</td> 
   <td>8</td> 
   <td>boolean</td> 
   <td>1</td> 
   <td>char</td> 
   <td>2</td> 
  </tr> 
 </tbody> 
</table>

计算机访问内存的方式：一次一个字节

### 2.2.实例化对象的内存占用 ###

Java中数组被先定为对象

Date date = new Date()

1.  .**一个引用（机器地址）需要8个字节表示**

> 对象变量`date`，需要8个字节表示

1.  **每个对象自身需要占用16个字节**

> 除了对象内部存储的数据占用内存，对象的自身占用需要16个字节  
> `new Date()`需要16个字节保存对象的头信息

1.  **当内存装不下数据时，会以8字节为单位，进行填充内存**

> 如：现有17字节的数据需要装入16字节内存，装不下，系统将会自动增加8字节内存，也就是24个字节的内存来装着17个字节的数据

1.  **Java中数组被限定为对象**

> 一个原始数据类型的数组一般需要**24字节的头信息**（16字节自身对象开销，4字节保存长度，4字节填充空余的字节）

## 3.函数的渐进增长 ##

对于函数f(n)、g(n)，存在一个整数N，当n>N时，f(n)>g(n)

随着输入规模的增大：  
  
    1.**算法的常数操作可以忽略不计**  
  
    2.**与最高次项相乘的常数可以忽略**  
  
    3.**算法中n的最高次幂越小，算法效率越高**

## 4.大O记法 ##

使用O()表示时间/空间复杂度的记法：O(f(n)) = T(n)  
一般情况下，随着输入规模n的增大，T(n)增长最慢的算法为最优算法

**执行次数=执行时间**

对于Java这类在电脑这类拥有较大内存的计算机上运行的高级语言，讨论算法空间复杂度没有多大意义

### 4.1.推导大O阶的标识法的规则： ###

1.  用常数1取代运行时间中的所有加法常数
2.  在修改后的运行次数中，只保留高阶项
3.  如果高阶项存在，且常数因子不为1，则 去除 与这个项相乘的常数

### 4.2.常见的大O阶 ###

1.  常数阶O(1)

int n = 999;               //执行1次
    int m = 0;                 //执行1次

1.  线性阶O(n)

int n = 999;               //执行1次
    int m = 0;                 //执行1次
    for (int i=0;i < n;i++){
           
        m += i;                //执行n次
    }

1.  平方阶O(n^2)

int n = 999;                   //执行1次
    int m = 0;                     //执行1次
    for (int i=0;i < n;i++){
           
        m += i;                    //执行n次
        for (int j=n;j > 0;j--){
        
            m++;                   //执行n次
        }               
    }

1.  立方阶O(n^3)
2.  对数阶O(logn)

int n = 999;                //执行1次
    int m = 0;                  //执行1次
    for (int i=1;i <= n;i*=2){
        
        m+=i;                   //执行log2(n)次
    }

> 在大O分析时，我们会忽略底数，因为无论底数为多少，当随着n增大时，增长趋势一样

O(1) < O(logn) < O(n) < O(nlogn) < O(n^2) < O(n^3)

### 4.3.最坏情况分析 ###

**（没做特殊要求时）运行时间都是指在最坏情况下的运行时间**

最坏情况

> 是一种保证，即使在最坏情况下，也能正常提供服务
> 
> --------------------
> 
> 如：在一个含有n个元素的列表中寻找目标元素  
> 最好情况：第一个元素就是目标元素O(1)  
> 平均情况：O(n/2)  
> 最坏情况：查找的最后一个元素才为目标元素O(n)

--------------------