[datawhale202208]计算之魂共读：算法规范化，大数和数量级的概念

结论速递

本次阅读了1.1及1.2章节。

1.1章节首先介绍计算机的软硬件分离历史，引出了程序算法独立存在的价值。并介绍了提出将算法进行量化度量的高德纳的五件闻名于世的事，强调了算法量化的重要性。

1.2章节首先介绍了计算机所需处理的数据——大数的概念，随后介绍了高德纳的算法分析思想：只需考虑数据量特别大的情形，决定算法快慢的因素可以分为与数据量有关及无关的，复杂度上的微小差异会在数据量大时导致效率的亿万倍之差。并讲述了大O的概念。

1 算法规范化和量化度量

1.1 阅读归纳思维导图

1.2 关键内容总结

1. 冯诺依曼体系结构
   • 客观上将计算机分成了软硬件两个部分。
   • 涵盖了一种通用的计算机的体系结构，并且告诉后人计算机是需要顶层设计的，而不是从经验出发归纳总结。
   • 从而确定了软件算法的独立存在地位。
2. 计算机算法基础的奠基人：高德纳
   • 提出评估计算机算法的标准；
   • 编写了计算机科学领域的“圣经”——《计算机程序设计艺术》；
   • 最年轻的图灵奖获得者；
   • 学术排版之王LaTex前身TeX之父；
   • 算法效率的践行者：总能用最慢的计算机在硅谷地区编程比赛中打败众多图灵奖得主拔得头筹。

1.3 思考题

世界上还有什么产品类似于计算机，是软硬件分离的？

能想到的比如现在的很多涉及智能控制的产品都可以说是软硬件分离的。
在工业中的，比如数控机床，本身是机床（硬件），加上控制端（软件），来实现自动化机床操作；
比如电动水阀门，本身是一个阀门硬件，和一些传感器（硬件），加上一个控制器（软件），来实现反馈调节控制。
在家居中的，比如智能灯，本身是灯泡（硬件），加上智能控制端（软件），来实现智能化的开关灯。
其优势在于可以利用原有的硬件基础，叠加软件进行智能化升级~这种趋势或许在以后会越来越多。

2 大数和数量级的概念

2.1 阅读归纳思维导图

2.2 关键内容小结

1. 计算机所需处理的数据量远超人们的常规认知
2. 高德纳的算法分析思想
   • 只需考虑数据量特别大的情形；
   • 所有决定算法快慢的因素都可以分为与数据量有关及无关的；
   • 复杂度上的微小差异会在数据量大时导致效率的亿万倍之差；
3. 算法复杂度
   • 只考虑$N$趋近于无穷大时和$N$相关的那部分；
   • 把一种算法的计算量或者占用空间的大小，写成$N$的一个函数$f(N)$；
   • 函数的边界（上界或者下界）可以用数学上的大O概念来限制:
     两个函数$f(N)$和$g(N)$，在$N$趋近于无穷大时比值只差一个常数，则可以被看成同一个数量级的函数。
     在计算机科学中相应的算法被认为是具有相同的复杂度。
   • 一个算法的复杂度由一高一低的两部分$f(N)$和$g(N)$组成，即$f(N)+g(N)$，后面数量级低的那部分可以直接省略，也就是说$O(f(N)+g(N))=O(f(N))$。
     其目的是让计算机科学家们能够把注意力放在数量级的差异上。

2.3 思考题

如果一个程序只运行一次，在编写它的时候，你是采用最直观但是效率较低的算法，还是依然寻找复杂度最优的算法？

其实这个问题没有问的很清楚，不清楚程序所涉及的数据量级及运算量如何，也没有提及手头所拥有的计算资源如何。在这种背景下，最理想的状况下是需要寻找复杂度最优的算法的，这样可以保证在无论计算资源是否富裕，且程序问题本身是否十分复杂的条件下，都能尽可能高效地解决问题。
在实际的实践中，或许我们会受到时间限制等因素的影响，不得不放弃暂时对复杂度最优的追求。但编写程序是一个熟能生巧的过程，对复杂度最优的追求需时刻牢记于心。

参考阅读

1. 计算之魂——吴军