【读书笔记】数据结构与算法之美 第1章 复杂度分析

《数据结构与算法之美》，王争 著

标签：数据结构、算法

第一章 复杂度分析分为两个部分，第一部分，首先从复杂度分析的意义开始引入，然后介绍了大O复杂度表示法，介绍了两种时间复杂度分析方法，介绍了几种常见的时间复杂度量级，最后简介了空间复杂度分析方法。第二部分通过代码举例分析的方式，介绍了最好、最坏、平均、均摊四种时间复杂度分析方法。

点评：第一章的内容并不长，对复杂度分析的术语和概念等知识的描述不多，因为这不是一本教科书，作者从直接给出代码样例复杂度分析的角度来阐述复杂度分析，让内容变得更加通俗易懂，便于初学者学习，而且，选取的代码，也有特色，实用性强。

内容推荐：

1：讲解了两种比较实用时间复杂度分析方法：加法法则和乘法法则。这两种方法，所有的复杂度分析的书都会涉及，但是用这两个词并不多，这两个词来表述这两个方法，对学习者交流不错。请记住这两个词：加法法则和乘法法则。

2：几种常见的时间复杂度量级，这一段也有意思，作者代为总结对学习者有帮助。

3：第二部分，介绍四种时间复杂度分析方法，要注意，这类复杂度分析方法，有一个前提，就是问题的输入规模，即n，是不变的，在输入规模不变时，有些代码针对不同的输入实例，时间复杂度是不一样的。

4：第二部分中，介绍的加权平均时间复杂度（期望时间复杂度），这个术语和方法，在常见的数据结构或算法教材中复杂度分析中是没有的，在教材中，这种方法叫做概率分析，属于高级算法分析方法。均摊分析也是高级算法分析方法之一。因为这本书的侧重点不是理论，也不是教材，所以概率分析和均摊分析的理论知识，读者需要从其他书籍中获取了。

5：这一章结束时，留的事件复杂度分析思考题，不错，因为这段代码有一定的实用性（这是C++ STL中数组容器的实现原理），而且这段代码的时间复杂度分析，可以把书中介绍的最好、最坏、平均、均摊四种时间复杂度分析方法四都用上。