这是一本零根底入门的书，写得十分的浅显易懂，就算不会写代码也能看懂。而且很薄，内容不多，一两个星期就能看完。
次要讲了工夫复杂度的概念、常见的的数据结构和算法。
对于想学数据结构和算法，又啃不下看不懂《算法导论》那种大部头书的人，强烈推荐看这本小书入门。不看会悔恨系列：）
书的豆瓣地址：https://book.douban.com/subje…
我这篇笔记只整顿了前三章的内容。

根底数据结构：数组

个别数据结构都有以下 4 种操作（或者说用法）。
读取 ：查看数据结构中某一地位上的数据。
查找 ：从数据结构中找出某个数据值的所在。
插入 ：给数据结构减少一个数据值。
删除：从数据结构中移走一个数据值。

操作的速度，并不按工夫计算，而是按 步数 计算。

对数组进行读取操作 ，即查看数组中某个索引所指的数据值，这 只有一步 就够了，因为计算机本身就有跳到任一索引地位的能力。
当程序申明一个数组时，它会先划分出一些 间断 的空格子以备应用。
只须要一步，是因为：
(1) 计算机能够一步就跳到任意一个内存地址上。
(2) 数组自身会记有第一个格子的内存地址，因而，计算机晓得这个数组的结尾在哪里。
(3) 数组的索引从 0 算起。
(4) 数组的格子是间断的。
所以，数组的读取是一种十分高效的操作，因为它只有一步就好。一步天然也是最快的速度。
这种一步读取任意索引的能力，也是数组好用的起因之一。

对数组进行查找操作 ，须要从第 0 个，到最初一个， 挨个寻找 数组中的每个值 (遍历数组)，直到找到为止。
最好的状况只须要一步，在数组的第 0 个找到了，最坏的状况，长度为 N 的数组，须要 N 步，找到最初一个才找到、或者找不到。

对数组进行插入操作 ，须要把插入地位前面的值往后移，为新插入的元素腾出空间。最好的状况是在数组开端插入，只须要一步，直接插入，不须要腾空间。最坏的状况是在数组的结尾插入，要把数组的每一项都往后移一位，长度为 N 的数组， 须要 N 步 操作。

对数组进行删除操作 ，须要删除元素，而后把元素前面的所有元素都往前移一位。跟插入一样，最好的状况是删除数据开端的元素，最坏的状况是删除数组结尾的元素， 须要 N 步。

工夫复杂度：大 O 记法

影响算法性能的次要因素是其所需的步数。

对于数组的查找，咱们能够这样形容：对于具备 N 个元素的数组，查找操作最多须要 N 步。（个别叫这种查找为“线性查找”）

这听起来很啰唆。为了不便表白数据结构和算法的工夫复杂度，计算机科学家从数学界借鉴了一种简洁又通用的形式，那就是 大 O 记法。

数组不管多大，读取都只需 1 步。用大 O 记法来示意，就是：O(1)  也叫常数工夫。

对于 N 个元素的数组，线性查找须要花 N 步。用大 O 记法来示意，即为：O(N)  也叫线性工夫。

二分查找的大 O 记法是：O(log N)  也叫对数工夫。

O(log N) 也就是 O(log2 N)，不过为了不便就省略了 2 而已。
O(log N)则代表算法解决 N 个元素须要 log2 N 步。如果有 8 个元素，那么这种算法须要 3 步，因为 log2 8 = 3。
从另一个角度来看，如果要把 8 个元素一直地分成两半，那么得拆分 3 次能力拆到只剩 1 个元素。
这正是二分查找所干的事件。它就是一直地将数组拆成两半，直至范畴放大到只剩你要找的那个元素。

双层嵌套 for 循环的大 O 记法是：O(N²)      也被叫作二次工夫

对于 N 个元素的数组，使双层嵌套 for 循环，要操作 N * N 步。