算法时间空间复杂度

墨蓝 2024-03-22 14:57 68阅读 0赞

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

*  算法
 *   *  算法特性
 *  时间复杂度
 *   *  时间复杂度概念
     *  算法运行时间
     *  例如
     *  时间复杂度分三种
 *  空间复杂度

## 算法 ##

### 算法特性 ###

1.**有穷性**：执行有穷步（有限步）之后结束。

2.**确定性**：只有唯一的执行路径。

3.**可行性**：代码可以执行起来。

4、**输入**：零个或多个输入。

5.**输出**：一个或多个输出。

时间效率和空间效率有时候是有矛盾的

## 时间复杂度 ##

### 时间复杂度概念 ###

**概念：** 若有某个辅助函数 f ( n ) \\color\{pink\}\{f(n)\} f(n) 使得当n趋近于无穷大时。  T ( n ) / f ( n ) \\color\{pink\}\{T(n)/f(n)\} T(n)/f(n)的极值为不等于0的常数，则称 f n 是 T ( n ) \\color\{pink\}\{fn是T(n)\} fn是T(n)的同数量级函数。记作 T ( n ) = O ( f ( n ) ) \\color\{pink\}\{T(n)=O(f(n))\} T(n)=O(f(n))称 O ( f ( n ) ) \\color\{pink\}\{O(f(n))\} O(f(n))为算法的渐进时间复杂度（O是数量级的符号）

时间复杂度是由嵌套最深层语句的频度决定的。

### 算法运行时间 ###

算法运行时间=（每条语句频度 \* 该语句执行一次所需的时间）的求和。

### 例如 ###

i=1;
    while(i<=n)
    	i=i*2;

**解释：**

<table> 
 <thead> 
  <tr> 
   <th align="center">执行循环次数</th> 
   <th align="right"></th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td align="center">1</td> 
   <td align="right">i=1*2=2<sup>1</sup></td> 
  </tr> 
  <tr> 
   <td align="center">2</td> 
   <td align="right">i=2*2=2<sup>2</sup></td> 
  </tr> 
  <tr> 
   <td align="center">3</td> 
   <td align="right">i=2*2 *2=2<sup>3</sup></td> 
  </tr> 
  <tr> 
   <td align="center">x</td> 
   <td align="right">i=2<sup>x</sup></td> 
  </tr> 
 </tbody> 
</table>

i<=n
    则
    2^x<=n
    则
    x<=log2(n)

### 时间复杂度分三种 ###

(1):最坏时间复杂度

(2):平均时间复杂度

(3):最好时间复杂度

以上三种复杂度，通常考虑最坏时间复杂度

## 空间复杂度 ##

顾名思义： \\color\{pink\}\{顾名思义：\} 顾名思义：算法所需存储空间的度量。 S ( n ) = O ( f ( n ) ) \\color\{pink\}\{S(n)=O(f(n))\} S(n)=O(f(n))

![在这里插入图片描述][e9d8aa712fc14ae08e572a5ff2461f90.jpeg_pic_center]

学的不是技术，更是梦想！！！

[e9d8aa712fc14ae08e572a5ff2461f90.jpeg_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/18/f27e40066a474f87ac530cbd506578c2.png