《数据结构与算法之美》读书笔记

写在前面

这本书的大部分内容比较浅显，因此只挑DSAA课程上没有涉及或没有深入讨论的点总结

第二章

数组相关

1. 提高传统数组插入/删除数据效率的方法：

   • 如果插入的数据不要求有序，可以直接把某位的原数据替换成新数据，然后把原数据放到数组末尾，避免大面积的数据移动。
   • 删除时不用一个一个删，可以先把要删的元素一个个标记好，等到数组中没有更多的存储空间时一并集中删除。

2. 警惕C语言中数组访问越界的问题，通过内存公式计算出的内存地址是可用的，即便越界，程序也可能不报任何错。

3. 容器（ArrayList/vector）VS 传统数组：

   • 容器好用，上手快，封装性强，但有时需要装箱拆箱，存在性能损失。
   • 插入数据时的扩容操作隐藏了复杂度，一行操作可能实际上远远不止。
   • 对于底层的开发，性能优化需要做到极致，数组优于容器。

C和Java数组的实现方式

• C/C++的多维数组也是从前往后连续存储，Java则是存储对象的引用。

• JavaScript根据存储内容动态选择存储结构，可利用ArrayBuffer进行底层开发。

第三章

递归

1. 堆栈溢出不一定是死循环，可能是递归太深，栈装不下了。

2. 递归时常常会不小心重复计算，可以使用哈希表等事先检测是否已求解过。

3. 尾递归可避免堆栈溢出，但在实际软件开发中并没有多大用途。

排序

1. 稳定排序与非稳定排序：稳定排序保持相同元素相对顺序不变。

2. 归并排序虽稳定但空间复杂度高，通常不如快速排序实用。

3. 线性排序：

   • 桶排序：适用于数据易于划分成若干个桶的场景，需注意内存占用和数据范围。

   • 计数排序：桶内数据相同，适用于高考分数等场景，注意处理负数和时间复杂度。

   • 基数排序：要求每位排序使用稳定排序算法，时间复杂度近似O(n)。