《计算思维导论》笔记：什么是有限时间内能求解 - 问题的计算复杂性与分类

电玩女神 2024-02-05 11:56 14阅读 0赞

> 《大学计算机—计算思维导论》（战德臣 哈尔滨工业大学）  
> 《计算思维第14讲 - 什么是有限时间内能求解》

## 1. 概述（思维导图） ##

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

## 2. 关于问题求解的疑问 ##

*  什么是有限时间内能求解的问题？
 *  什么是难解型问题？

## 3. 算法复杂性 ##

### 3.1. 算法复杂性的概念 ###

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

### 3.2. 算法复杂性计算示例 ###

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

### 3.3. 不同量级复杂性在计算时间方面的差异 ###

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

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

## 4. 由`算法复杂性`到`计算复杂性` ##

### 4.1. 计算复杂性 ###

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

### 4.2. 有限时间内是否能完成算法的执行 ###

#### 4.2.1. 复杂度 `多项式级别`：能够完成 ####

#### 4.2.2. 复杂度 `指数级别`或`阶乘级别`：不能完成 ####

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

## 5. 可求解与难求解问题 ##

### 5.1. 用计算复杂性划分问题 ###

NP类问题，是可验证问题。  
加密算法：NPC问题。  
![在这里插入图片描述][f1ec17c9af574ec8a2321d909e8e923a.png]

### 5.2. 可解性问题与难解性问题 ###

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

## 6. NPC类问题求解思维 ##

### 6.1. NPC类问题 - 求近似解、满意解 ###

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

### 6.2. 如何降低计算量 - 随机搜索 ###

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

### 6.3. 如何提高近似解的质量 - 导向性随机搜索 ###

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

### 6.4. 如何避免初始解的偏差 - 导向性群（体）随机搜索 ###

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

## 7. 小结 ##

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

[9ca4fa9e88b64587a921c4f66df350f7.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/05/aac2530eac524b01905c711c50c270f2.png
[39e40d9bf3824e2ab25a08d78983760a.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/05/9c35a698da934746ade458f3b79498e2.png
[50e962583a0c4f308450e017d9d05474.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/05/7f6bc95fec74452087cb128762d9789b.png
[bed267c133ce4277b25f52e2cfbe4381.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/05/7ee33e226bf84d57b1e4c3139e2d99ea.png
[6715c262041d4b5aa75cb90eae554a55.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/05/b1e539c76c1a49559d84e1879686b6d9.png
[acd521ef6e65486d86473ac4bda12381.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/05/cc06076e582843abb7ff85cd040084dd.png
[e4bd4ae16b1d4d119e063be36e21a7a0.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/05/7275284eda9545b9a41e89682eb7d56e.png
[f1ec17c9af574ec8a2321d909e8e923a.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/05/a8faa93c36e34ef2be58bc2d1ab7c806.png
[5fbb9f460dd644f5a7fb49dd10569e90.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/05/91cbff2f9f19475198ff5d40c0fcdd2c.png
[72c8024247d1466d96582d3ec5076d14.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/05/1b18620526da407288901a9fee9c39fe.png
[03c792982d194085a41e868196119881.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/05/6d332373d3ff4320a892b6c2969be2be.png
[84ae4d383ca34737ae2bd9914bc57e99.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/05/fcb1d82e5905455a929660c269cceb83.png
[4424021cd76d474a961554d1dab48d64.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/05/814095bb9fff427388b73b52ad24c670.png
[ae8d4869c42641eeabddc7c5b1830c2c.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/05/d8e89e9db87b42ab99a8e0bcfa139afd.png