数据结构与算法学习之算法入门笔记

深藏阁楼爱情的钟 2023-07-13 15:14 1阅读 0赞

### 计算 ###

关于计算：

> 对象：规律、技巧。
> 
> 目标：高效、低耗。

Computer science ------ **Computing science**

算法：特定计算模型下，旨在解决特定问题的指令序列。

> 输入、输出、正确性、确定性、可行性、有穷性。

Hailstone序列目前无法证明有穷性或无穷性。  
程序 不等于 算法 死循环~~有穷性

好算法：正确？健壮？可读？**效率**！！！速度尽可能快，存储空间尽可能少。（既要马儿少吃草，又要马儿快快跑！）

> **Algorithm + Data Structures = Programs**

### 图灵机 ###

图灵机(Turing Machine)：  
![邓俊辉先生的课堂][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzE2NDk3NDIz_size_16_color_FFFFFF_t_70]  
![邓俊辉先生的课堂][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzE2NDk3NDIz_size_16_color_FFFFFF_t_70 1]

### RAM ###

Random Access Machine (RAM)  
寄存器顺序编号，总数没有限制。  
每一基本操作仅需常数时间。  
与TM模型一样，RAM模型也是一般计算工具的简化与抽象。

算法运行时间 可转化为 算法需要执行的基本操作次数。（这样可以不用考虑硬件环境）

### big-O notation ###

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzE2NDk3NDIz_size_16_color_FFFFFF_t_70 2] ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzE2NDk3NDIz_size_16_color_FFFFFF_t_70 3]

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzE2NDk3NDIz_size_16_color_FFFFFF_t_70 4]

大O记号 不求甚解，即眼光长远，不拘细节

> 常系数可忽略，低次项可忽略。

**常数复杂度 constant function O(1)** 甚至2013^2013 也等于 O(1)。  
不含转向（循环、调用、递归）的顺序执行代码往往是O(1)，但有时含循环、调用、递归由于存在特殊情况，所以也可能是O(1)的。  
**对数O(log n)** 对底数无所谓，可通过换底公式证明；对常数次幂无所谓，因为完全可以提到系数上，而常数可忽略；对数本身也可以是多项式形式(ploy-log function)，此时可忽略低次项。  
**多项式复杂度O(n^c)** 多项式中只关心最高项，并忽略常系数。  
其中比较特殊的是：**线性复杂度O(n):linear function**  
然后比较重要也比较常见的是介于O(n)与O(n^2)之间的复杂度，  
**指数复杂度O(2^n)**：exponential function 往往是不可忍受的。

CPU 目前大概是1s 9次方的运算。  
而1天大概为 10的五次方秒；  
一生用一世纪来估算，大概3\* 10^4 days 即 3\* 10 ^9秒；  
三生三世 大概是300年 估算10 ^10秒；  
所以在三生三世中的一天 相当于 一天中的一秒。  
现在估计宇宙大爆炸至今约为10 ^21秒  
1000秒大概 20分钟  
归并排序MergeSort是 n\* log(n)的复杂度

要抓住问题的主要方面！  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzE2NDk3NDIz_size_16_color_FFFFFF_t_70 5]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzE2NDk3NDIz_size_16_color_FFFFFF_t_70]: /images/20230529/a15830a93e114863a296cde2653e767f.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzE2NDk3NDIz_size_16_color_FFFFFF_t_70 1]: /images/20230529/0452789250014d68a1f6f277608c107a.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzE2NDk3NDIz_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20200313140400437.jpg?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzE2NDk3NDIz,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzE2NDk3NDIz_size_16_color_FFFFFF_t_70 3]: /images/20230529/c812e22c0d744126b341632156aeed9e.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzE2NDk3NDIz_size_16_color_FFFFFF_t_70 4]: /images/20230529/6f95f608c37a4d77b7c2931af24b3506.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzE2NDk3NDIz_size_16_color_FFFFFF_t_70 5]: /images/20230529/570cae4c9efc43709caeebb6f8b630c1.png