《计算之魂》阅读笔记

#吴军 #计算机

计算科学品味和认知进阶。

吴军博士的硅谷来信对我启发非常大，因此基本他写的书我都非常喜欢看，这次算是他真正第一本「硬核」计算机科学相关的书，对当前阶段的我，如及时雨般。

引子：计算的本质 —— 从机械到电子

• 运算能力 + 存储能力 + 指令控制
  • 算盘的计算之魂：珠算口诀
• 布尔代数、开关电路：等价性、模块化 -> 化繁为简
• 图灵机：计算机的本质是机械运动
  • 可计算的数据问题仅仅是所有问题的子集
  • 图灵的伟大之处在于划定了可计算问题的边界

第 1 章：毫厘千里之差 —— 大 O 概念

1.1 算法的规范化和量化度量

关于高德纳的五件事：

1. 计算机算法分析的鼻祖，提出了评估计算机算法的标准
2. 编著了计算机科学领域「圣经」——《计算机程序设计艺术》

比尔盖茨：如果你想成为一个优秀的程序员，那就去读这卷《基本算法》吧。

3. 迄今为止最年轻的图灵奖获得者
4. 编写了著名的排版软件 TeX
5. 硅谷地区众多图灵奖获得者中名气最大、最会编程的人

体系结构：软件领域从计算机科学中分离出来，蓬勃发展

1.2 大数和数量级的概念

高德纳的算法分析思想主要分为三个部分：

1. 在比较算法快慢时，只需要考虑数据量特别大，近乎无穷大时的情况
2. 决定算法快慢的因素有许多，但都可以归为两类：
   • 不随数据量变化的因素
   • 随数据量变化的因素
3. 两种算法在复杂度相差一点，在 N 不断放大时，效率就能差之千里。

复杂度、数量级、大 O 的概念

1.3 怎么寻找最好的算法

例题：总和最大区间问题 🌟🌟🌟
给定一个实数序列，设计一个最有效的算法，找到一个总和最大的区间

• 对应 Leetcode 题目：53. 最大子数组和
  • 我的题解(Swift)

pub fn max_sub_array(nums: Vec<i32>) -> i32 {
	let mut nums_iter = nums.into_iter();
	let mut cur_sum = nums_iter.nextMIN).to_owned(;
	let mut max_sum = cur_sum;

	for num in nums_iter {
		cur_sum = (cur_sum + num).max(num);
		max_sum = max_sum.max(cur_sum);
	}
	max_sum
}

分治算法、递归、少做无用功、逆向思维、复杂度巨大的差异

1.4 关于排序的讨论

根据时间复杂度，排序算法大致分为两类：

• O(N^2)：较为直观，无需太多计算机知识就能想到
• O(N logN)：执行效率高，相对不那么直观，找到并减少了无用功的步骤
  • 理解要点：递归和分治

1.4.1 直观的排序算法时间到底浪费在哪里

• 选择排序（Selection Sort）
• 插入排序（Insert Sort）
• 哪些操作在做无用功：
  • 1. 元素两两比较，未充分利用比较大小的可传递性，X<Y, Y<Z, 则 X< Z 一定成立
  • 2. 不必要的位置互换

1.4.2 有效的排序算法效率来自哪里